gcc/tree-cfg.c

   1 /* Control flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
   3    Free Software Foundation, Inc.
   4    Contributed by Diego Novillo <dnovillo@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License 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 "tree.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "hard-reg-set.h"
  30 #include "basic-block.h"
  31 #include "output.h"
  32 #include "flags.h"
  33 #include "function.h"
  34 #include "expr.h"
  35 #include "ggc.h"
  36 #include "langhooks.h"
  37 #include "diagnostic.h"
  38 #include "tree-flow.h"
  39 #include "timevar.h"
  40 #include "tree-dump.h"
  41 #include "tree-pass.h"
  42 #include "toplev.h"
  43 #include "except.h"
  44 #include "cfgloop.h"
  45 #include "cfglayout.h"
  46 #include "tree-ssa-propagate.h"
  47 #include "value-prof.h"
  48 #include "pointer-set.h"
  49 #include "tree-inline.h"
  50
  51 /* This file contains functions for building the Control Flow Graph (CFG)
  52    for a function tree.  */
  53
  54 /* Local declarations.  */
  55
  56 /* Initial capacity for the basic block array.  */
  57 static const int initial_cfg_capacity = 20;
  58
  59 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
  60    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
  61    via their TREE_CHAIN field, which we clear after we're done with the
  62    hash table to prevent problems with duplication of GIMPLE_SWITCHes.
  63
  64    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
  65    update the case vector in response to edge redirections.
  66
  67    Right now this table is set up and torn down at key points in the
  68    compilation process.  It would be nice if we could make the table
  69    more persistent.  The key is getting notification of changes to
  70    the CFG (particularly edge removal, creation and redirection).  */
  71
  72 static struct pointer_map_t *edge_to_cases;
  73
  74 /* CFG statistics.  */
  75 struct cfg_stats_d
  76 {
  77   long num_merged_labels;
  78 };
  79
  80 static struct cfg_stats_d cfg_stats;
  81
  82 /* Nonzero if we found a computed goto while building basic blocks.  */
  83 static bool found_computed_goto;
  84
  85 /* Hash table to store last discriminator assigned for each locus.  */
  86 struct locus_discrim_map
  87 {
  88   location_t locus;
  89   int discriminator;
  90 };
  91 static htab_t discriminator_per_locus;
  92
  93 /* Basic blocks and flowgraphs.  */
  94 static void make_blocks (gimple_seq);
  95 static void factor_computed_gotos (void);
  96
  97 /* Edges.  */
  98 static void make_edges (void);
  99 static void make_cond_expr_edges (basic_block);
 100 static void make_gimple_switch_edges (basic_block);
 101 static void make_goto_expr_edges (basic_block);
 102 static void make_gimple_asm_edges (basic_block);
 103 static unsigned int locus_map_hash (const void *);
 104 static int locus_map_eq (const void *, const void *);
 105 static void assign_discriminator (location_t, basic_block);
 106 static edge gimple_redirect_edge_and_branch (edge, basic_block);
 107 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block);
 108 static unsigned int split_critical_edges (void);
 109
 110 /* Various helpers.  */
 111 static inline bool stmt_starts_bb_p (gimple, gimple);
 112 static int gimple_verify_flow_info (void);
 113 static void gimple_make_forwarder_block (edge);
 114 static void gimple_cfg2vcg (FILE *);
 115 static gimple first_non_label_stmt (basic_block);
 116
 117 /* Flowgraph optimization and cleanup.  */
 118 static void gimple_merge_blocks (basic_block, basic_block);
 119 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
 120 static void remove_bb (basic_block);
 121 static edge find_taken_edge_computed_goto (basic_block, tree);
 122 static edge find_taken_edge_cond_expr (basic_block, tree);
 123 static edge find_taken_edge_switch_expr (basic_block, tree);
 124 static tree find_case_label_for_value (gimple, tree);
 125
 126 void
 127 init_empty_tree_cfg_for_function (struct function *fn)
 128 {
 129   /* Initialize the basic block array.  */
 130   init_flow (fn);
 131   profile_status_for_function (fn) = PROFILE_ABSENT;
 132   n_basic_blocks_for_function (fn) = NUM_FIXED_BLOCKS;
 133   last_basic_block_for_function (fn) = NUM_FIXED_BLOCKS;
 134   basic_block_info_for_function (fn)
 135     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 136   VEC_safe_grow_cleared (basic_block, gc,
 137                          basic_block_info_for_function (fn),
 138                          initial_cfg_capacity);
 139
 140   /* Build a mapping of labels to their associated blocks.  */
 141   label_to_block_map_for_function (fn)
 142     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 143   VEC_safe_grow_cleared (basic_block, gc,
 144                          label_to_block_map_for_function (fn),
 145                          initial_cfg_capacity);
 146
 147   SET_BASIC_BLOCK_FOR_FUNCTION (fn, ENTRY_BLOCK,
 148                                 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn));
 149   SET_BASIC_BLOCK_FOR_FUNCTION (fn, EXIT_BLOCK,
 150                    EXIT_BLOCK_PTR_FOR_FUNCTION (fn));
 151
 152   ENTRY_BLOCK_PTR_FOR_FUNCTION (fn)->next_bb
 153     = EXIT_BLOCK_PTR_FOR_FUNCTION (fn);
 154   EXIT_BLOCK_PTR_FOR_FUNCTION (fn)->prev_bb
 155     = ENTRY_BLOCK_PTR_FOR_FUNCTION (fn);
 156 }
 157
 158 void
 159 init_empty_tree_cfg (void)
 160 {
 161   init_empty_tree_cfg_for_function (cfun);
 162 }
 163
 164 /*---------------------------------------------------------------------------
 165                               Create basic blocks
 166 ---------------------------------------------------------------------------*/
 167
 168 /* Entry point to the CFG builder for trees.  SEQ is the sequence of
 169    statements to be added to the flowgraph.  */
 170
 171 static void
 172 build_gimple_cfg (gimple_seq seq)
 173 {
 174   /* Register specific gimple functions.  */
 175   gimple_register_cfg_hooks ();
 176
 177   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
 178
 179   init_empty_tree_cfg ();
 180
 181   found_computed_goto = 0;
 182   make_blocks (seq);
 183
 184   /* Computed gotos are hell to deal with, especially if there are
 185      lots of them with a large number of destinations.  So we factor
 186      them to a common computed goto location before we build the
 187      edge list.  After we convert back to normal form, we will un-factor
 188      the computed gotos since factoring introduces an unwanted jump.  */
 189   if (found_computed_goto)
 190     factor_computed_gotos ();
 191
 192   /* Make sure there is always at least one block, even if it's empty.  */
 193   if (n_basic_blocks == NUM_FIXED_BLOCKS)
 194     create_empty_bb (ENTRY_BLOCK_PTR);
 195
 196   /* Adjust the size of the array.  */
 197   if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
 198     VEC_safe_grow_cleared (basic_block, gc, basic_block_info, n_basic_blocks);
 199
 200   /* To speed up statement iterator walks, we first purge dead labels.  */
 201   cleanup_dead_labels ();
 202
 203   /* Group case nodes to reduce the number of edges.
 204      We do this after cleaning up dead labels because otherwise we miss
 205      a lot of obvious case merging opportunities.  */
 206   group_case_labels ();
 207
 208   /* Create the edges of the flowgraph.  */
 209   discriminator_per_locus = htab_create (13, locus_map_hash, locus_map_eq,
 210                                          free);
 211   make_edges ();
 212   cleanup_dead_labels ();
 213   htab_delete (discriminator_per_locus);
 214
 215   /* Debugging dumps.  */
 216
 217   /* Write the flowgraph to a VCG file.  */
 218   {
 219     int local_dump_flags;
 220     FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
 221     if (vcg_file)
 222       {
 223         gimple_cfg2vcg (vcg_file);
 224         dump_end (TDI_vcg, vcg_file);
 225       }
 226   }
 227
 228 #ifdef ENABLE_CHECKING
 229   verify_stmts ();
 230 #endif
 231 }
 232
 233 static unsigned int
 234 execute_build_cfg (void)
 235 {
 236   gimple_seq body = gimple_body (current_function_decl);
 237
 238   build_gimple_cfg (body);
 239   gimple_set_body (current_function_decl, NULL);
 240   if (dump_file && (dump_flags & TDF_DETAILS))
 241     {
 242       fprintf (dump_file, "Scope blocks:\n");
 243       dump_scope_blocks (dump_file, dump_flags);
 244     }
 245   return 0;
 246 }
 247
 248 struct gimple_opt_pass pass_build_cfg =
 249 {
 250  {
 251   GIMPLE_PASS,
 252   "cfg",                                /* name */
 253   NULL,                                 /* gate */
 254   execute_build_cfg,                    /* execute */
 255   NULL,                                 /* sub */
 256   NULL,                                 /* next */
 257   0,                                    /* static_pass_number */
 258   TV_TREE_CFG,                          /* tv_id */
 259   PROP_gimple_leh,                      /* properties_required */
 260   PROP_cfg,                             /* properties_provided */
 261   0,                                    /* properties_destroyed */
 262   0,                                    /* todo_flags_start */
 263   TODO_verify_stmts | TODO_cleanup_cfg
 264   | TODO_dump_func                      /* todo_flags_finish */
 265  }
 266 };
 267
 268
 269 /* Return true if T is a computed goto.  */
 270
 271 static bool
 272 computed_goto_p (gimple t)
 273 {
 274   return (gimple_code (t) == GIMPLE_GOTO
 275           && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
 276 }
 277
 278
 279 /* Search the CFG for any computed gotos.  If found, factor them to a
 280    common computed goto site.  Also record the location of that site so
 281    that we can un-factor the gotos after we have converted back to
 282    normal form.  */
 283
 284 static void
 285 factor_computed_gotos (void)
 286 {
 287   basic_block bb;
 288   tree factored_label_decl = NULL;
 289   tree var = NULL;
 290   gimple factored_computed_goto_label = NULL;
 291   gimple factored_computed_goto = NULL;
 292
 293   /* We know there are one or more computed gotos in this function.
 294      Examine the last statement in each basic block to see if the block
 295      ends with a computed goto.  */
 296
 297   FOR_EACH_BB (bb)
 298     {
 299       gimple_stmt_iterator gsi = gsi_last_bb (bb);
 300       gimple last;
 301
 302       if (gsi_end_p (gsi))
 303         continue;
 304
 305       last = gsi_stmt (gsi);
 306
 307       /* Ignore the computed goto we create when we factor the original
 308          computed gotos.  */
 309       if (last == factored_computed_goto)
 310         continue;
 311
 312       /* If the last statement is a computed goto, factor it.  */
 313       if (computed_goto_p (last))
 314         {
 315           gimple assignment;
 316
 317           /* The first time we find a computed goto we need to create
 318              the factored goto block and the variable each original
 319              computed goto will use for their goto destination.  */
 320           if (!factored_computed_goto)
 321             {
 322               basic_block new_bb = create_empty_bb (bb);
 323               gimple_stmt_iterator new_gsi = gsi_start_bb (new_bb);
 324
 325               /* Create the destination of the factored goto.  Each original
 326                  computed goto will put its desired destination into this
 327                  variable and jump to the label we create immediately
 328                  below.  */
 329               var = create_tmp_var (ptr_type_node, "gotovar");
 330
 331               /* Build a label for the new block which will contain the
 332                  factored computed goto.  */
 333               factored_label_decl = create_artificial_label (UNKNOWN_LOCATION);
 334               factored_computed_goto_label
 335                 = gimple_build_label (factored_label_decl);
 336               gsi_insert_after (&new_gsi, factored_computed_goto_label,
 337                                 GSI_NEW_STMT);
 338
 339               /* Build our new computed goto.  */
 340               factored_computed_goto = gimple_build_goto (var);
 341               gsi_insert_after (&new_gsi, factored_computed_goto, GSI_NEW_STMT);
 342             }
 343
 344           /* Copy the original computed goto's destination into VAR.  */
 345           assignment = gimple_build_assign (var, gimple_goto_dest (last));
 346           gsi_insert_before (&gsi, assignment, GSI_SAME_STMT);
 347
 348           /* And re-vector the computed goto to the new destination.  */
 349           gimple_goto_set_dest (last, factored_label_decl);
 350         }
 351     }
 352 }
 353
 354
 355 /* Build a flowgraph for the sequence of stmts SEQ.  */
 356
 357 static void
 358 make_blocks (gimple_seq seq)
 359 {
 360   gimple_stmt_iterator i = gsi_start (seq);
 361   gimple stmt = NULL;
 362   bool start_new_block = true;
 363   bool first_stmt_of_seq = true;
 364   basic_block bb = ENTRY_BLOCK_PTR;
 365
 366   while (!gsi_end_p (i))
 367     {
 368       gimple prev_stmt;
 369
 370       prev_stmt = stmt;
 371       stmt = gsi_stmt (i);
 372
 373       /* If the statement starts a new basic block or if we have determined
 374          in a previous pass that we need to create a new block for STMT, do
 375          so now.  */
 376       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
 377         {
 378           if (!first_stmt_of_seq)
 379             seq = gsi_split_seq_before (&i);
 380           bb = create_basic_block (seq, NULL, bb);
 381           start_new_block = false;
 382         }
 383
 384       /* Now add STMT to BB and create the subgraphs for special statement
 385          codes.  */
 386       gimple_set_bb (stmt, bb);
 387
 388       if (computed_goto_p (stmt))
 389         found_computed_goto = true;
 390
 391       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
 392          next iteration.  */
 393       if (stmt_ends_bb_p (stmt))
 394         {
 395           /* If the stmt can make abnormal goto use a new temporary
 396              for the assignment to the LHS.  This makes sure the old value
 397              of the LHS is available on the abnormal edge.  Otherwise
 398              we will end up with overlapping life-ranges for abnormal
 399              SSA names.  */
 400           if (gimple_has_lhs (stmt)
 401               && stmt_can_make_abnormal_goto (stmt)
 402               && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt))))
 403             {
 404               tree lhs = gimple_get_lhs (stmt);
 405               tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
 406               gimple s = gimple_build_assign (lhs, tmp);
 407               gimple_set_location (s, gimple_location (stmt));
 408               gimple_set_block (s, gimple_block (stmt));
 409               gimple_set_lhs (stmt, tmp);
 410               if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE
 411                   || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE)
 412                 DECL_GIMPLE_REG_P (tmp) = 1;
 413               gsi_insert_after (&i, s, GSI_SAME_STMT);
 414             }
 415           start_new_block = true;
 416         }
 417
 418       gsi_next (&i);
 419       first_stmt_of_seq = false;
 420     }
 421 }
 422
 423
 424 /* Create and return a new empty basic block after bb AFTER.  */
 425
 426 static basic_block
 427 create_bb (void *h, void *e, basic_block after)
 428 {
 429   basic_block bb;
 430
 431   gcc_assert (!e);
 432
 433   /* Create and initialize a new basic block.  Since alloc_block uses
 434      ggc_alloc_cleared to allocate a basic block, we do not have to
 435      clear the newly allocated basic block here.  */
 436   bb = alloc_block ();
 437
 438   bb->index = last_basic_block;
 439   bb->flags = BB_NEW;
 440   bb->il.gimple = GGC_CNEW (struct gimple_bb_info);
 441   set_bb_seq (bb, h ? (gimple_seq) h : gimple_seq_alloc ());
 442
 443   /* Add the new block to the linked list of blocks.  */
 444   link_block (bb, after);
 445
 446   /* Grow the basic block array if needed.  */
 447   if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
 448     {
 449       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
 450       VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
 451     }
 452
 453   /* Add the newly created block to the array.  */
 454   SET_BASIC_BLOCK (last_basic_block, bb);
 455
 456   n_basic_blocks++;
 457   last_basic_block++;
 458
 459   return bb;
 460 }
 461
 462
 463 /*---------------------------------------------------------------------------
 464                                  Edge creation
 465 ---------------------------------------------------------------------------*/
 466
 467 /* Fold COND_EXPR_COND of each COND_EXPR.  */
 468
 469 void
 470 fold_cond_expr_cond (void)
 471 {
 472   basic_block bb;
 473
 474   FOR_EACH_BB (bb)
 475     {
 476       gimple stmt = last_stmt (bb);
 477
 478       if (stmt && gimple_code (stmt) == GIMPLE_COND)
 479         {
 480           location_t loc = gimple_location (stmt);
 481           tree cond;
 482           bool zerop, onep;
 483
 484           fold_defer_overflow_warnings ();
 485           cond = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node,
 486                               gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 487           if (cond)
 488             {
 489               zerop = integer_zerop (cond);
 490               onep = integer_onep (cond);
 491             }
 492           else
 493             zerop = onep = false;
 494
 495           fold_undefer_overflow_warnings (zerop || onep,
 496                                           stmt,
 497                                           WARN_STRICT_OVERFLOW_CONDITIONAL);
 498           if (zerop)
 499             gimple_cond_make_false (stmt);
 500           else if (onep)
 501             gimple_cond_make_true (stmt);
 502         }
 503     }
 504 }
 505
 506 /* Join all the blocks in the flowgraph.  */
 507
 508 static void
 509 make_edges (void)
 510 {
 511   basic_block bb;
 512   struct omp_region *cur_region = NULL;
 513
 514   /* Create an edge from entry to the first block with executable
 515      statements in it.  */
 516   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
 517
 518   /* Traverse the basic block array placing edges.  */
 519   FOR_EACH_BB (bb)
 520     {
 521       gimple last = last_stmt (bb);
 522       bool fallthru;
 523
 524       if (last)
 525         {
 526           enum gimple_code code = gimple_code (last);
 527           switch (code)
 528             {
 529             case GIMPLE_GOTO:
 530               make_goto_expr_edges (bb);
 531               fallthru = false;
 532               break;
 533             case GIMPLE_RETURN:
 534               make_edge (bb, EXIT_BLOCK_PTR, 0);
 535               fallthru = false;
 536               break;
 537             case GIMPLE_COND:
 538               make_cond_expr_edges (bb);
 539               fallthru = false;
 540               break;
 541             case GIMPLE_SWITCH:
 542               make_gimple_switch_edges (bb);
 543               fallthru = false;
 544               break;
 545             case GIMPLE_RESX:
 546               make_eh_edges (last);
 547               fallthru = false;
 548               break;
 549             case GIMPLE_EH_DISPATCH:
 550               fallthru = make_eh_dispatch_edges (last);
 551               break;
 552
 553             case GIMPLE_CALL:
 554               /* If this function receives a nonlocal goto, then we need to
 555                  make edges from this call site to all the nonlocal goto
 556                  handlers.  */
 557               if (stmt_can_make_abnormal_goto (last))
 558                 make_abnormal_goto_edges (bb, true);
 559
 560               /* If this statement has reachable exception handlers, then
 561                  create abnormal edges to them.  */
 562               make_eh_edges (last);
 563
 564               /* Some calls are known not to return.  */
 565               fallthru = !(gimple_call_flags (last) & ECF_NORETURN);
 566               break;
 567
 568             case GIMPLE_ASSIGN:
 569                /* A GIMPLE_ASSIGN may throw internally and thus be considered
 570                   control-altering. */
 571               if (is_ctrl_altering_stmt (last))
 572                 make_eh_edges (last);
 573               fallthru = true;
 574               break;
 575
 576             case GIMPLE_ASM:
 577               make_gimple_asm_edges (bb);
 578               fallthru = true;
 579               break;
 580
 581             case GIMPLE_OMP_PARALLEL:
 582             case GIMPLE_OMP_TASK:
 583             case GIMPLE_OMP_FOR:
 584             case GIMPLE_OMP_SINGLE:
 585             case GIMPLE_OMP_MASTER:
 586             case GIMPLE_OMP_ORDERED:
 587             case GIMPLE_OMP_CRITICAL:
 588             case GIMPLE_OMP_SECTION:
 589               cur_region = new_omp_region (bb, code, cur_region);
 590               fallthru = true;
 591               break;
 592
 593             case GIMPLE_OMP_SECTIONS:
 594               cur_region = new_omp_region (bb, code, cur_region);
 595               fallthru = true;
 596               break;
 597
 598             case GIMPLE_OMP_SECTIONS_SWITCH:
 599               fallthru = false;
 600               break;
 601
 602             case GIMPLE_OMP_ATOMIC_LOAD:
 603             case GIMPLE_OMP_ATOMIC_STORE:
 604                fallthru = true;
 605                break;
 606
 607             case GIMPLE_OMP_RETURN:
 608               /* In the case of a GIMPLE_OMP_SECTION, the edge will go
 609                  somewhere other than the next block.  This will be
 610                  created later.  */
 611               cur_region->exit = bb;
 612               fallthru = cur_region->type != GIMPLE_OMP_SECTION;
 613               cur_region = cur_region->outer;
 614               break;
 615
 616             case GIMPLE_OMP_CONTINUE:
 617               cur_region->cont = bb;
 618               switch (cur_region->type)
 619                 {
 620                 case GIMPLE_OMP_FOR:
 621                   /* Mark all GIMPLE_OMP_FOR and GIMPLE_OMP_CONTINUE
 622                      succs edges as abnormal to prevent splitting
 623                      them.  */
 624                   single_succ_edge (cur_region->entry)->flags |= EDGE_ABNORMAL;
 625                   /* Make the loopback edge.  */
 626                   make_edge (bb, single_succ (cur_region->entry),
 627                              EDGE_ABNORMAL);
 628
 629                   /* Create an edge from GIMPLE_OMP_FOR to exit, which
 630                      corresponds to the case that the body of the loop
 631                      is not executed at all.  */
 632                   make_edge (cur_region->entry, bb->next_bb, EDGE_ABNORMAL);
 633                   make_edge (bb, bb->next_bb, EDGE_FALLTHRU | EDGE_ABNORMAL);
 634                   fallthru = false;
 635                   break;
 636
 637                 case GIMPLE_OMP_SECTIONS:
 638                   /* Wire up the edges into and out of the nested sections.  */
 639                   {
 640                     basic_block switch_bb = single_succ (cur_region->entry);
 641
 642                     struct omp_region *i;
 643                     for (i = cur_region->inner; i ; i = i->next)
 644                       {
 645                         gcc_assert (i->type == GIMPLE_OMP_SECTION);
 646                         make_edge (switch_bb, i->entry, 0);
 647                         make_edge (i->exit, bb, EDGE_FALLTHRU);
 648                       }
 649
 650                     /* Make the loopback edge to the block with
 651                        GIMPLE_OMP_SECTIONS_SWITCH.  */
 652                     make_edge (bb, switch_bb, 0);
 653
 654                     /* Make the edge from the switch to exit.  */
 655                     make_edge (switch_bb, bb->next_bb, 0);
 656                     fallthru = false;
 657                   }
 658                   break;
 659
 660                 default:
 661                   gcc_unreachable ();
 662                 }
 663               break;
 664
 665             default:
 666               gcc_assert (!stmt_ends_bb_p (last));
 667               fallthru = true;
 668             }
 669         }
 670       else
 671         fallthru = true;
 672
 673       if (fallthru)
 674         {
 675           make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 676           if (last)
 677             assign_discriminator (gimple_location (last), bb->next_bb);
 678         }
 679     }
 680
 681   if (root_omp_region)
 682     free_omp_regions ();
 683
 684   /* Fold COND_EXPR_COND of each COND_EXPR.  */
 685   fold_cond_expr_cond ();
 686 }
 687
 688 /* Trivial hash function for a location_t.  ITEM is a pointer to
 689    a hash table entry that maps a location_t to a discriminator.  */
 690
 691 static unsigned int
 692 locus_map_hash (const void *item)
 693 {
 694   return ((const struct locus_discrim_map *) item)->locus;
 695 }
 696
 697 /* Equality function for the locus-to-discriminator map.  VA and VB
 698    point to the two hash table entries to compare.  */
 699
 700 static int
 701 locus_map_eq (const void *va, const void *vb)
 702 {
 703   const struct locus_discrim_map *a = (const struct locus_discrim_map *) va;
 704   const struct locus_discrim_map *b = (const struct locus_discrim_map *) vb;
 705   return a->locus == b->locus;
 706 }
 707
 708 /* Find the next available discriminator value for LOCUS.  The
 709    discriminator distinguishes among several basic blocks that
 710    share a common locus, allowing for more accurate sample-based
 711    profiling.  */
 712
 713 static int
 714 next_discriminator_for_locus (location_t locus)
 715 {
 716   struct locus_discrim_map item;
 717   struct locus_discrim_map **slot;
 718
 719   item.locus = locus;
 720   item.discriminator = 0;
 721   slot = (struct locus_discrim_map **)
 722       htab_find_slot_with_hash (discriminator_per_locus, (void *) &item,
 723                                 (hashval_t) locus, INSERT);
 724   gcc_assert (slot);
 725   if (*slot == HTAB_EMPTY_ENTRY)
 726     {
 727       *slot = XNEW (struct locus_discrim_map);
 728       gcc_assert (*slot);
 729       (*slot)->locus = locus;
 730       (*slot)->discriminator = 0;
 731     }
 732   (*slot)->discriminator++;
 733   return (*slot)->discriminator;
 734 }
 735
 736 /* Return TRUE if LOCUS1 and LOCUS2 refer to the same source line.  */
 737
 738 static bool
 739 same_line_p (location_t locus1, location_t locus2)
 740 {
 741   expanded_location from, to;
 742
 743   if (locus1 == locus2)
 744     return true;
 745
 746   from = expand_location (locus1);
 747   to = expand_location (locus2);
 748
 749   if (from.line != to.line)
 750     return false;
 751   if (from.file == to.file)
 752     return true;
 753   return (from.file != NULL
 754           && to.file != NULL
 755           && strcmp (from.file, to.file) == 0);
 756 }
 757
 758 /* Assign a unique discriminator value to block BB if it begins at the same
 759    LOCUS as its predecessor block.  */
 760
 761 static void
 762 assign_discriminator (location_t locus, basic_block bb)
 763 {
 764   gimple first_in_to_bb, last_in_to_bb;
 765
 766   if (locus == 0 || bb->discriminator != 0)
 767     return;
 768
 769   first_in_to_bb = first_non_label_stmt (bb);
 770   last_in_to_bb = last_stmt (bb);
 771   if ((first_in_to_bb && same_line_p (locus, gimple_location (first_in_to_bb)))
 772       || (last_in_to_bb && same_line_p (locus, gimple_location (last_in_to_bb))))
 773     bb->discriminator = next_discriminator_for_locus (locus);
 774 }
 775
 776 /* Create the edges for a GIMPLE_COND starting at block BB.  */
 777
 778 static void
 779 make_cond_expr_edges (basic_block bb)
 780 {
 781   gimple entry = last_stmt (bb);
 782   gimple then_stmt, else_stmt;
 783   basic_block then_bb, else_bb;
 784   tree then_label, else_label;
 785   edge e;
 786   location_t entry_locus;
 787
 788   gcc_assert (entry);
 789   gcc_assert (gimple_code (entry) == GIMPLE_COND);
 790
 791   entry_locus = gimple_location (entry);
 792
 793   /* Entry basic blocks for each component.  */
 794   then_label = gimple_cond_true_label (entry);
 795   else_label = gimple_cond_false_label (entry);
 796   then_bb = label_to_block (then_label);
 797   else_bb = label_to_block (else_label);
 798   then_stmt = first_stmt (then_bb);
 799   else_stmt = first_stmt (else_bb);
 800
 801   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
 802   assign_discriminator (entry_locus, then_bb);
 803   e->goto_locus = gimple_location (then_stmt);
 804   if (e->goto_locus)
 805     e->goto_block = gimple_block (then_stmt);
 806   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
 807   if (e)
 808     {
 809       assign_discriminator (entry_locus, else_bb);
 810       e->goto_locus = gimple_location (else_stmt);
 811       if (e->goto_locus)
 812         e->goto_block = gimple_block (else_stmt);
 813     }
 814
 815   /* We do not need the labels anymore.  */
 816   gimple_cond_set_true_label (entry, NULL_TREE);
 817   gimple_cond_set_false_label (entry, NULL_TREE);
 818 }
 819
 820
 821 /* Called for each element in the hash table (P) as we delete the
 822    edge to cases hash table.
 823
 824    Clear all the TREE_CHAINs to prevent problems with copying of
 825    SWITCH_EXPRs and structure sharing rules, then free the hash table
 826    element.  */
 827
 828 static bool
 829 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
 830                        void *data ATTRIBUTE_UNUSED)
 831 {
 832   tree t, next;
 833
 834   for (t = (tree) *value; t; t = next)
 835     {
 836       next = TREE_CHAIN (t);
 837       TREE_CHAIN (t) = NULL;
 838     }
 839
 840   *value = NULL;
 841   return false;
 842 }
 843
 844 /* Start recording information mapping edges to case labels.  */
 845
 846 void
 847 start_recording_case_labels (void)
 848 {
 849   gcc_assert (edge_to_cases == NULL);
 850   edge_to_cases = pointer_map_create ();
 851 }
 852
 853 /* Return nonzero if we are recording information for case labels.  */
 854
 855 static bool
 856 recording_case_labels_p (void)
 857 {
 858   return (edge_to_cases != NULL);
 859 }
 860
 861 /* Stop recording information mapping edges to case labels and
 862    remove any information we have recorded.  */
 863 void
 864 end_recording_case_labels (void)
 865 {
 866   pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
 867   pointer_map_destroy (edge_to_cases);
 868   edge_to_cases = NULL;
 869 }
 870
 871 /* If we are inside a {start,end}_recording_cases block, then return
 872    a chain of CASE_LABEL_EXPRs from T which reference E.
 873
 874    Otherwise return NULL.  */
 875
 876 static tree
 877 get_cases_for_edge (edge e, gimple t)
 878 {
 879   void **slot;
 880   size_t i, n;
 881
 882   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
 883      chains available.  Return NULL so the caller can detect this case.  */
 884   if (!recording_case_labels_p ())
 885     return NULL;
 886
 887   slot = pointer_map_contains (edge_to_cases, e);
 888   if (slot)
 889     return (tree) *slot;
 890
 891   /* If we did not find E in the hash table, then this must be the first
 892      time we have been queried for information about E & T.  Add all the
 893      elements from T to the hash table then perform the query again.  */
 894
 895   n = gimple_switch_num_labels (t);
 896   for (i = 0; i < n; i++)
 897     {
 898       tree elt = gimple_switch_label (t, i);
 899       tree lab = CASE_LABEL (elt);
 900       basic_block label_bb = label_to_block (lab);
 901       edge this_edge = find_edge (e->src, label_bb);
 902
 903       /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
 904          a new chain.  */
 905       slot = pointer_map_insert (edge_to_cases, this_edge);
 906       TREE_CHAIN (elt) = (tree) *slot;
 907       *slot = elt;
 908     }
 909
 910   return (tree) *pointer_map_contains (edge_to_cases, e);
 911 }
 912
 913 /* Create the edges for a GIMPLE_SWITCH starting at block BB.  */
 914
 915 static void
 916 make_gimple_switch_edges (basic_block bb)
 917 {
 918   gimple entry = last_stmt (bb);
 919   location_t entry_locus;
 920   size_t i, n;
 921
 922   entry_locus = gimple_location (entry);
 923
 924   n = gimple_switch_num_labels (entry);
 925
 926   for (i = 0; i < n; ++i)
 927     {
 928       tree lab = CASE_LABEL (gimple_switch_label (entry, i));
 929       basic_block label_bb = label_to_block (lab);
 930       make_edge (bb, label_bb, 0);
 931       assign_discriminator (entry_locus, label_bb);
 932     }
 933 }
 934
 935
 936 /* Return the basic block holding label DEST.  */
 937
 938 basic_block
 939 label_to_block_fn (struct function *ifun, tree dest)
 940 {
 941   int uid = LABEL_DECL_UID (dest);
 942
 943   /* We would die hard when faced by an undefined label.  Emit a label to
 944      the very first basic block.  This will hopefully make even the dataflow
 945      and undefined variable warnings quite right.  */
 946   if ((errorcount || sorrycount) && uid < 0)
 947     {
 948       gimple_stmt_iterator gsi = gsi_start_bb (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 949       gimple stmt;
 950
 951       stmt = gimple_build_label (dest);
 952       gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 953       uid = LABEL_DECL_UID (dest);
 954     }
 955   if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
 956       <= (unsigned int) uid)
 957     return NULL;
 958   return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
 959 }
 960
 961 /* Create edges for an abnormal goto statement at block BB.  If FOR_CALL
 962    is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR.  */
 963
 964 void
 965 make_abnormal_goto_edges (basic_block bb, bool for_call)
 966 {
 967   basic_block target_bb;
 968   gimple_stmt_iterator gsi;
 969
 970   FOR_EACH_BB (target_bb)
 971     for (gsi = gsi_start_bb (target_bb); !gsi_end_p (gsi); gsi_next (&gsi))
 972       {
 973         gimple label_stmt = gsi_stmt (gsi);
 974         tree target;
 975
 976         if (gimple_code (label_stmt) != GIMPLE_LABEL)
 977           break;
 978
 979         target = gimple_label_label (label_stmt);
 980
 981         /* Make an edge to every label block that has been marked as a
 982            potential target for a computed goto or a non-local goto.  */
 983         if ((FORCED_LABEL (target) && !for_call)
 984             || (DECL_NONLOCAL (target) && for_call))
 985           {
 986             make_edge (bb, target_bb, EDGE_ABNORMAL);
 987             break;
 988           }
 989       }
 990 }
 991
 992 /* Create edges for a goto statement at block BB.  */
 993
 994 static void
 995 make_goto_expr_edges (basic_block bb)
 996 {
 997   gimple_stmt_iterator last = gsi_last_bb (bb);
 998   gimple goto_t = gsi_stmt (last);
 999
1000   /* A simple GOTO creates normal edges.  */
1001   if (simple_goto_p (goto_t))
1002     {
1003       tree dest = gimple_goto_dest (goto_t);
1004       basic_block label_bb = label_to_block (dest);
1005       edge e = make_edge (bb, label_bb, EDGE_FALLTHRU);
1006       e->goto_locus = gimple_location (goto_t);
1007       assign_discriminator (e->goto_locus, label_bb);
1008       if (e->goto_locus)
1009         e->goto_block = gimple_block (goto_t);
1010       gsi_remove (&last, true);
1011       return;
1012     }
1013
1014   /* A computed GOTO creates abnormal edges.  */
1015   make_abnormal_goto_edges (bb, false);
1016 }
1017
1018 /* Create edges for an asm statement with labels at block BB.  */
1019
1020 static void
1021 make_gimple_asm_edges (basic_block bb)
1022 {
1023   gimple stmt = last_stmt (bb);
1024   location_t stmt_loc = gimple_location (stmt);
1025   int i, n = gimple_asm_nlabels (stmt);
1026
1027   for (i = 0; i < n; ++i)
1028     {
1029       tree label = TREE_VALUE (gimple_asm_label_op (stmt, i));
1030       basic_block label_bb = label_to_block (label);
1031       make_edge (bb, label_bb, 0);
1032       assign_discriminator (stmt_loc, label_bb);
1033     }
1034 }
1035
1036 /*---------------------------------------------------------------------------
1037                                Flowgraph analysis
1038 ---------------------------------------------------------------------------*/
1039
1040 /* Cleanup useless labels in basic blocks.  This is something we wish
1041    to do early because it allows us to group case labels before creating
1042    the edges for the CFG, and it speeds up block statement iterators in
1043    all passes later on.
1044    We rerun this pass after CFG is created, to get rid of the labels that
1045    are no longer referenced.  After then we do not run it any more, since
1046    (almost) no new labels should be created.  */
1047
1048 /* A map from basic block index to the leading label of that block.  */
1049 static struct label_record
1050 {
1051   /* The label.  */
1052   tree label;
1053
1054   /* True if the label is referenced from somewhere.  */
1055   bool used;
1056 } *label_for_bb;
1057
1058 /* Given LABEL return the first label in the same basic block.  */
1059
1060 static tree
1061 main_block_label (tree label)
1062 {
1063   basic_block bb = label_to_block (label);
1064   tree main_label = label_for_bb[bb->index].label;
1065
1066   /* label_to_block possibly inserted undefined label into the chain.  */
1067   if (!main_label)
1068     {
1069       label_for_bb[bb->index].label = label;
1070       main_label = label;
1071     }
1072
1073   label_for_bb[bb->index].used = true;
1074   return main_label;
1075 }
1076
1077 /* Clean up redundant labels within the exception tree.  */
1078
1079 static void
1080 cleanup_dead_labels_eh (void)
1081 {
1082   eh_landing_pad lp;
1083   eh_region r;
1084   tree lab;
1085   int i;
1086
1087   if (cfun->eh == NULL)
1088     return;
1089
1090   for (i = 1; VEC_iterate (eh_landing_pad, cfun->eh->lp_array, i, lp); ++i)
1091     if (lp && lp->post_landing_pad)
1092       {
1093         lab = main_block_label (lp->post_landing_pad);
1094         if (lab != lp->post_landing_pad)
1095           {
1096             EH_LANDING_PAD_NR (lp->post_landing_pad) = 0;
1097             EH_LANDING_PAD_NR (lab) = lp->index;
1098           }
1099       }
1100
1101   FOR_ALL_EH_REGION (r)
1102     switch (r->type)
1103       {
1104       case ERT_CLEANUP:
1105       case ERT_MUST_NOT_THROW:
1106         break;
1107
1108       case ERT_TRY:
1109         {
1110           eh_catch c;
1111           for (c = r->u.eh_try.first_catch; c ; c = c->next_catch)
1112             {
1113               lab = c->label;
1114               if (lab)
1115                 c->label = main_block_label (lab);
1116             }
1117         }
1118         break;
1119
1120       case ERT_ALLOWED_EXCEPTIONS:
1121         lab = r->u.allowed.label;
1122         if (lab)
1123           r->u.allowed.label = main_block_label (lab);
1124         break;
1125       }
1126 }
1127
1128
1129 /* Cleanup redundant labels.  This is a three-step process:
1130      1) Find the leading label for each block.
1131      2) Redirect all references to labels to the leading labels.
1132      3) Cleanup all useless labels.  */
1133
1134 void
1135 cleanup_dead_labels (void)
1136 {
1137   basic_block bb;
1138   label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
1139
1140   /* Find a suitable label for each block.  We use the first user-defined
1141      label if there is one, or otherwise just the first label we see.  */
1142   FOR_EACH_BB (bb)
1143     {
1144       gimple_stmt_iterator i;
1145
1146       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
1147         {
1148           tree label;
1149           gimple stmt = gsi_stmt (i);
1150
1151           if (gimple_code (stmt) != GIMPLE_LABEL)
1152             break;
1153
1154           label = gimple_label_label (stmt);
1155
1156           /* If we have not yet seen a label for the current block,
1157              remember this one and see if there are more labels.  */
1158           if (!label_for_bb[bb->index].label)
1159             {
1160               label_for_bb[bb->index].label = label;
1161               continue;
1162             }
1163
1164           /* If we did see a label for the current block already, but it
1165              is an artificially created label, replace it if the current
1166              label is a user defined label.  */
1167           if (!DECL_ARTIFICIAL (label)
1168               && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
1169             {
1170               label_for_bb[bb->index].label = label;
1171               break;
1172             }
1173         }
1174     }
1175
1176   /* Now redirect all jumps/branches to the selected label.
1177      First do so for each block ending in a control statement.  */
1178   FOR_EACH_BB (bb)
1179     {
1180       gimple stmt = last_stmt (bb);
1181       if (!stmt)
1182         continue;
1183
1184       switch (gimple_code (stmt))
1185         {
1186         case GIMPLE_COND:
1187           {
1188             tree true_label = gimple_cond_true_label (stmt);
1189             tree false_label = gimple_cond_false_label (stmt);
1190
1191             if (true_label)
1192               gimple_cond_set_true_label (stmt, main_block_label (true_label));
1193             if (false_label)
1194               gimple_cond_set_false_label (stmt, main_block_label (false_label));
1195             break;
1196           }
1197
1198         case GIMPLE_SWITCH:
1199           {
1200             size_t i, n = gimple_switch_num_labels (stmt);
1201
1202             /* Replace all destination labels.  */
1203             for (i = 0; i < n; ++i)
1204               {
1205                 tree case_label = gimple_switch_label (stmt, i);
1206                 tree label = main_block_label (CASE_LABEL (case_label));
1207                 CASE_LABEL (case_label) = label;
1208               }
1209             break;
1210           }
1211
1212         case GIMPLE_ASM:
1213           {
1214             int i, n = gimple_asm_nlabels (stmt);
1215
1216             for (i = 0; i < n; ++i)
1217               {
1218                 tree cons = gimple_asm_label_op (stmt, i);
1219                 tree label = main_block_label (TREE_VALUE (cons));
1220                 TREE_VALUE (cons) = label;
1221               }
1222             break;
1223           }
1224
1225         /* We have to handle gotos until they're removed, and we don't
1226            remove them until after we've created the CFG edges.  */
1227         case GIMPLE_GOTO:
1228           if (!computed_goto_p (stmt))
1229             {
1230               tree new_dest = main_block_label (gimple_goto_dest (stmt));
1231               gimple_goto_set_dest (stmt, new_dest);
1232             }
1233           break;
1234
1235         default:
1236           break;
1237       }
1238     }
1239
1240   /* Do the same for the exception region tree labels.  */
1241   cleanup_dead_labels_eh ();
1242
1243   /* Finally, purge dead labels.  All user-defined labels and labels that
1244      can be the target of non-local gotos and labels which have their
1245      address taken are preserved.  */
1246   FOR_EACH_BB (bb)
1247     {
1248       gimple_stmt_iterator i;
1249       tree label_for_this_bb = label_for_bb[bb->index].label;
1250
1251       if (!label_for_this_bb)
1252         continue;
1253
1254       /* If the main label of the block is unused, we may still remove it.  */
1255       if (!label_for_bb[bb->index].used)
1256         label_for_this_bb = NULL;
1257
1258       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1259         {
1260           tree label;
1261           gimple stmt = gsi_stmt (i);
1262
1263           if (gimple_code (stmt) != GIMPLE_LABEL)
1264             break;
1265
1266           label = gimple_label_label (stmt);
1267
1268           if (label == label_for_this_bb
1269               || !DECL_ARTIFICIAL (label)
1270               || DECL_NONLOCAL (label)
1271               || FORCED_LABEL (label))
1272             gsi_next (&i);
1273           else
1274             gsi_remove (&i, true);
1275         }
1276     }
1277
1278   free (label_for_bb);
1279 }
1280
1281 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
1282    and scan the sorted vector of cases.  Combine the ones jumping to the
1283    same label.
1284    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1285
1286 void
1287 group_case_labels (void)
1288 {
1289   basic_block bb;
1290
1291   FOR_EACH_BB (bb)
1292     {
1293       gimple stmt = last_stmt (bb);
1294       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1295         {
1296           int old_size = gimple_switch_num_labels (stmt);
1297           int i, j, new_size = old_size;
1298           tree default_case = NULL_TREE;
1299           tree default_label = NULL_TREE;
1300           bool has_default;
1301
1302           /* The default label is always the first case in a switch
1303              statement after gimplification if it was not optimized
1304              away */
1305           if (!CASE_LOW (gimple_switch_default_label (stmt))
1306               && !CASE_HIGH (gimple_switch_default_label (stmt)))
1307             {
1308               default_case = gimple_switch_default_label (stmt);
1309               default_label = CASE_LABEL (default_case);
1310               has_default = true;
1311             }
1312           else
1313             has_default = false;
1314
1315           /* Look for possible opportunities to merge cases.  */
1316           if (has_default)
1317             i = 1;
1318           else
1319             i = 0;
1320           while (i < old_size)
1321             {
1322               tree base_case, base_label, base_high;
1323               base_case = gimple_switch_label (stmt, i);
1324
1325               gcc_assert (base_case);
1326               base_label = CASE_LABEL (base_case);
1327
1328               /* Discard cases that have the same destination as the
1329                  default case.  */
1330               if (base_label == default_label)
1331                 {
1332                   gimple_switch_set_label (stmt, i, NULL_TREE);
1333                   i++;
1334                   new_size--;
1335                   continue;
1336                 }
1337
1338               base_high = CASE_HIGH (base_case)
1339                           ? CASE_HIGH (base_case)
1340                           : CASE_LOW (base_case);
1341               i++;
1342
1343               /* Try to merge case labels.  Break out when we reach the end
1344                  of the label vector or when we cannot merge the next case
1345                  label with the current one.  */
1346               while (i < old_size)
1347                 {
1348                   tree merge_case = gimple_switch_label (stmt, i);
1349                   tree merge_label = CASE_LABEL (merge_case);
1350                   tree t = int_const_binop (PLUS_EXPR, base_high,
1351                                             integer_one_node, 1);
1352
1353                   /* Merge the cases if they jump to the same place,
1354                      and their ranges are consecutive.  */
1355                   if (merge_label == base_label
1356                       && tree_int_cst_equal (CASE_LOW (merge_case), t))
1357                     {
1358                       base_high = CASE_HIGH (merge_case) ?
1359                         CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1360                       CASE_HIGH (base_case) = base_high;
1361                       gimple_switch_set_label (stmt, i, NULL_TREE);
1362                       new_size--;
1363                       i++;
1364                     }
1365                   else
1366                     break;
1367                 }
1368             }
1369
1370           /* Compress the case labels in the label vector, and adjust the
1371              length of the vector.  */
1372           for (i = 0, j = 0; i < new_size; i++)
1373             {
1374               while (! gimple_switch_label (stmt, j))
1375                 j++;
1376               gimple_switch_set_label (stmt, i,
1377                                        gimple_switch_label (stmt, j++));
1378             }
1379
1380           gcc_assert (new_size <= old_size);
1381           gimple_switch_set_num_labels (stmt, new_size);
1382         }
1383     }
1384 }
1385
1386 /* Checks whether we can merge block B into block A.  */
1387
1388 static bool
1389 gimple_can_merge_blocks_p (basic_block a, basic_block b)
1390 {
1391   gimple stmt;
1392   gimple_stmt_iterator gsi;
1393   gimple_seq phis;
1394
1395   if (!single_succ_p (a))
1396     return false;
1397
1398   if (single_succ_edge (a)->flags & (EDGE_ABNORMAL | EDGE_EH))
1399     return false;
1400
1401   if (single_succ (a) != b)
1402     return false;
1403
1404   if (!single_pred_p (b))
1405     return false;
1406
1407   if (b == EXIT_BLOCK_PTR)
1408     return false;
1409
1410   /* If A ends by a statement causing exceptions or something similar, we
1411      cannot merge the blocks.  */
1412   stmt = last_stmt (a);
1413   if (stmt && stmt_ends_bb_p (stmt))
1414     return false;
1415
1416   /* Do not allow a block with only a non-local label to be merged.  */
1417   if (stmt
1418       && gimple_code (stmt) == GIMPLE_LABEL
1419       && DECL_NONLOCAL (gimple_label_label (stmt)))
1420     return false;
1421
1422   /* Examine the labels at the beginning of B.  */
1423   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
1424     {
1425       tree lab;
1426       stmt = gsi_stmt (gsi);
1427       if (gimple_code (stmt) != GIMPLE_LABEL)
1428         break;
1429       lab = gimple_label_label (stmt);
1430
1431       /* Do not remove user labels.  */
1432       if (!DECL_ARTIFICIAL (lab))
1433         return false;
1434     }
1435
1436   /* Protect the loop latches.  */
1437   if (current_loops && b->loop_father->latch == b)
1438     return false;
1439
1440   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1441      is not up-to-date, we cannot eliminate any phis; however, if only
1442      some symbols as whole are marked for renaming, this is not a problem,
1443      as phi nodes for those symbols are irrelevant in updating anyway.  */
1444   phis = phi_nodes (b);
1445   if (!gimple_seq_empty_p (phis))
1446     {
1447       gimple_stmt_iterator i;
1448
1449       if (name_mappings_registered_p ())
1450         return false;
1451
1452       for (i = gsi_start (phis); !gsi_end_p (i); gsi_next (&i))
1453         {
1454           gimple phi = gsi_stmt (i);
1455
1456           if (!is_gimple_reg (gimple_phi_result (phi))
1457               && !may_propagate_copy (gimple_phi_result (phi),
1458                                       gimple_phi_arg_def (phi, 0)))
1459             return false;
1460         }
1461     }
1462
1463   return true;
1464 }
1465
1466 /* Return true if the var whose chain of uses starts at PTR has no
1467    nondebug uses.  */
1468 bool
1469 has_zero_uses_1 (const ssa_use_operand_t *head)
1470 {
1471   const ssa_use_operand_t *ptr;
1472
1473   for (ptr = head->next; ptr != head; ptr = ptr->next)
1474     if (!is_gimple_debug (USE_STMT (ptr)))
1475       return false;
1476
1477   return true;
1478 }
1479
1480 /* Return true if the var whose chain of uses starts at PTR has a
1481    single nondebug use.  Set USE_P and STMT to that single nondebug
1482    use, if so, or to NULL otherwise.  */
1483 bool
1484 single_imm_use_1 (const ssa_use_operand_t *head,
1485                   use_operand_p *use_p, gimple *stmt)
1486 {
1487   ssa_use_operand_t *ptr, *single_use = 0;
1488
1489   for (ptr = head->next; ptr != head; ptr = ptr->next)
1490     if (!is_gimple_debug (USE_STMT (ptr)))
1491       {
1492         if (single_use)
1493           {
1494             single_use = NULL;
1495             break;
1496           }
1497         single_use = ptr;
1498       }
1499
1500   if (use_p)
1501     *use_p = single_use;
1502
1503   if (stmt)
1504     *stmt = single_use ? single_use->loc.stmt : NULL;
1505
1506   return !!single_use;
1507 }
1508
1509 /* Replaces all uses of NAME by VAL.  */
1510
1511 void
1512 replace_uses_by (tree name, tree val)
1513 {
1514   imm_use_iterator imm_iter;
1515   use_operand_p use;
1516   gimple stmt;
1517   edge e;
1518
1519   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1520     {
1521       FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1522         {
1523           replace_exp (use, val);
1524
1525           if (gimple_code (stmt) == GIMPLE_PHI)
1526             {
1527               e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use));
1528               if (e->flags & EDGE_ABNORMAL)
1529                 {
1530                   /* This can only occur for virtual operands, since
1531                      for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1532                      would prevent replacement.  */
1533                   gcc_assert (!is_gimple_reg (name));
1534                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1535                 }
1536             }
1537         }
1538
1539       if (gimple_code (stmt) != GIMPLE_PHI)
1540         {
1541           size_t i;
1542
1543           fold_stmt_inplace (stmt);
1544           if (cfgcleanup_altered_bbs)
1545             bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1546
1547           /* FIXME.  This should go in update_stmt.  */
1548           for (i = 0; i < gimple_num_ops (stmt); i++)
1549             {
1550               tree op = gimple_op (stmt, i);
1551               /* Operands may be empty here.  For example, the labels
1552                  of a GIMPLE_COND are nulled out following the creation
1553                  of the corresponding CFG edges.  */
1554               if (op && TREE_CODE (op) == ADDR_EXPR)
1555                 recompute_tree_invariant_for_addr_expr (op);
1556             }
1557
1558           maybe_clean_or_replace_eh_stmt (stmt, stmt);
1559           update_stmt (stmt);
1560         }
1561     }
1562
1563   gcc_assert (has_zero_uses (name));
1564
1565   /* Also update the trees stored in loop structures.  */
1566   if (current_loops)
1567     {
1568       struct loop *loop;
1569       loop_iterator li;
1570
1571       FOR_EACH_LOOP (li, loop, 0)
1572         {
1573           substitute_in_loop_info (loop, name, val);
1574         }
1575     }
1576 }
1577
1578 /* Merge block B into block A.  */
1579
1580 static void
1581 gimple_merge_blocks (basic_block a, basic_block b)
1582 {
1583   gimple_stmt_iterator last, gsi, psi;
1584   gimple_seq phis = phi_nodes (b);
1585
1586   if (dump_file)
1587     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1588
1589   /* Remove all single-valued PHI nodes from block B of the form
1590      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1591   gsi = gsi_last_bb (a);
1592   for (psi = gsi_start (phis); !gsi_end_p (psi); )
1593     {
1594       gimple phi = gsi_stmt (psi);
1595       tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1596       gimple copy;
1597       bool may_replace_uses = !is_gimple_reg (def)
1598                               || may_propagate_copy (def, use);
1599
1600       /* In case we maintain loop closed ssa form, do not propagate arguments
1601          of loop exit phi nodes.  */
1602       if (current_loops
1603           && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1604           && is_gimple_reg (def)
1605           && TREE_CODE (use) == SSA_NAME
1606           && a->loop_father != b->loop_father)
1607         may_replace_uses = false;
1608
1609       if (!may_replace_uses)
1610         {
1611           gcc_assert (is_gimple_reg (def));
1612
1613           /* Note that just emitting the copies is fine -- there is no problem
1614              with ordering of phi nodes.  This is because A is the single
1615              predecessor of B, therefore results of the phi nodes cannot
1616              appear as arguments of the phi nodes.  */
1617           copy = gimple_build_assign (def, use);
1618           gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1619           remove_phi_node (&psi, false);
1620         }
1621       else
1622         {
1623           /* If we deal with a PHI for virtual operands, we can simply
1624              propagate these without fussing with folding or updating
1625              the stmt.  */
1626           if (!is_gimple_reg (def))
1627             {
1628               imm_use_iterator iter;
1629               use_operand_p use_p;
1630               gimple stmt;
1631
1632               FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1633                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1634                   SET_USE (use_p, use);
1635             }
1636           else
1637             replace_uses_by (def, use);
1638
1639           remove_phi_node (&psi, true);
1640         }
1641     }
1642
1643   /* Ensure that B follows A.  */
1644   move_block_after (b, a);
1645
1646   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1647   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1648
1649   /* Remove labels from B and set gimple_bb to A for other statements.  */
1650   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1651     {
1652       gimple stmt = gsi_stmt (gsi);
1653       if (gimple_code (stmt) == GIMPLE_LABEL)
1654         {
1655           tree label = gimple_label_label (stmt);
1656           int lp_nr;
1657
1658           gsi_remove (&gsi, false);
1659
1660           /* Now that we can thread computed gotos, we might have
1661              a situation where we have a forced label in block B
1662              However, the label at the start of block B might still be
1663              used in other ways (think about the runtime checking for
1664              Fortran assigned gotos).  So we can not just delete the
1665              label.  Instead we move the label to the start of block A.  */
1666           if (FORCED_LABEL (label))
1667             {
1668               gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1669               gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT);
1670             }
1671
1672           lp_nr = EH_LANDING_PAD_NR (label);
1673           if (lp_nr)
1674             {
1675               eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1676               lp->post_landing_pad = NULL;
1677             }
1678         }
1679       else
1680         {
1681           gimple_set_bb (stmt, a);
1682           gsi_next (&gsi);
1683         }
1684     }
1685
1686   /* Merge the sequences.  */
1687   last = gsi_last_bb (a);
1688   gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1689   set_bb_seq (b, NULL);
1690
1691   if (cfgcleanup_altered_bbs)
1692     bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1693 }
1694
1695
1696 /* Return the one of two successors of BB that is not reachable by a
1697    complex edge, if there is one.  Else, return BB.  We use
1698    this in optimizations that use post-dominators for their heuristics,
1699    to catch the cases in C++ where function calls are involved.  */
1700
1701 basic_block
1702 single_noncomplex_succ (basic_block bb)
1703 {
1704   edge e0, e1;
1705   if (EDGE_COUNT (bb->succs) != 2)
1706     return bb;
1707
1708   e0 = EDGE_SUCC (bb, 0);
1709   e1 = EDGE_SUCC (bb, 1);
1710   if (e0->flags & EDGE_COMPLEX)
1711     return e1->dest;
1712   if (e1->flags & EDGE_COMPLEX)
1713     return e0->dest;
1714
1715   return bb;
1716 }
1717
1718
1719 /* Walk the function tree removing unnecessary statements.
1720
1721      * Empty statement nodes are removed
1722
1723      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1724
1725      * Unnecessary COND_EXPRs are removed
1726
1727      * Some unnecessary BIND_EXPRs are removed
1728
1729      * GOTO_EXPRs immediately preceding destination are removed.
1730
1731    Clearly more work could be done.  The trick is doing the analysis
1732    and removal fast enough to be a net improvement in compile times.
1733
1734    Note that when we remove a control structure such as a COND_EXPR
1735    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1736    to ensure we eliminate all the useless code.  */
1737
1738 struct rus_data
1739 {
1740   bool repeat;
1741   bool may_throw;
1742   bool may_branch;
1743   bool has_label;
1744   bool last_was_goto;
1745   gimple_stmt_iterator last_goto_gsi;
1746 };
1747
1748
1749 static void remove_useless_stmts_1 (gimple_stmt_iterator *gsi, struct rus_data *);
1750
1751 /* Given a statement sequence, find the first executable statement with
1752    location information, and warn that it is unreachable.  When searching,
1753    descend into containers in execution order.  */
1754
1755 static bool
1756 remove_useless_stmts_warn_notreached (gimple_seq stmts)
1757 {
1758   gimple_stmt_iterator gsi;
1759
1760   for (gsi = gsi_start (stmts); !gsi_end_p (gsi); gsi_next (&gsi))
1761     {
1762       gimple stmt = gsi_stmt (gsi);
1763
1764       if (gimple_no_warning_p (stmt)) return false;
1765
1766       if (gimple_has_location (stmt))
1767         {
1768           location_t loc = gimple_location (stmt);
1769           if (LOCATION_LINE (loc) > 0)
1770             {
1771               warning_at (loc, OPT_Wunreachable_code, "will never be executed");
1772               return true;
1773             }
1774         }
1775
1776       switch (gimple_code (stmt))
1777         {
1778         /* Unfortunately, we need the CFG now to detect unreachable
1779            branches in a conditional, so conditionals are not handled here.  */
1780
1781         case GIMPLE_TRY:
1782           if (remove_useless_stmts_warn_notreached (gimple_try_eval (stmt)))
1783             return true;
1784           if (remove_useless_stmts_warn_notreached (gimple_try_cleanup (stmt)))
1785             return true;
1786           break;
1787
1788         case GIMPLE_CATCH:
1789           return remove_useless_stmts_warn_notreached (gimple_catch_handler (stmt));
1790
1791         case GIMPLE_EH_FILTER:
1792           return remove_useless_stmts_warn_notreached (gimple_eh_filter_failure (stmt));
1793
1794         case GIMPLE_BIND:
1795           return remove_useless_stmts_warn_notreached (gimple_bind_body (stmt));
1796
1797         default:
1798           break;
1799         }
1800     }
1801
1802   return false;
1803 }
1804
1805 /* Helper for remove_useless_stmts_1.  Handle GIMPLE_COND statements.  */
1806
1807 static void
1808 remove_useless_stmts_cond (gimple_stmt_iterator *gsi, struct rus_data *data)
1809 {
1810   gimple stmt = gsi_stmt (*gsi);
1811
1812   /* The folded result must still be a conditional statement.  */
1813   fold_stmt (gsi);
1814   gcc_assert (gsi_stmt (*gsi) == stmt);
1815
1816   data->may_branch = true;
1817
1818   /* Replace trivial conditionals with gotos. */
1819   if (gimple_cond_true_p (stmt))
1820     {
1821       /* Goto THEN label.  */
1822       tree then_label = gimple_cond_true_label (stmt);
1823
1824       gsi_replace (gsi, gimple_build_goto (then_label), false);
1825       data->last_goto_gsi = *gsi;
1826       data->last_was_goto = true;
1827       data->repeat = true;
1828     }
1829   else if (gimple_cond_false_p (stmt))
1830     {
1831       /* Goto ELSE label.  */
1832       tree else_label = gimple_cond_false_label (stmt);
1833
1834       gsi_replace (gsi, gimple_build_goto (else_label), false);
1835       data->last_goto_gsi = *gsi;
1836       data->last_was_goto = true;
1837       data->repeat = true;
1838     }
1839   else
1840     {
1841       tree then_label = gimple_cond_true_label (stmt);
1842       tree else_label = gimple_cond_false_label (stmt);
1843
1844       if (then_label == else_label)
1845         {
1846           /* Goto common destination.  */
1847           gsi_replace (gsi, gimple_build_goto (then_label), false);
1848           data->last_goto_gsi = *gsi;
1849           data->last_was_goto = true;
1850           data->repeat = true;
1851         }
1852     }
1853
1854   gsi_next (gsi);
1855
1856   data->last_was_goto = false;
1857 }
1858
1859 /* Helper for remove_useless_stmts_1.
1860    Handle the try-finally case for GIMPLE_TRY statements.  */
1861
1862 static void
1863 remove_useless_stmts_tf (gimple_stmt_iterator *gsi, struct rus_data *data)
1864 {
1865   bool save_may_branch, save_may_throw;
1866   bool this_may_branch, this_may_throw;
1867
1868   gimple_seq eval_seq, cleanup_seq;
1869   gimple_stmt_iterator eval_gsi, cleanup_gsi;
1870
1871   gimple stmt = gsi_stmt (*gsi);
1872
1873   /* Collect may_branch and may_throw information for the body only.  */
1874   save_may_branch = data->may_branch;
1875   save_may_throw = data->may_throw;
1876   data->may_branch = false;
1877   data->may_throw = false;
1878   data->last_was_goto = false;
1879
1880   eval_seq = gimple_try_eval (stmt);
1881   eval_gsi = gsi_start (eval_seq);
1882   remove_useless_stmts_1 (&eval_gsi, data);
1883
1884   this_may_branch = data->may_branch;
1885   this_may_throw = data->may_throw;
1886   data->may_branch |= save_may_branch;
1887   data->may_throw |= save_may_throw;
1888   data->last_was_goto = false;
1889
1890   cleanup_seq = gimple_try_cleanup (stmt);
1891   cleanup_gsi = gsi_start (cleanup_seq);
1892   remove_useless_stmts_1 (&cleanup_gsi, data);
1893
1894   /* If the body is empty, then we can emit the FINALLY block without
1895      the enclosing TRY_FINALLY_EXPR.  */
1896   if (gimple_seq_empty_p (eval_seq))
1897     {
1898       gsi_insert_seq_before (gsi, cleanup_seq, GSI_SAME_STMT);
1899       gsi_remove (gsi, false);
1900       data->repeat = true;
1901     }
1902
1903   /* If the handler is empty, then we can emit the TRY block without
1904      the enclosing TRY_FINALLY_EXPR.  */
1905   else if (gimple_seq_empty_p (cleanup_seq))
1906     {
1907       gsi_insert_seq_before (gsi, eval_seq, GSI_SAME_STMT);
1908       gsi_remove (gsi, false);
1909       data->repeat = true;
1910     }
1911
1912   /* If the body neither throws, nor branches, then we can safely
1913      string the TRY and FINALLY blocks together.  */
1914   else if (!this_may_branch && !this_may_throw)
1915     {
1916       gsi_insert_seq_before (gsi, eval_seq, GSI_SAME_STMT);
1917       gsi_insert_seq_before (gsi, cleanup_seq, GSI_SAME_STMT);
1918       gsi_remove (gsi, false);
1919       data->repeat = true;
1920     }
1921   else
1922     gsi_next (gsi);
1923 }
1924
1925 /* Helper for remove_useless_stmts_1.
1926    Handle the try-catch case for GIMPLE_TRY statements.  */
1927
1928 static void
1929 remove_useless_stmts_tc (gimple_stmt_iterator *gsi, struct rus_data *data)
1930 {
1931   bool save_may_throw, this_may_throw;
1932
1933   gimple_seq eval_seq, cleanup_seq, handler_seq, failure_seq;
1934   gimple_stmt_iterator eval_gsi, cleanup_gsi, handler_gsi, failure_gsi;
1935
1936   gimple stmt = gsi_stmt (*gsi);
1937
1938   /* Collect may_throw information for the body only.  */
1939   save_may_throw = data->may_throw;
1940   data->may_throw = false;
1941   data->last_was_goto = false;
1942
1943   eval_seq = gimple_try_eval (stmt);
1944   eval_gsi = gsi_start (eval_seq);
1945   remove_useless_stmts_1 (&eval_gsi, data);
1946
1947   this_may_throw = data->may_throw;
1948   data->may_throw = save_may_throw;
1949
1950   cleanup_seq = gimple_try_cleanup (stmt);
1951
1952   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1953   if (!this_may_throw)
1954     {
1955       if (warn_notreached)
1956         {
1957           remove_useless_stmts_warn_notreached (cleanup_seq);
1958         }
1959       gsi_insert_seq_before (gsi, eval_seq, GSI_SAME_STMT);
1960       gsi_remove (gsi, false);
1961       data->repeat = true;
1962       return;
1963     }
1964
1965   /* Process the catch clause specially.  We may be able to tell that
1966      no exceptions propagate past this point.  */
1967
1968   this_may_throw = true;
1969   cleanup_gsi = gsi_start (cleanup_seq);
1970   stmt = gsi_stmt (cleanup_gsi);
1971   data->last_was_goto = false;
1972
1973   switch (gimple_code (stmt))
1974     {
1975     case GIMPLE_CATCH:
1976       /* If the first element is a catch, they all must be.  */
1977       while (!gsi_end_p (cleanup_gsi))
1978         {
1979           stmt = gsi_stmt (cleanup_gsi);
1980           /* If we catch all exceptions, then the body does not
1981              propagate exceptions past this point.  */
1982           if (gimple_catch_types (stmt) == NULL)
1983             this_may_throw = false;
1984           data->last_was_goto = false;
1985           handler_seq = gimple_catch_handler (stmt);
1986           handler_gsi = gsi_start (handler_seq);
1987           remove_useless_stmts_1 (&handler_gsi, data);
1988           gsi_next (&cleanup_gsi);
1989         }
1990       gsi_next (gsi);
1991       break;
1992
1993     case GIMPLE_EH_FILTER:
1994       if (gimple_eh_filter_types (stmt) == NULL)
1995         this_may_throw = false;
1996       failure_seq = gimple_eh_filter_failure (stmt);
1997       failure_gsi = gsi_start (failure_seq);
1998       remove_useless_stmts_1 (&failure_gsi, data);
1999       gsi_next (gsi);
2000       break;
2001
2002     case GIMPLE_EH_MUST_NOT_THROW:
2003       this_may_throw = false;
2004       break;
2005
2006     default:
2007       /* Otherwise this is a list of cleanup statements.  */
2008       remove_useless_stmts_1 (&cleanup_gsi, data);
2009
2010       /* If the cleanup is empty, then we can emit the TRY block without
2011          the enclosing TRY_CATCH_EXPR.  */
2012       if (gimple_seq_empty_p (cleanup_seq))
2013         {
2014           gsi_insert_seq_before (gsi, eval_seq, GSI_SAME_STMT);
2015           gsi_remove(gsi, false);
2016           data->repeat = true;
2017         }
2018       else
2019         gsi_next (gsi);
2020       break;
2021     }
2022
2023   data->may_throw |= this_may_throw;
2024 }
2025
2026 /* Helper for remove_useless_stmts_1.  Handle GIMPLE_BIND statements.  */
2027
2028 static void
2029 remove_useless_stmts_bind (gimple_stmt_iterator *gsi, struct rus_data *data ATTRIBUTE_UNUSED)
2030 {
2031   tree block;
2032   gimple_seq body_seq, fn_body_seq;
2033   gimple_stmt_iterator body_gsi;
2034
2035   gimple stmt = gsi_stmt (*gsi);
2036
2037   /* First remove anything underneath the BIND_EXPR.  */
2038
2039   body_seq = gimple_bind_body (stmt);
2040   body_gsi = gsi_start (body_seq);
2041   remove_useless_stmts_1 (&body_gsi, data);
2042
2043   /* If the GIMPLE_BIND has no variables, then we can pull everything
2044      up one level and remove the GIMPLE_BIND, unless this is the toplevel
2045      GIMPLE_BIND for the current function or an inlined function.
2046
2047      When this situation occurs we will want to apply this
2048      optimization again.  */
2049   block = gimple_bind_block (stmt);
2050   fn_body_seq = gimple_body (current_function_decl);
2051   if (gimple_bind_vars (stmt) == NULL_TREE
2052       && (gimple_seq_empty_p (fn_body_seq)
2053           || stmt != gimple_seq_first_stmt (fn_body_seq))
2054       && (! block
2055           || ! BLOCK_ABSTRACT_ORIGIN (block)
2056           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
2057               != FUNCTION_DECL)))
2058     {
2059       tree var = NULL_TREE;
2060       /* Even if there are no gimple_bind_vars, there might be other
2061          decls in BLOCK_VARS rendering the GIMPLE_BIND not useless.  */
2062       if (block && !BLOCK_NUM_NONLOCALIZED_VARS (block))
2063         for (var = BLOCK_VARS (block); var; var = TREE_CHAIN (var))
2064           if (TREE_CODE (var) == IMPORTED_DECL)
2065             break;
2066       if (var || (block && BLOCK_NUM_NONLOCALIZED_VARS (block)))
2067         gsi_next (gsi);
2068       else
2069         {
2070           gsi_insert_seq_before (gsi, body_seq, GSI_SAME_STMT);
2071           gsi_remove (gsi, false);
2072           data->repeat = true;
2073         }
2074     }
2075   else
2076     gsi_next (gsi);
2077 }
2078
2079 /* Helper for remove_useless_stmts_1.  Handle GIMPLE_GOTO statements.  */
2080
2081 static void
2082 remove_useless_stmts_goto (gimple_stmt_iterator *gsi, struct rus_data *data)
2083 {
2084   gimple stmt = gsi_stmt (*gsi);
2085
2086   tree dest = gimple_goto_dest (stmt);
2087
2088   data->may_branch = true;
2089   data->last_was_goto = false;
2090
2091   /* Record iterator for last goto expr, so that we can delete it if unnecessary.  */
2092   if (TREE_CODE (dest) == LABEL_DECL)
2093     {
2094       data->last_goto_gsi = *gsi;
2095       data->last_was_goto = true;
2096     }
2097
2098   gsi_next(gsi);
2099 }
2100
2101 /* Helper for remove_useless_stmts_1.  Handle GIMPLE_LABEL statements.  */
2102
2103 static void
2104 remove_useless_stmts_label (gimple_stmt_iterator *gsi, struct rus_data *data)
2105 {
2106   gimple stmt = gsi_stmt (*gsi);
2107
2108   tree label = gimple_label_label (stmt);
2109
2110   data->has_label = true;
2111
2112   /* We do want to jump across non-local label receiver code.  */
2113   if (DECL_NONLOCAL (label))
2114     data->last_was_goto = false;
2115
2116   else if (data->last_was_goto
2117            && gimple_goto_dest (gsi_stmt (data->last_goto_gsi)) == label)
2118     {
2119       /* Replace the preceding GIMPLE_GOTO statement with
2120          a GIMPLE_NOP, which will be subsequently removed.
2121          In this way, we avoid invalidating other iterators
2122          active on the statement sequence.  */
2123       gsi_replace(&data->last_goto_gsi, gimple_build_nop(), false);
2124       data->last_was_goto = false;
2125       data->repeat = true;
2126     }
2127
2128   /* ??? Add something here to delete unused labels.  */
2129
2130   gsi_next (gsi);
2131 }
2132
2133
2134 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
2135
2136 void
2137 notice_special_calls (gimple call)
2138 {
2139   int flags = gimple_call_flags (call);
2140
2141   if (flags & ECF_MAY_BE_ALLOCA)
2142     cfun->calls_alloca = true;
2143   if (flags & ECF_RETURNS_TWICE)
2144     cfun->calls_setjmp = true;
2145 }
2146
2147
2148 /* Clear flags set by notice_special_calls.  Used by dead code removal
2149    to update the flags.  */
2150
2151 void
2152 clear_special_calls (void)
2153 {
2154   cfun->calls_alloca = false;
2155   cfun->calls_setjmp = false;
2156 }
2157
2158 /* Remove useless statements from a statement sequence, and perform
2159    some preliminary simplifications.  */
2160
2161 static void
2162 remove_useless_stmts_1 (gimple_stmt_iterator *gsi, struct rus_data *data)
2163 {
2164   while (!gsi_end_p (*gsi))
2165     {
2166       gimple stmt = gsi_stmt (*gsi);
2167
2168       switch (gimple_code (stmt))
2169         {
2170         case GIMPLE_COND:
2171           remove_useless_stmts_cond (gsi, data);
2172           break;
2173
2174         case GIMPLE_GOTO:
2175           remove_useless_stmts_goto (gsi, data);
2176           break;
2177
2178         case GIMPLE_LABEL:
2179           remove_useless_stmts_label (gsi, data);
2180           break;
2181
2182         case GIMPLE_ASSIGN:
2183           fold_stmt (gsi);
2184           stmt = gsi_stmt (*gsi);
2185           data->last_was_goto = false;
2186           if (stmt_could_throw_p (stmt))
2187             data->may_throw = true;
2188           gsi_next (gsi);
2189           break;
2190
2191         case GIMPLE_ASM:
2192           fold_stmt (gsi);
2193           data->last_was_goto = false;
2194           gsi_next (gsi);
2195           break;
2196
2197         case GIMPLE_CALL:
2198           fold_stmt (gsi);
2199           stmt = gsi_stmt (*gsi);
2200           data->last_was_goto = false;
2201           if (is_gimple_call (stmt))
2202             notice_special_calls (stmt);
2203
2204           /* We used to call update_gimple_call_flags here,
2205              which copied side-effects and nothrows status
2206              from the function decl to the call.  In the new
2207              tuplified GIMPLE, the accessors for this information
2208              always consult the function decl, so this copying
2209              is no longer necessary.  */
2210           if (stmt_could_throw_p (stmt))
2211             data->may_throw = true;
2212           gsi_next (gsi);
2213           break;
2214
2215         case GIMPLE_RETURN:
2216           fold_stmt (gsi);
2217           data->last_was_goto = false;
2218           data->may_branch = true;
2219           gsi_next (gsi);
2220           break;
2221
2222         case GIMPLE_BIND:
2223           remove_useless_stmts_bind (gsi, data);
2224           break;
2225
2226         case GIMPLE_TRY:
2227           if (gimple_try_kind (stmt) == GIMPLE_TRY_CATCH)
2228             remove_useless_stmts_tc (gsi, data);
2229           else if (gimple_try_kind (stmt) == GIMPLE_TRY_FINALLY)
2230             remove_useless_stmts_tf (gsi, data);
2231           else
2232             gcc_unreachable ();
2233           break;
2234
2235         case GIMPLE_CATCH:
2236           gcc_unreachable ();
2237           break;
2238
2239         case GIMPLE_NOP:
2240           gsi_remove (gsi, false);
2241           break;
2242
2243         case GIMPLE_OMP_FOR:
2244           {
2245             gimple_seq pre_body_seq = gimple_omp_for_pre_body (stmt);
2246             gimple_stmt_iterator pre_body_gsi = gsi_start (pre_body_seq);
2247
2248             remove_useless_stmts_1 (&pre_body_gsi, data);
2249             data->last_was_goto = false;
2250           }
2251           /* FALLTHROUGH */
2252         case GIMPLE_OMP_CRITICAL:
2253         case GIMPLE_OMP_CONTINUE:
2254         case GIMPLE_OMP_MASTER:
2255         case GIMPLE_OMP_ORDERED:
2256         case GIMPLE_OMP_SECTION:
2257         case GIMPLE_OMP_SECTIONS:
2258         case GIMPLE_OMP_SINGLE:
2259           {
2260             gimple_seq body_seq = gimple_omp_body (stmt);
2261             gimple_stmt_iterator body_gsi = gsi_start (body_seq);
2262
2263             remove_useless_stmts_1 (&body_gsi, data);
2264             data->last_was_goto = false;
2265             gsi_next (gsi);
2266           }
2267           break;
2268
2269         case GIMPLE_OMP_PARALLEL:
2270         case GIMPLE_OMP_TASK:
2271           {
2272             /* Make sure the outermost GIMPLE_BIND isn't removed
2273                as useless.  */
2274             gimple_seq body_seq = gimple_omp_body (stmt);
2275             gimple bind = gimple_seq_first_stmt (body_seq);
2276             gimple_seq bind_seq = gimple_bind_body (bind);
2277             gimple_stmt_iterator bind_gsi = gsi_start (bind_seq);
2278
2279             remove_useless_stmts_1 (&bind_gsi, data);
2280             data->last_was_goto = false;
2281             gsi_next (gsi);
2282           }
2283           break;
2284
2285         default:
2286           data->last_was_goto = false;
2287           gsi_next (gsi);
2288           break;
2289         }
2290     }
2291 }
2292
2293 /* Walk the function tree, removing useless statements and performing
2294    some preliminary simplifications.  */
2295
2296 static unsigned int
2297 remove_useless_stmts (void)
2298 {
2299   struct rus_data data;
2300
2301   clear_special_calls ();
2302
2303   do
2304     {
2305       gimple_stmt_iterator gsi;
2306
2307       gsi = gsi_start (gimple_body (current_function_decl));
2308       memset (&data, 0, sizeof (data));
2309       remove_useless_stmts_1 (&gsi, &data);
2310     }
2311   while (data.repeat);
2312
2313 #ifdef ENABLE_TYPES_CHECKING
2314   verify_types_in_gimple_seq (gimple_body (current_function_decl));
2315 #endif
2316
2317   return 0;
2318 }
2319
2320
2321 struct gimple_opt_pass pass_remove_useless_stmts =
2322 {
2323  {
2324   GIMPLE_PASS,
2325   "useless",                            /* name */
2326   NULL,                                 /* gate */
2327   remove_useless_stmts,                 /* execute */
2328   NULL,                                 /* sub */
2329   NULL,                                 /* next */
2330   0,                                    /* static_pass_number */
2331   TV_NONE,                              /* tv_id */
2332   PROP_gimple_any,                      /* properties_required */
2333   0,                                    /* properties_provided */
2334   0,                                    /* properties_destroyed */
2335   0,                                    /* todo_flags_start */
2336   TODO_dump_func                        /* todo_flags_finish */
2337  }
2338 };
2339
2340 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
2341
2342 static void
2343 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
2344 {
2345   /* Since this block is no longer reachable, we can just delete all
2346      of its PHI nodes.  */
2347   remove_phi_nodes (bb);
2348
2349   /* Remove edges to BB's successors.  */
2350   while (EDGE_COUNT (bb->succs) > 0)
2351     remove_edge (EDGE_SUCC (bb, 0));
2352 }
2353
2354
2355 /* Remove statements of basic block BB.  */
2356
2357 static void
2358 remove_bb (basic_block bb)
2359 {
2360   gimple_stmt_iterator i;
2361   source_location loc = UNKNOWN_LOCATION;
2362
2363   if (dump_file)
2364     {
2365       fprintf (dump_file, "Removing basic block %d\n", bb->index);
2366       if (dump_flags & TDF_DETAILS)
2367         {
2368           dump_bb (bb, dump_file, 0);
2369           fprintf (dump_file, "\n");
2370         }
2371     }
2372
2373   if (current_loops)
2374     {
2375       struct loop *loop = bb->loop_father;
2376
2377       /* If a loop gets removed, clean up the information associated
2378          with it.  */
2379       if (loop->latch == bb
2380           || loop->header == bb)
2381         free_numbers_of_iterations_estimates_loop (loop);
2382     }
2383
2384   /* Remove all the instructions in the block.  */
2385   if (bb_seq (bb) != NULL)
2386     {
2387       /* Walk backwards so as to get a chance to substitute all
2388          released DEFs into debug stmts.  See
2389          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
2390          details.  */
2391       for (i = gsi_last_bb (bb); !gsi_end_p (i);)
2392         {
2393           gimple stmt = gsi_stmt (i);
2394           if (gimple_code (stmt) == GIMPLE_LABEL
2395               && (FORCED_LABEL (gimple_label_label (stmt))
2396                   || DECL_NONLOCAL (gimple_label_label (stmt))))
2397             {
2398               basic_block new_bb;
2399               gimple_stmt_iterator new_gsi;
2400
2401               /* A non-reachable non-local label may still be referenced.
2402                  But it no longer needs to carry the extra semantics of
2403                  non-locality.  */
2404               if (DECL_NONLOCAL (gimple_label_label (stmt)))
2405                 {
2406                   DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
2407                   FORCED_LABEL (gimple_label_label (stmt)) = 1;
2408                 }
2409
2410               new_bb = bb->prev_bb;
2411               new_gsi = gsi_start_bb (new_bb);
2412               gsi_remove (&i, false);
2413               gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
2414             }
2415           else
2416             {
2417               /* Release SSA definitions if we are in SSA.  Note that we
2418                  may be called when not in SSA.  For example,
2419                  final_cleanup calls this function via
2420                  cleanup_tree_cfg.  */
2421               if (gimple_in_ssa_p (cfun))
2422                 release_defs (stmt);
2423
2424               gsi_remove (&i, true);
2425             }
2426
2427           if (gsi_end_p (i))
2428             i = gsi_last_bb (bb);
2429           else
2430             gsi_prev (&i);
2431
2432           /* Don't warn for removed gotos.  Gotos are often removed due to
2433              jump threading, thus resulting in bogus warnings.  Not great,
2434              since this way we lose warnings for gotos in the original
2435              program that are indeed unreachable.  */
2436           if (gimple_code (stmt) != GIMPLE_GOTO
2437               && gimple_has_location (stmt))
2438             loc = gimple_location (stmt);
2439         }
2440     }
2441
2442   /* If requested, give a warning that the first statement in the
2443      block is unreachable.  We walk statements backwards in the
2444      loop above, so the last statement we process is the first statement
2445      in the block.  */
2446   if (loc > BUILTINS_LOCATION && LOCATION_LINE (loc) > 0)
2447     warning_at (loc, OPT_Wunreachable_code, "will never be executed");
2448
2449   remove_phi_nodes_and_edges_for_unreachable_block (bb);
2450   bb->il.gimple = NULL;
2451 }
2452
2453
2454 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2455    predicate VAL, return the edge that will be taken out of the block.
2456    If VAL does not match a unique edge, NULL is returned.  */
2457
2458 edge
2459 find_taken_edge (basic_block bb, tree val)
2460 {
2461   gimple stmt;
2462
2463   stmt = last_stmt (bb);
2464
2465   gcc_assert (stmt);
2466   gcc_assert (is_ctrl_stmt (stmt));
2467
2468   if (val == NULL)
2469     return NULL;
2470
2471   if (!is_gimple_min_invariant (val))
2472     return NULL;
2473
2474   if (gimple_code (stmt) == GIMPLE_COND)
2475     return find_taken_edge_cond_expr (bb, val);
2476
2477   if (gimple_code (stmt) == GIMPLE_SWITCH)
2478     return find_taken_edge_switch_expr (bb, val);
2479
2480   if (computed_goto_p (stmt))
2481     {
2482       /* Only optimize if the argument is a label, if the argument is
2483          not a label then we can not construct a proper CFG.
2484
2485          It may be the case that we only need to allow the LABEL_REF to
2486          appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
2487          appear inside a LABEL_EXPR just to be safe.  */
2488       if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
2489           && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
2490         return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
2491       return NULL;
2492     }
2493
2494   gcc_unreachable ();
2495 }
2496
2497 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2498    statement, determine which of the outgoing edges will be taken out of the
2499    block.  Return NULL if either edge may be taken.  */
2500
2501 static edge
2502 find_taken_edge_computed_goto (basic_block bb, tree val)
2503 {
2504   basic_block dest;
2505   edge e = NULL;
2506
2507   dest = label_to_block (val);
2508   if (dest)
2509     {
2510       e = find_edge (bb, dest);
2511       gcc_assert (e != NULL);
2512     }
2513
2514   return e;
2515 }
2516
2517 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2518    statement, determine which of the two edges will be taken out of the
2519    block.  Return NULL if either edge may be taken.  */
2520
2521 static edge
2522 find_taken_edge_cond_expr (basic_block bb, tree val)
2523 {
2524   edge true_edge, false_edge;
2525
2526   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2527
2528   gcc_assert (TREE_CODE (val) == INTEGER_CST);
2529   return (integer_zerop (val) ? false_edge : true_edge);
2530 }
2531
2532 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2533    statement, determine which edge will be taken out of the block.  Return
2534    NULL if any edge may be taken.  */
2535
2536 static edge
2537 find_taken_edge_switch_expr (basic_block bb, tree val)
2538 {
2539   basic_block dest_bb;
2540   edge e;
2541   gimple switch_stmt;
2542   tree taken_case;
2543
2544   switch_stmt = last_stmt (bb);
2545   taken_case = find_case_label_for_value (switch_stmt, val);
2546   dest_bb = label_to_block (CASE_LABEL (taken_case));
2547
2548   e = find_edge (bb, dest_bb);
2549   gcc_assert (e);
2550   return e;
2551 }
2552
2553
2554 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
2555    We can make optimal use here of the fact that the case labels are
2556    sorted: We can do a binary search for a case matching VAL.  */
2557
2558 static tree
2559 find_case_label_for_value (gimple switch_stmt, tree val)
2560 {
2561   size_t low, high, n = gimple_switch_num_labels (switch_stmt);
2562   tree default_case = gimple_switch_default_label (switch_stmt);
2563
2564   for (low = 0, high = n; high - low > 1; )
2565     {
2566       size_t i = (high + low) / 2;
2567       tree t = gimple_switch_label (switch_stmt, i);
2568       int cmp;
2569
2570       /* Cache the result of comparing CASE_LOW and val.  */
2571       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2572
2573       if (cmp > 0)
2574         high = i;
2575       else
2576         low = i;
2577
2578       if (CASE_HIGH (t) == NULL)
2579         {
2580           /* A singe-valued case label.  */
2581           if (cmp == 0)
2582             return t;
2583         }
2584       else
2585         {
2586           /* A case range.  We can only handle integer ranges.  */
2587           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2588             return t;
2589         }
2590     }
2591
2592   return default_case;
2593 }
2594
2595
2596 /* Dump a basic block on stderr.  */
2597
2598 void
2599 gimple_debug_bb (basic_block bb)
2600 {
2601   gimple_dump_bb (bb, stderr, 0, TDF_VOPS|TDF_MEMSYMS);
2602 }
2603
2604
2605 /* Dump basic block with index N on stderr.  */
2606
2607 basic_block
2608 gimple_debug_bb_n (int n)
2609 {
2610   gimple_debug_bb (BASIC_BLOCK (n));
2611   return BASIC_BLOCK (n);
2612 }
2613
2614
2615 /* Dump the CFG on stderr.
2616
2617    FLAGS are the same used by the tree dumping functions
2618    (see TDF_* in tree-pass.h).  */
2619
2620 void
2621 gimple_debug_cfg (int flags)
2622 {
2623   gimple_dump_cfg (stderr, flags);
2624 }
2625
2626
2627 /* Dump the program showing basic block boundaries on the given FILE.
2628
2629    FLAGS are the same used by the tree dumping functions (see TDF_* in
2630    tree.h).  */
2631
2632 void
2633 gimple_dump_cfg (FILE *file, int flags)
2634 {
2635   if (flags & TDF_DETAILS)
2636     {
2637       const char *funcname
2638         = lang_hooks.decl_printable_name (current_function_decl, 2);
2639
2640       fputc ('\n', file);
2641       fprintf (file, ";; Function %s\n\n", funcname);
2642       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2643                n_basic_blocks, n_edges, last_basic_block);
2644
2645       brief_dump_cfg (file);
2646       fprintf (file, "\n");
2647     }
2648
2649   if (flags & TDF_STATS)
2650     dump_cfg_stats (file);
2651
2652   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2653 }
2654
2655
2656 /* Dump CFG statistics on FILE.  */
2657
2658 void
2659 dump_cfg_stats (FILE *file)
2660 {
2661   static long max_num_merged_labels = 0;
2662   unsigned long size, total = 0;
2663   long num_edges;
2664   basic_block bb;
2665   const char * const fmt_str   = "%-30s%-13s%12s\n";
2666   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2667   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2668   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2669   const char *funcname
2670     = lang_hooks.decl_printable_name (current_function_decl, 2);
2671
2672
2673   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2674
2675   fprintf (file, "---------------------------------------------------------\n");
2676   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2677   fprintf (file, fmt_str, "", "  instances  ", "used ");
2678   fprintf (file, "---------------------------------------------------------\n");
2679
2680   size = n_basic_blocks * sizeof (struct basic_block_def);
2681   total += size;
2682   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2683            SCALE (size), LABEL (size));
2684
2685   num_edges = 0;
2686   FOR_EACH_BB (bb)
2687     num_edges += EDGE_COUNT (bb->succs);
2688   size = num_edges * sizeof (struct edge_def);
2689   total += size;
2690   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2691
2692   fprintf (file, "---------------------------------------------------------\n");
2693   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2694            LABEL (total));
2695   fprintf (file, "---------------------------------------------------------\n");
2696   fprintf (file, "\n");
2697
2698   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2699     max_num_merged_labels = cfg_stats.num_merged_labels;
2700
2701   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2702            cfg_stats.num_merged_labels, max_num_merged_labels);
2703
2704   fprintf (file, "\n");
2705 }
2706
2707
2708 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2709    linked in the final executable.  */
2710
2711 void
2712 debug_cfg_stats (void)
2713 {
2714   dump_cfg_stats (stderr);
2715 }
2716
2717
2718 /* Dump the flowgraph to a .vcg FILE.  */
2719
2720 static void
2721 gimple_cfg2vcg (FILE *file)
2722 {
2723   edge e;
2724   edge_iterator ei;
2725   basic_block bb;
2726   const char *funcname
2727     = lang_hooks.decl_printable_name (current_function_decl, 2);
2728
2729   /* Write the file header.  */
2730   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2731   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2732   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2733
2734   /* Write blocks and edges.  */
2735   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2736     {
2737       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2738                e->dest->index);
2739
2740       if (e->flags & EDGE_FAKE)
2741         fprintf (file, " linestyle: dotted priority: 10");
2742       else
2743         fprintf (file, " linestyle: solid priority: 100");
2744
2745       fprintf (file, " }\n");
2746     }
2747   fputc ('\n', file);
2748
2749   FOR_EACH_BB (bb)
2750     {
2751       enum gimple_code head_code, end_code;
2752       const char *head_name, *end_name;
2753       int head_line = 0;
2754       int end_line = 0;
2755       gimple first = first_stmt (bb);
2756       gimple last = last_stmt (bb);
2757
2758       if (first)
2759         {
2760           head_code = gimple_code (first);
2761           head_name = gimple_code_name[head_code];
2762           head_line = get_lineno (first);
2763         }
2764       else
2765         head_name = "no-statement";
2766
2767       if (last)
2768         {
2769           end_code = gimple_code (last);
2770           end_name = gimple_code_name[end_code];
2771           end_line = get_lineno (last);
2772         }
2773       else
2774         end_name = "no-statement";
2775
2776       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2777                bb->index, bb->index, head_name, head_line, end_name,
2778                end_line);
2779
2780       FOR_EACH_EDGE (e, ei, bb->succs)
2781         {
2782           if (e->dest == EXIT_BLOCK_PTR)
2783             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2784           else
2785             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2786
2787           if (e->flags & EDGE_FAKE)
2788             fprintf (file, " priority: 10 linestyle: dotted");
2789           else
2790             fprintf (file, " priority: 100 linestyle: solid");
2791
2792           fprintf (file, " }\n");
2793         }
2794
2795       if (bb->next_bb != EXIT_BLOCK_PTR)
2796         fputc ('\n', file);
2797     }
2798
2799   fputs ("}\n\n", file);
2800 }
2801
2802
2803
2804 /*---------------------------------------------------------------------------
2805                              Miscellaneous helpers
2806 ---------------------------------------------------------------------------*/
2807
2808 /* Return true if T represents a stmt that always transfers control.  */
2809
2810 bool
2811 is_ctrl_stmt (gimple t)
2812 {
2813   switch (gimple_code (t))
2814     {
2815     case GIMPLE_COND:
2816     case GIMPLE_SWITCH:
2817     case GIMPLE_GOTO:
2818     case GIMPLE_RETURN:
2819     case GIMPLE_RESX:
2820       return true;
2821     default:
2822       return false;
2823     }
2824 }
2825
2826
2827 /* Return true if T is a statement that may alter the flow of control
2828    (e.g., a call to a non-returning function).  */
2829
2830 bool
2831 is_ctrl_altering_stmt (gimple t)
2832 {
2833   gcc_assert (t);
2834
2835   switch (gimple_code (t))
2836     {
2837     case GIMPLE_CALL:
2838       {
2839         int flags = gimple_call_flags (t);
2840
2841         /* A non-pure/const call alters flow control if the current
2842            function has nonlocal labels.  */
2843         if (!(flags & (ECF_CONST | ECF_PURE)) && cfun->has_nonlocal_label)
2844           return true;
2845
2846         /* A call also alters control flow if it does not return.  */
2847         if (gimple_call_flags (t) & ECF_NORETURN)
2848           return true;
2849       }
2850       break;
2851
2852     case GIMPLE_EH_DISPATCH:
2853       /* EH_DISPATCH branches to the individual catch handlers at
2854          this level of a try or allowed-exceptions region.  It can
2855          fallthru to the next statement as well.  */
2856       return true;
2857
2858     case GIMPLE_ASM:
2859       if (gimple_asm_nlabels (t) > 0)
2860         return true;
2861       break;
2862
2863     CASE_GIMPLE_OMP:
2864       /* OpenMP directives alter control flow.  */
2865       return true;
2866
2867     default:
2868       break;
2869     }
2870
2871   /* If a statement can throw, it alters control flow.  */
2872   return stmt_can_throw_internal (t);
2873 }
2874
2875
2876 /* Return true if T is a simple local goto.  */
2877
2878 bool
2879 simple_goto_p (gimple t)
2880 {
2881   return (gimple_code (t) == GIMPLE_GOTO
2882           && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2883 }
2884
2885
2886 /* Return true if T can make an abnormal transfer of control flow.
2887    Transfers of control flow associated with EH are excluded.  */
2888
2889 bool
2890 stmt_can_make_abnormal_goto (gimple t)
2891 {
2892   if (computed_goto_p (t))
2893     return true;
2894   if (is_gimple_call (t))
2895     return gimple_has_side_effects (t) && cfun->has_nonlocal_label;
2896   return false;
2897 }
2898
2899
2900 /* Return true if STMT should start a new basic block.  PREV_STMT is
2901    the statement preceding STMT.  It is used when STMT is a label or a
2902    case label.  Labels should only start a new basic block if their
2903    previous statement wasn't a label.  Otherwise, sequence of labels
2904    would generate unnecessary basic blocks that only contain a single
2905    label.  */
2906
2907 static inline bool
2908 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2909 {
2910   if (stmt == NULL)
2911     return false;
2912
2913   /* Labels start a new basic block only if the preceding statement
2914      wasn't a label of the same type.  This prevents the creation of
2915      consecutive blocks that have nothing but a single label.  */
2916   if (gimple_code (stmt) == GIMPLE_LABEL)
2917     {
2918       /* Nonlocal and computed GOTO targets always start a new block.  */
2919       if (DECL_NONLOCAL (gimple_label_label (stmt))
2920           || FORCED_LABEL (gimple_label_label (stmt)))
2921         return true;
2922
2923       if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2924         {
2925           if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2926             return true;
2927
2928           cfg_stats.num_merged_labels++;
2929           return false;
2930         }
2931       else
2932         return true;
2933     }
2934
2935   return false;
2936 }
2937
2938
2939 /* Return true if T should end a basic block.  */
2940
2941 bool
2942 stmt_ends_bb_p (gimple t)
2943 {
2944   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2945 }
2946
2947 /* Remove block annotations and other data structures.  */
2948
2949 void
2950 delete_tree_cfg_annotations (void)
2951 {
2952   label_to_block_map = NULL;
2953 }
2954
2955
2956 /* Return the first statement in basic block BB.  */
2957
2958 gimple
2959 first_stmt (basic_block bb)
2960 {
2961   gimple_stmt_iterator i = gsi_start_bb (bb);
2962   gimple stmt = NULL;
2963
2964   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2965     {
2966       gsi_next (&i);
2967       stmt = NULL;
2968     }
2969   return stmt;
2970 }
2971
2972 /* Return the first non-label statement in basic block BB.  */
2973
2974 static gimple
2975 first_non_label_stmt (basic_block bb)
2976 {
2977   gimple_stmt_iterator i = gsi_start_bb (bb);
2978   while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2979     gsi_next (&i);
2980   return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2981 }
2982
2983 /* Return the last statement in basic block BB.  */
2984
2985 gimple
2986 last_stmt (basic_block bb)
2987 {
2988   gimple_stmt_iterator i = gsi_last_bb (bb);
2989   gimple stmt = NULL;
2990
2991   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2992     {
2993       gsi_prev (&i);
2994       stmt = NULL;
2995     }
2996   return stmt;
2997 }
2998
2999 /* Return the last statement of an otherwise empty block.  Return NULL
3000    if the block is totally empty, or if it contains more than one
3001    statement.  */
3002
3003 gimple
3004 last_and_only_stmt (basic_block bb)
3005 {
3006   gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
3007   gimple last, prev;
3008
3009   if (gsi_end_p (i))
3010     return NULL;
3011
3012   last = gsi_stmt (i);
3013   gsi_prev_nondebug (&i);
3014   if (gsi_end_p (i))
3015     return last;
3016
3017   /* Empty statements should no longer appear in the instruction stream.
3018      Everything that might have appeared before should be deleted by
3019      remove_useless_stmts, and the optimizers should just gsi_remove
3020      instead of smashing with build_empty_stmt.
3021
3022      Thus the only thing that should appear here in a block containing
3023      one executable statement is a label.  */
3024   prev = gsi_stmt (i);
3025   if (gimple_code (prev) == GIMPLE_LABEL)
3026     return last;
3027   else
3028     return NULL;
3029 }
3030
3031 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
3032
3033 static void
3034 reinstall_phi_args (edge new_edge, edge old_edge)
3035 {
3036   edge_var_map_vector v;
3037   edge_var_map *vm;
3038   int i;
3039   gimple_stmt_iterator phis;
3040
3041   v = redirect_edge_var_map_vector (old_edge);
3042   if (!v)
3043     return;
3044
3045   for (i = 0, phis = gsi_start_phis (new_edge->dest);
3046        VEC_iterate (edge_var_map, v, i, vm) && !gsi_end_p (phis);
3047        i++, gsi_next (&phis))
3048     {
3049       gimple phi = gsi_stmt (phis);
3050       tree result = redirect_edge_var_map_result (vm);
3051       tree arg = redirect_edge_var_map_def (vm);
3052
3053       gcc_assert (result == gimple_phi_result (phi));
3054
3055       add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
3056     }
3057
3058   redirect_edge_var_map_clear (old_edge);
3059 }
3060
3061 /* Returns the basic block after which the new basic block created
3062    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
3063    near its "logical" location.  This is of most help to humans looking
3064    at debugging dumps.  */
3065
3066 static basic_block
3067 split_edge_bb_loc (edge edge_in)
3068 {
3069   basic_block dest = edge_in->dest;
3070   basic_block dest_prev = dest->prev_bb;
3071
3072   if (dest_prev)
3073     {
3074       edge e = find_edge (dest_prev, dest);
3075       if (e && !(e->flags & EDGE_COMPLEX))
3076         return edge_in->src;
3077     }
3078   return dest_prev;
3079 }
3080
3081 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3082    Abort on abnormal edges.  */
3083
3084 static basic_block
3085 gimple_split_edge (edge edge_in)
3086 {
3087   basic_block new_bb, after_bb, dest;
3088   edge new_edge, e;
3089
3090   /* Abnormal edges cannot be split.  */
3091   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3092
3093   dest = edge_in->dest;
3094
3095   after_bb = split_edge_bb_loc (edge_in);
3096
3097   new_bb = create_empty_bb (after_bb);
3098   new_bb->frequency = EDGE_FREQUENCY (edge_in);
3099   new_bb->count = edge_in->count;
3100   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3101   new_edge->probability = REG_BR_PROB_BASE;
3102   new_edge->count = edge_in->count;
3103
3104   e = redirect_edge_and_branch (edge_in, new_bb);
3105   gcc_assert (e == edge_in);
3106   reinstall_phi_args (new_edge, e);
3107
3108   return new_bb;
3109 }
3110
3111 /* Callback for walk_tree, check that all elements with address taken are
3112    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
3113    inside a PHI node.  */
3114
3115 static tree
3116 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3117 {
3118   tree t = *tp, x;
3119
3120   if (TYPE_P (t))
3121     *walk_subtrees = 0;
3122
3123   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
3124 #define CHECK_OP(N, MSG) \
3125   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
3126        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3127
3128   switch (TREE_CODE (t))
3129     {
3130     case SSA_NAME:
3131       if (SSA_NAME_IN_FREE_LIST (t))
3132         {
3133           error ("SSA name in freelist but still referenced");
3134           return *tp;
3135         }
3136       break;
3137
3138     case INDIRECT_REF:
3139       x = TREE_OPERAND (t, 0);
3140       if (!is_gimple_reg (x) && !is_gimple_min_invariant (x))
3141         {
3142           error ("Indirect reference's operand is not a register or a constant.");
3143           return x;
3144         }
3145       break;
3146
3147     case ASSERT_EXPR:
3148       x = fold (ASSERT_EXPR_COND (t));
3149       if (x == boolean_false_node)
3150         {
3151           error ("ASSERT_EXPR with an always-false condition");
3152           return *tp;
3153         }
3154       break;
3155
3156     case MODIFY_EXPR:
3157       error ("MODIFY_EXPR not expected while having tuples.");
3158       return *tp;
3159
3160     case ADDR_EXPR:
3161       {
3162         bool old_constant;
3163         bool old_side_effects;
3164         bool new_constant;
3165         bool new_side_effects;
3166
3167         gcc_assert (is_gimple_address (t));
3168
3169         old_constant = TREE_CONSTANT (t);
3170         old_side_effects = TREE_SIDE_EFFECTS (t);
3171
3172         recompute_tree_invariant_for_addr_expr (t);
3173         new_side_effects = TREE_SIDE_EFFECTS (t);
3174         new_constant = TREE_CONSTANT (t);
3175
3176         if (old_constant != new_constant)
3177           {
3178             error ("constant not recomputed when ADDR_EXPR changed");
3179             return t;
3180           }
3181         if (old_side_effects != new_side_effects)
3182           {
3183             error ("side effects not recomputed when ADDR_EXPR changed");
3184             return t;
3185           }
3186
3187         /* Skip any references (they will be checked when we recurse down the
3188            tree) and ensure that any variable used as a prefix is marked
3189            addressable.  */
3190         for (x = TREE_OPERAND (t, 0);
3191              handled_component_p (x);
3192              x = TREE_OPERAND (x, 0))
3193           ;
3194
3195         if (!(TREE_CODE (x) == VAR_DECL
3196               || TREE_CODE (x) == PARM_DECL
3197               || TREE_CODE (x) == RESULT_DECL))
3198           return NULL;
3199         if (!TREE_ADDRESSABLE (x))
3200           {
3201             error ("address taken, but ADDRESSABLE bit not set");
3202             return x;
3203           }
3204         if (DECL_GIMPLE_REG_P (x))
3205           {
3206             error ("DECL_GIMPLE_REG_P set on a variable with address taken");
3207             return x;
3208           }
3209
3210         break;
3211       }
3212
3213     case COND_EXPR:
3214       x = COND_EXPR_COND (t);
3215       if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
3216         {
3217           error ("non-integral used in condition");
3218           return x;
3219         }
3220       if (!is_gimple_condexpr (x))
3221         {
3222           error ("invalid conditional operand");
3223           return x;
3224         }
3225       break;
3226
3227     case NON_LVALUE_EXPR:
3228         gcc_unreachable ();
3229
3230     CASE_CONVERT:
3231     case FIX_TRUNC_EXPR:
3232     case FLOAT_EXPR:
3233     case NEGATE_EXPR:
3234     case ABS_EXPR:
3235     case BIT_NOT_EXPR:
3236     case TRUTH_NOT_EXPR:
3237       CHECK_OP (0, "invalid operand to unary operator");
3238       break;
3239
3240     case REALPART_EXPR:
3241     case IMAGPART_EXPR:
3242     case COMPONENT_REF:
3243     case ARRAY_REF:
3244     case ARRAY_RANGE_REF:
3245     case BIT_FIELD_REF:
3246     case VIEW_CONVERT_EXPR:
3247       /* We have a nest of references.  Verify that each of the operands
3248          that determine where to reference is either a constant or a variable,
3249          verify that the base is valid, and then show we've already checked
3250          the subtrees.  */
3251       while (handled_component_p (t))
3252         {
3253           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3254             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
3255           else if (TREE_CODE (t) == ARRAY_REF
3256                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3257             {
3258               CHECK_OP (1, "invalid array index");
3259               if (TREE_OPERAND (t, 2))
3260                 CHECK_OP (2, "invalid array lower bound");
3261               if (TREE_OPERAND (t, 3))
3262                 CHECK_OP (3, "invalid array stride");
3263             }
3264           else if (TREE_CODE (t) == BIT_FIELD_REF)
3265             {
3266               if (!host_integerp (TREE_OPERAND (t, 1), 1)
3267                   || !host_integerp (TREE_OPERAND (t, 2), 1))
3268                 {
3269                   error ("invalid position or size operand to BIT_FIELD_REF");
3270                   return t;
3271                 }
3272               else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
3273                        && (TYPE_PRECISION (TREE_TYPE (t))
3274                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
3275                 {
3276                   error ("integral result type precision does not match "
3277                          "field size of BIT_FIELD_REF");
3278                   return t;
3279                 }
3280               if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
3281                   && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
3282                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
3283                 {
3284                   error ("mode precision of non-integral result does not "
3285                          "match field size of BIT_FIELD_REF");
3286                   return t;
3287                 }
3288             }
3289
3290           t = TREE_OPERAND (t, 0);
3291         }
3292
3293       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
3294         {
3295           error ("invalid reference prefix");
3296           return t;
3297         }
3298       *walk_subtrees = 0;
3299       break;
3300     case PLUS_EXPR:
3301     case MINUS_EXPR:
3302       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
3303          POINTER_PLUS_EXPR. */
3304       if (POINTER_TYPE_P (TREE_TYPE (t)))
3305         {
3306           error ("invalid operand to plus/minus, type is a pointer");
3307           return t;
3308         }
3309       CHECK_OP (0, "invalid operand to binary operator");
3310       CHECK_OP (1, "invalid operand to binary operator");
3311       break;
3312
3313     case POINTER_PLUS_EXPR:
3314       /* Check to make sure the first operand is a pointer or reference type. */
3315       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
3316         {
3317           error ("invalid operand to pointer plus, first operand is not a pointer");
3318           return t;
3319         }
3320       /* Check to make sure the second operand is an integer with type of
3321          sizetype.  */
3322       if (!useless_type_conversion_p (sizetype,
3323                                      TREE_TYPE (TREE_OPERAND (t, 1))))
3324         {
3325           error ("invalid operand to pointer plus, second operand is not an "
3326                  "integer with type of sizetype.");
3327           return t;
3328         }
3329       /* FALLTHROUGH */
3330     case LT_EXPR:
3331     case LE_EXPR:
3332     case GT_EXPR:
3333     case GE_EXPR:
3334     case EQ_EXPR:
3335     case NE_EXPR:
3336     case UNORDERED_EXPR:
3337     case ORDERED_EXPR:
3338     case UNLT_EXPR:
3339     case UNLE_EXPR:
3340     case UNGT_EXPR:
3341     case UNGE_EXPR:
3342     case UNEQ_EXPR:
3343     case LTGT_EXPR:
3344     case MULT_EXPR:
3345     case TRUNC_DIV_EXPR:
3346     case CEIL_DIV_EXPR:
3347     case FLOOR_DIV_EXPR:
3348     case ROUND_DIV_EXPR:
3349     case TRUNC_MOD_EXPR:
3350     case CEIL_MOD_EXPR:
3351     case FLOOR_MOD_EXPR:
3352     case ROUND_MOD_EXPR:
3353     case RDIV_EXPR:
3354     case EXACT_DIV_EXPR:
3355     case MIN_EXPR:
3356     case MAX_EXPR:
3357     case LSHIFT_EXPR:
3358     case RSHIFT_EXPR:
3359     case LROTATE_EXPR:
3360     case RROTATE_EXPR:
3361     case BIT_IOR_EXPR:
3362     case BIT_XOR_EXPR:
3363     case BIT_AND_EXPR:
3364       CHECK_OP (0, "invalid operand to binary operator");
3365       CHECK_OP (1, "invalid operand to binary operator");
3366       break;
3367
3368     case CONSTRUCTOR:
3369       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
3370         *walk_subtrees = 0;
3371       break;
3372
3373     default:
3374       break;
3375     }
3376   return NULL;
3377
3378 #undef CHECK_OP
3379 }
3380
3381
3382 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
3383    Returns true if there is an error, otherwise false.  */
3384
3385 static bool
3386 verify_types_in_gimple_min_lval (tree expr)
3387 {
3388   tree op;
3389
3390   if (is_gimple_id (expr))
3391     return false;
3392
3393   if (!INDIRECT_REF_P (expr)
3394       && TREE_CODE (expr) != TARGET_MEM_REF)
3395     {
3396       error ("invalid expression for min lvalue");
3397       return true;
3398     }
3399
3400   /* TARGET_MEM_REFs are strange beasts.  */
3401   if (TREE_CODE (expr) == TARGET_MEM_REF)
3402     return false;
3403
3404   op = TREE_OPERAND (expr, 0);
3405   if (!is_gimple_val (op))
3406     {
3407       error ("invalid operand in indirect reference");
3408       debug_generic_stmt (op);
3409       return true;
3410     }
3411   if (!useless_type_conversion_p (TREE_TYPE (expr),
3412                                   TREE_TYPE (TREE_TYPE (op))))
3413     {
3414       error ("type mismatch in indirect reference");
3415       debug_generic_stmt (TREE_TYPE (expr));
3416       debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3417       return true;
3418     }
3419
3420   return false;
3421 }
3422
3423 /* Verify if EXPR is a valid GIMPLE reference expression.  If
3424    REQUIRE_LVALUE is true verifies it is an lvalue.  Returns true
3425    if there is an error, otherwise false.  */
3426
3427 static bool
3428 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
3429 {
3430   while (handled_component_p (expr))
3431     {
3432       tree op = TREE_OPERAND (expr, 0);
3433
3434       if (TREE_CODE (expr) == ARRAY_REF
3435           || TREE_CODE (expr) == ARRAY_RANGE_REF)
3436         {
3437           if (!is_gimple_val (TREE_OPERAND (expr, 1))
3438               || (TREE_OPERAND (expr, 2)
3439                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
3440               || (TREE_OPERAND (expr, 3)
3441                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
3442             {
3443               error ("invalid operands to array reference");
3444               debug_generic_stmt (expr);
3445               return true;
3446             }
3447         }
3448
3449       /* Verify if the reference array element types are compatible.  */
3450       if (TREE_CODE (expr) == ARRAY_REF
3451           && !useless_type_conversion_p (TREE_TYPE (expr),
3452                                          TREE_TYPE (TREE_TYPE (op))))
3453         {
3454           error ("type mismatch in array reference");
3455           debug_generic_stmt (TREE_TYPE (expr));
3456           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3457           return true;
3458         }
3459       if (TREE_CODE (expr) == ARRAY_RANGE_REF
3460           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
3461                                          TREE_TYPE (TREE_TYPE (op))))
3462         {
3463           error ("type mismatch in array range reference");
3464           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
3465           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3466           return true;
3467         }
3468
3469       if ((TREE_CODE (expr) == REALPART_EXPR
3470            || TREE_CODE (expr) == IMAGPART_EXPR)
3471           && !useless_type_conversion_p (TREE_TYPE (expr),
3472                                          TREE_TYPE (TREE_TYPE (op))))
3473         {
3474           error ("type mismatch in real/imagpart reference");
3475           debug_generic_stmt (TREE_TYPE (expr));
3476           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3477           return true;
3478         }
3479
3480       if (TREE_CODE (expr) == COMPONENT_REF
3481           && !useless_type_conversion_p (TREE_TYPE (expr),
3482                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
3483         {
3484           error ("type mismatch in component reference");
3485           debug_generic_stmt (TREE_TYPE (expr));
3486           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3487           return true;
3488         }
3489
3490       /* For VIEW_CONVERT_EXPRs which are allowed here, too, there
3491          is nothing to verify.  Gross mismatches at most invoke
3492          undefined behavior.  */
3493       if (TREE_CODE (expr) == VIEW_CONVERT_EXPR
3494           && !handled_component_p (op))
3495         return false;
3496
3497       expr = op;
3498     }
3499
3500   return ((require_lvalue || !is_gimple_min_invariant (expr))
3501           && verify_types_in_gimple_min_lval (expr));
3502 }
3503
3504 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3505    list of pointer-to types that is trivially convertible to DEST.  */
3506
3507 static bool
3508 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3509 {
3510   tree src;
3511
3512   if (!TYPE_POINTER_TO (src_obj))
3513     return true;
3514
3515   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3516     if (useless_type_conversion_p (dest, src))
3517       return true;
3518
3519   return false;
3520 }
3521
3522 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3523    from TYPE2 can be handled by FIXED_CONVERT_EXPR.  */
3524
3525 static bool
3526 valid_fixed_convert_types_p (tree type1, tree type2)
3527 {
3528   return (FIXED_POINT_TYPE_P (type1)
3529           && (INTEGRAL_TYPE_P (type2)
3530               || SCALAR_FLOAT_TYPE_P (type2)
3531               || FIXED_POINT_TYPE_P (type2)));
3532 }
3533
3534 /* Verify the contents of a GIMPLE_CALL STMT.  Returns true when there
3535    is a problem, otherwise false.  */
3536
3537 static bool
3538 verify_gimple_call (gimple stmt)
3539 {
3540   tree fn = gimple_call_fn (stmt);
3541   tree fntype;
3542
3543   if (!POINTER_TYPE_P (TREE_TYPE  (fn))
3544       || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3545           && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE))
3546     {
3547       error ("non-function in gimple call");
3548       return true;
3549     }
3550
3551   if (gimple_call_lhs (stmt)
3552       && !is_gimple_lvalue (gimple_call_lhs (stmt)))
3553     {
3554       error ("invalid LHS in gimple call");
3555       return true;
3556     }
3557
3558   fntype = TREE_TYPE (TREE_TYPE (fn));
3559   if (gimple_call_lhs (stmt)
3560       && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3561                                      TREE_TYPE (fntype))
3562       /* ???  At least C++ misses conversions at assignments from
3563          void * call results.
3564          ???  Java is completely off.  Especially with functions
3565          returning java.lang.Object.
3566          For now simply allow arbitrary pointer type conversions.  */
3567       && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3568            && POINTER_TYPE_P (TREE_TYPE (fntype))))
3569     {
3570       error ("invalid conversion in gimple call");
3571       debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3572       debug_generic_stmt (TREE_TYPE (fntype));
3573       return true;
3574     }
3575
3576   /* If there is a static chain argument, this should not be an indirect
3577      call, and the decl should not have DECL_NO_STATIC_CHAIN set.  */
3578   if (gimple_call_chain (stmt))
3579     {
3580       if (TREE_CODE (fn) != ADDR_EXPR
3581           || TREE_CODE (TREE_OPERAND (fn, 0)) != FUNCTION_DECL)
3582         {
3583           error ("static chain in indirect gimple call");
3584           return true;
3585         }
3586       fn = TREE_OPERAND (fn, 0);
3587
3588       if (DECL_NO_STATIC_CHAIN (fn))
3589         {
3590           error ("static chain with function that doesn't use one");
3591           return true;
3592         }
3593     }
3594
3595   /* ???  The C frontend passes unpromoted arguments in case it
3596      didn't see a function declaration before the call.  So for now
3597      leave the call arguments unverified.  Once we gimplify
3598      unit-at-a-time we have a chance to fix this.  */
3599
3600   return false;
3601 }
3602
3603 /* Verifies the gimple comparison with the result type TYPE and
3604    the operands OP0 and OP1.  */
3605
3606 static bool
3607 verify_gimple_comparison (tree type, tree op0, tree op1)
3608 {
3609   tree op0_type = TREE_TYPE (op0);
3610   tree op1_type = TREE_TYPE (op1);
3611
3612   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3613     {
3614       error ("invalid operands in gimple comparison");
3615       return true;
3616     }
3617
3618   /* For comparisons we do not have the operations type as the
3619      effective type the comparison is carried out in.  Instead
3620      we require that either the first operand is trivially
3621      convertible into the second, or the other way around.
3622      The resulting type of a comparison may be any integral type.
3623      Because we special-case pointers to void we allow
3624      comparisons of pointers with the same mode as well.  */
3625   if ((!useless_type_conversion_p (op0_type, op1_type)
3626        && !useless_type_conversion_p (op1_type, op0_type)
3627        && (!POINTER_TYPE_P (op0_type)
3628            || !POINTER_TYPE_P (op1_type)
3629            || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3630       || !INTEGRAL_TYPE_P (type))
3631     {
3632       error ("type mismatch in comparison expression");
3633       debug_generic_expr (type);
3634       debug_generic_expr (op0_type);
3635       debug_generic_expr (op1_type);
3636       return true;
3637     }
3638
3639   return false;
3640 }
3641
3642 /* Verify a gimple assignment statement STMT with an unary rhs.
3643    Returns true if anything is wrong.  */
3644
3645 static bool
3646 verify_gimple_assign_unary (gimple stmt)
3647 {
3648   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3649   tree lhs = gimple_assign_lhs (stmt);
3650   tree lhs_type = TREE_TYPE (lhs);
3651   tree rhs1 = gimple_assign_rhs1 (stmt);
3652   tree rhs1_type = TREE_TYPE (rhs1);
3653
3654   if (!is_gimple_reg (lhs)
3655       && !(optimize == 0
3656            && TREE_CODE (lhs_type) == COMPLEX_TYPE))
3657     {
3658       error ("non-register as LHS of unary operation");
3659       return true;
3660     }
3661
3662   if (!is_gimple_val (rhs1))
3663     {
3664       error ("invalid operand in unary operation");
3665       return true;
3666     }
3667
3668   /* First handle conversions.  */
3669   switch (rhs_code)
3670     {
3671     CASE_CONVERT:
3672       {
3673         /* Allow conversions between integral types and pointers only if
3674            there is no sign or zero extension involved.
3675            For targets were the precision of sizetype doesn't match that
3676            of pointers we need to allow arbitrary conversions from and
3677            to sizetype.  */
3678         if ((POINTER_TYPE_P (lhs_type)
3679              && INTEGRAL_TYPE_P (rhs1_type)
3680              && (TYPE_PRECISION (lhs_type) >= TYPE_PRECISION (rhs1_type)
3681                  || rhs1_type == sizetype))
3682             || (POINTER_TYPE_P (rhs1_type)
3683                 && INTEGRAL_TYPE_P (lhs_type)
3684                 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3685                     || lhs_type == sizetype)))
3686           return false;
3687
3688         /* Allow conversion from integer to offset type and vice versa.  */
3689         if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3690              && TREE_CODE (rhs1_type) == INTEGER_TYPE)
3691             || (TREE_CODE (lhs_type) == INTEGER_TYPE
3692                 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3693           return false;
3694
3695         /* Otherwise assert we are converting between types of the
3696            same kind.  */
3697         if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3698           {
3699             error ("invalid types in nop conversion");
3700             debug_generic_expr (lhs_type);
3701             debug_generic_expr (rhs1_type);
3702             return true;
3703           }
3704
3705         return false;
3706       }
3707
3708     case FIXED_CONVERT_EXPR:
3709       {
3710         if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3711             && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3712           {
3713             error ("invalid types in fixed-point conversion");
3714             debug_generic_expr (lhs_type);
3715             debug_generic_expr (rhs1_type);
3716             return true;
3717           }
3718
3719         return false;
3720       }
3721
3722     case FLOAT_EXPR:
3723       {
3724         if (!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3725           {
3726             error ("invalid types in conversion to floating point");
3727             debug_generic_expr (lhs_type);
3728             debug_generic_expr (rhs1_type);
3729             return true;
3730           }
3731
3732         return false;
3733       }
3734
3735     case FIX_TRUNC_EXPR:
3736       {
3737         if (!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3738           {
3739             error ("invalid types in conversion to integer");
3740             debug_generic_expr (lhs_type);
3741             debug_generic_expr (rhs1_type);
3742             return true;
3743           }
3744
3745         return false;
3746       }
3747
3748     case VEC_UNPACK_HI_EXPR:
3749     case VEC_UNPACK_LO_EXPR:
3750     case REDUC_MAX_EXPR:
3751     case REDUC_MIN_EXPR:
3752     case REDUC_PLUS_EXPR:
3753     case VEC_UNPACK_FLOAT_HI_EXPR:
3754     case VEC_UNPACK_FLOAT_LO_EXPR:
3755       /* FIXME.  */
3756       return false;
3757
3758     case TRUTH_NOT_EXPR:
3759     case NEGATE_EXPR:
3760     case ABS_EXPR:
3761     case BIT_NOT_EXPR:
3762     case PAREN_EXPR:
3763     case NON_LVALUE_EXPR:
3764     case CONJ_EXPR:
3765       break;
3766
3767     default:
3768       gcc_unreachable ();
3769     }
3770
3771   /* For the remaining codes assert there is no conversion involved.  */
3772   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3773     {
3774       error ("non-trivial conversion in unary operation");
3775       debug_generic_expr (lhs_type);
3776       debug_generic_expr (rhs1_type);
3777       return true;
3778     }
3779
3780   return false;
3781 }
3782
3783 /* Verify a gimple assignment statement STMT with a binary rhs.
3784    Returns true if anything is wrong.  */
3785
3786 static bool
3787 verify_gimple_assign_binary (gimple stmt)
3788 {
3789   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3790   tree lhs = gimple_assign_lhs (stmt);
3791   tree lhs_type = TREE_TYPE (lhs);
3792   tree rhs1 = gimple_assign_rhs1 (stmt);
3793   tree rhs1_type = TREE_TYPE (rhs1);
3794   tree rhs2 = gimple_assign_rhs2 (stmt);
3795   tree rhs2_type = TREE_TYPE (rhs2);
3796
3797   if (!is_gimple_reg (lhs)
3798       && !(optimize == 0
3799            && TREE_CODE (lhs_type) == COMPLEX_TYPE))
3800     {
3801       error ("non-register as LHS of binary operation");
3802       return true;
3803     }
3804
3805   if (!is_gimple_val (rhs1)
3806       || !is_gimple_val (rhs2))
3807     {
3808       error ("invalid operands in binary operation");
3809       return true;
3810     }
3811
3812   /* First handle operations that involve different types.  */
3813   switch (rhs_code)
3814     {
3815     case COMPLEX_EXPR:
3816       {
3817         if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3818             || !(INTEGRAL_TYPE_P (rhs1_type)
3819                  || SCALAR_FLOAT_TYPE_P (rhs1_type))
3820             || !(INTEGRAL_TYPE_P (rhs2_type)
3821                  || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3822           {
3823             error ("type mismatch in complex expression");
3824             debug_generic_expr (lhs_type);
3825             debug_generic_expr (rhs1_type);
3826             debug_generic_expr (rhs2_type);
3827             return true;
3828           }
3829
3830         return false;
3831       }
3832
3833     case LSHIFT_EXPR:
3834     case RSHIFT_EXPR:
3835     case LROTATE_EXPR:
3836     case RROTATE_EXPR:
3837       {
3838         /* Shifts and rotates are ok on integral types, fixed point
3839            types and integer vector types.  */
3840         if ((!INTEGRAL_TYPE_P (rhs1_type)
3841              && !FIXED_POINT_TYPE_P (rhs1_type)
3842              && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3843                   && TREE_CODE (TREE_TYPE (rhs1_type)) == INTEGER_TYPE))
3844             || (!INTEGRAL_TYPE_P (rhs2_type)
3845                 /* Vector shifts of vectors are also ok.  */
3846                 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3847                      && TREE_CODE (TREE_TYPE (rhs1_type)) == INTEGER_TYPE
3848                      && TREE_CODE (rhs2_type) == VECTOR_TYPE
3849                      && TREE_CODE (TREE_TYPE (rhs2_type)) == INTEGER_TYPE))
3850             || !useless_type_conversion_p (lhs_type, rhs1_type))
3851           {
3852             error ("type mismatch in shift expression");
3853             debug_generic_expr (lhs_type);
3854             debug_generic_expr (rhs1_type);
3855             debug_generic_expr (rhs2_type);
3856             return true;
3857           }
3858
3859         return false;
3860       }
3861
3862     case VEC_LSHIFT_EXPR:
3863     case VEC_RSHIFT_EXPR:
3864       {
3865         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3866             || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3867                  || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3868                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3869             || (!INTEGRAL_TYPE_P (rhs2_type)
3870                 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3871                     || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3872             || !useless_type_conversion_p (lhs_type, rhs1_type))
3873           {
3874             error ("type mismatch in vector shift expression");
3875             debug_generic_expr (lhs_type);
3876             debug_generic_expr (rhs1_type);
3877             debug_generic_expr (rhs2_type);
3878             return true;
3879           }
3880         /* For shifting a vector of floating point components we
3881            only allow shifting by a constant multiple of the element size.  */
3882         if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type))
3883             && (TREE_CODE (rhs2) != INTEGER_CST
3884                 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3885                                            TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3886           {
3887             error ("non-element sized vector shift of floating point vector");
3888             return true;
3889           }
3890
3891         return false;
3892       }
3893
3894     case PLUS_EXPR:
3895       {
3896         /* We use regular PLUS_EXPR for vectors.
3897            ???  This just makes the checker happy and may not be what is
3898            intended.  */
3899         if (TREE_CODE (lhs_type) == VECTOR_TYPE
3900             && POINTER_TYPE_P (TREE_TYPE (lhs_type)))
3901           {
3902             if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3903                 || TREE_CODE (rhs2_type) != VECTOR_TYPE)
3904               {
3905                 error ("invalid non-vector operands to vector valued plus");
3906                 return true;
3907               }
3908             lhs_type = TREE_TYPE (lhs_type);
3909             rhs1_type = TREE_TYPE (rhs1_type);
3910             rhs2_type = TREE_TYPE (rhs2_type);
3911             /* PLUS_EXPR is commutative, so we might end up canonicalizing
3912                the pointer to 2nd place.  */
3913             if (POINTER_TYPE_P (rhs2_type))
3914               {
3915                 tree tem = rhs1_type;
3916                 rhs1_type = rhs2_type;
3917                 rhs2_type = tem;
3918               }
3919             goto do_pointer_plus_expr_check;
3920           }
3921       }
3922     /* Fallthru.  */
3923     case MINUS_EXPR:
3924       {
3925         if (POINTER_TYPE_P (lhs_type)
3926             || POINTER_TYPE_P (rhs1_type)
3927             || POINTER_TYPE_P (rhs2_type))
3928           {
3929             error ("invalid (pointer) operands to plus/minus");
3930             return true;
3931           }
3932
3933         /* Continue with generic binary expression handling.  */
3934         break;
3935       }
3936
3937     case POINTER_PLUS_EXPR:
3938       {
3939 do_pointer_plus_expr_check:
3940         if (!POINTER_TYPE_P (rhs1_type)
3941             || !useless_type_conversion_p (lhs_type, rhs1_type)
3942             || !useless_type_conversion_p (sizetype, rhs2_type))
3943           {
3944             error ("type mismatch in pointer plus expression");
3945             debug_generic_stmt (lhs_type);
3946             debug_generic_stmt (rhs1_type);
3947             debug_generic_stmt (rhs2_type);
3948             return true;
3949           }
3950
3951         return false;
3952       }
3953
3954     case TRUTH_ANDIF_EXPR:
3955     case TRUTH_ORIF_EXPR:
3956       gcc_unreachable ();
3957
3958     case TRUTH_AND_EXPR:
3959     case TRUTH_OR_EXPR:
3960     case TRUTH_XOR_EXPR:
3961       {
3962         /* We allow any kind of integral typed argument and result.  */
3963         if (!INTEGRAL_TYPE_P (rhs1_type)
3964             || !INTEGRAL_TYPE_P (rhs2_type)
3965             || !INTEGRAL_TYPE_P (lhs_type))
3966           {
3967             error ("type mismatch in binary truth expression");
3968             debug_generic_expr (lhs_type);
3969             debug_generic_expr (rhs1_type);
3970             debug_generic_expr (rhs2_type);
3971             return true;
3972           }
3973
3974         return false;
3975       }
3976
3977     case LT_EXPR:
3978     case LE_EXPR:
3979     case GT_EXPR:
3980     case GE_EXPR:
3981     case EQ_EXPR:
3982     case NE_EXPR:
3983     case UNORDERED_EXPR:
3984     case ORDERED_EXPR:
3985     case UNLT_EXPR:
3986     case UNLE_EXPR:
3987     case UNGT_EXPR:
3988     case UNGE_EXPR:
3989     case UNEQ_EXPR:
3990     case LTGT_EXPR:
3991       /* Comparisons are also binary, but the result type is not
3992          connected to the operand types.  */
3993       return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3994
3995     case WIDEN_SUM_EXPR:
3996     case WIDEN_MULT_EXPR:
3997     case VEC_WIDEN_MULT_HI_EXPR:
3998     case VEC_WIDEN_MULT_LO_EXPR:
3999     case VEC_PACK_TRUNC_EXPR:
4000     case VEC_PACK_SAT_EXPR:
4001     case VEC_PACK_FIX_TRUNC_EXPR:
4002     case VEC_EXTRACT_EVEN_EXPR:
4003     case VEC_EXTRACT_ODD_EXPR:
4004     case VEC_INTERLEAVE_HIGH_EXPR:
4005     case VEC_INTERLEAVE_LOW_EXPR:
4006       /* FIXME.  */
4007       return false;
4008
4009     case MULT_EXPR:
4010     case TRUNC_DIV_EXPR:
4011     case CEIL_DIV_EXPR:
4012     case FLOOR_DIV_EXPR:
4013     case ROUND_DIV_EXPR:
4014     case TRUNC_MOD_EXPR:
4015     case CEIL_MOD_EXPR:
4016     case FLOOR_MOD_EXPR:
4017     case ROUND_MOD_EXPR:
4018     case RDIV_EXPR:
4019     case EXACT_DIV_EXPR:
4020     case MIN_EXPR:
4021     case MAX_EXPR:
4022     case BIT_IOR_EXPR:
4023     case BIT_XOR_EXPR:
4024     case BIT_AND_EXPR:
4025       /* Continue with generic binary expression handling.  */
4026       break;
4027
4028     default:
4029       gcc_unreachable ();
4030     }
4031
4032   if (!useless_type_conversion_p (lhs_type, rhs1_type)
4033       || !useless_type_conversion_p (lhs_type, rhs2_type))
4034     {
4035       error ("type mismatch in binary expression");
4036       debug_generic_stmt (lhs_type);
4037       debug_generic_stmt (rhs1_type);
4038       debug_generic_stmt (rhs2_type);
4039       return true;
4040     }
4041
4042   return false;
4043 }
4044
4045 /* Verify a gimple assignment statement STMT with a single rhs.
4046    Returns true if anything is wrong.  */
4047
4048 static bool
4049 verify_gimple_assign_single (gimple stmt)
4050 {
4051   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
4052   tree lhs = gimple_assign_lhs (stmt);
4053   tree lhs_type = TREE_TYPE (lhs);
4054   tree rhs1 = gimple_assign_rhs1 (stmt);
4055   tree rhs1_type = TREE_TYPE (rhs1);
4056   bool res = false;
4057
4058   if (!useless_type_conversion_p (lhs_type, rhs1_type))
4059     {
4060       error ("non-trivial conversion at assignment");
4061       debug_generic_expr (lhs_type);
4062       debug_generic_expr (rhs1_type);
4063       return true;
4064     }
4065
4066   if (handled_component_p (lhs))
4067     res |= verify_types_in_gimple_reference (lhs, true);
4068
4069   /* Special codes we cannot handle via their class.  */
4070   switch (rhs_code)
4071     {
4072     case ADDR_EXPR:
4073       {
4074         tree op = TREE_OPERAND (rhs1, 0);
4075         if (!is_gimple_addressable (op))
4076           {
4077             error ("invalid operand in unary expression");
4078             return true;
4079           }
4080
4081         if (!types_compatible_p (TREE_TYPE (op), TREE_TYPE (TREE_TYPE (rhs1)))
4082             && !one_pointer_to_useless_type_conversion_p (TREE_TYPE (rhs1),
4083                                                           TREE_TYPE (op)))
4084           {
4085             error ("type mismatch in address expression");
4086             debug_generic_stmt (TREE_TYPE (rhs1));
4087             debug_generic_stmt (TREE_TYPE (op));
4088             return true;
4089           }
4090
4091         return verify_types_in_gimple_reference (op, true);
4092       }
4093
4094     /* tcc_reference  */
4095     case COMPONENT_REF:
4096     case BIT_FIELD_REF:
4097     case INDIRECT_REF:
4098     case ALIGN_INDIRECT_REF:
4099     case MISALIGNED_INDIRECT_REF:
4100     case ARRAY_REF:
4101     case ARRAY_RANGE_REF:
4102     case VIEW_CONVERT_EXPR:
4103     case REALPART_EXPR:
4104     case IMAGPART_EXPR:
4105     case TARGET_MEM_REF:
4106       if (!is_gimple_reg (lhs)
4107           && is_gimple_reg_type (TREE_TYPE (lhs)))
4108         {
4109           error ("invalid rhs for gimple memory store");
4110           debug_generic_stmt (lhs);
4111           debug_generic_stmt (rhs1);
4112           return true;
4113         }
4114       return res || verify_types_in_gimple_reference (rhs1, false);
4115
4116     /* tcc_constant  */
4117     case SSA_NAME:
4118     case INTEGER_CST:
4119     case REAL_CST:
4120     case FIXED_CST:
4121     case COMPLEX_CST:
4122     case VECTOR_CST:
4123     case STRING_CST:
4124       return res;
4125
4126     /* tcc_declaration  */
4127     case CONST_DECL:
4128       return res;
4129     case VAR_DECL:
4130     case PARM_DECL:
4131       if (!is_gimple_reg (lhs)
4132           && !is_gimple_reg (rhs1)
4133           && is_gimple_reg_type (TREE_TYPE (lhs)))
4134         {
4135           error ("invalid rhs for gimple memory store");
4136           debug_generic_stmt (lhs);
4137           debug_generic_stmt (rhs1);
4138           return true;
4139         }
4140       return res;
4141
4142     case COND_EXPR:
4143     case CONSTRUCTOR:
4144     case OBJ_TYPE_REF:
4145     case ASSERT_EXPR:
4146     case WITH_SIZE_EXPR:
4147     case POLYNOMIAL_CHREC:
4148     case DOT_PROD_EXPR:
4149     case VEC_COND_EXPR:
4150     case REALIGN_LOAD_EXPR:
4151       /* FIXME.  */
4152       return res;
4153
4154     default:;
4155     }
4156
4157   return res;
4158 }
4159
4160 /* Verify the contents of a GIMPLE_ASSIGN STMT.  Returns true when there
4161    is a problem, otherwise false.  */
4162
4163 static bool
4164 verify_gimple_assign (gimple stmt)
4165 {
4166   switch (gimple_assign_rhs_class (stmt))
4167     {
4168     case GIMPLE_SINGLE_RHS:
4169       return verify_gimple_assign_single (stmt);
4170
4171     case GIMPLE_UNARY_RHS:
4172       return verify_gimple_assign_unary (stmt);
4173
4174     case GIMPLE_BINARY_RHS:
4175       return verify_gimple_assign_binary (stmt);
4176
4177     default:
4178       gcc_unreachable ();
4179     }
4180 }
4181
4182 /* Verify the contents of a GIMPLE_RETURN STMT.  Returns true when there
4183    is a problem, otherwise false.  */
4184
4185 static bool
4186 verify_gimple_return (gimple stmt)
4187 {
4188   tree op = gimple_return_retval (stmt);
4189   tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
4190
4191   /* We cannot test for present return values as we do not fix up missing
4192      return values from the original source.  */
4193   if (op == NULL)
4194     return false;
4195
4196   if (!is_gimple_val (op)
4197       && TREE_CODE (op) != RESULT_DECL)
4198     {
4199       error ("invalid operand in return statement");
4200       debug_generic_stmt (op);
4201       return true;
4202     }
4203
4204   if (!useless_type_conversion_p (restype, TREE_TYPE (op))
4205       /* ???  With C++ we can have the situation that the result
4206          decl is a reference type while the return type is an aggregate.  */
4207       && !(TREE_CODE (op) == RESULT_DECL
4208            && TREE_CODE (TREE_TYPE (op)) == REFERENCE_TYPE
4209            && useless_type_conversion_p (restype, TREE_TYPE (TREE_TYPE (op)))))
4210     {
4211       error ("invalid conversion in return statement");
4212       debug_generic_stmt (restype);
4213       debug_generic_stmt (TREE_TYPE (op));
4214       return true;
4215     }
4216
4217   return false;
4218 }
4219
4220
4221 /* Verify the contents of a GIMPLE_GOTO STMT.  Returns true when there
4222    is a problem, otherwise false.  */
4223
4224 static bool
4225 verify_gimple_goto (gimple stmt)
4226 {
4227   tree dest = gimple_goto_dest (stmt);
4228
4229   /* ???  We have two canonical forms of direct goto destinations, a
4230      bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL.  */
4231   if (TREE_CODE (dest) != LABEL_DECL
4232       && (!is_gimple_val (dest)
4233           || !POINTER_TYPE_P (TREE_TYPE (dest))))
4234     {
4235       error ("goto destination is neither a label nor a pointer");
4236       return true;
4237     }
4238
4239   return false;
4240 }
4241
4242 /* Verify the contents of a GIMPLE_SWITCH STMT.  Returns true when there
4243    is a problem, otherwise false.  */
4244
4245 static bool
4246 verify_gimple_switch (gimple stmt)
4247 {
4248   if (!is_gimple_val (gimple_switch_index (stmt)))
4249     {
4250       error ("invalid operand to switch statement");
4251       debug_generic_stmt (gimple_switch_index (stmt));
4252       return true;
4253     }
4254
4255   return false;
4256 }
4257
4258
4259 /* Verify the contents of a GIMPLE_PHI.  Returns true if there is a problem,
4260    and false otherwise.  */
4261
4262 static bool
4263 verify_gimple_phi (gimple stmt)
4264 {
4265   tree type = TREE_TYPE (gimple_phi_result (stmt));
4266   unsigned i;
4267
4268   if (TREE_CODE (gimple_phi_result (stmt)) != SSA_NAME)
4269     {
4270       error ("Invalid PHI result");
4271       return true;
4272     }
4273
4274   for (i = 0; i < gimple_phi_num_args (stmt); i++)
4275     {
4276       tree arg = gimple_phi_arg_def (stmt, i);
4277       if ((is_gimple_reg (gimple_phi_result (stmt))
4278            && !is_gimple_val (arg))
4279           || (!is_gimple_reg (gimple_phi_result (stmt))
4280               && !is_gimple_addressable (arg)))
4281         {
4282           error ("Invalid PHI argument");
4283           debug_generic_stmt (arg);
4284           return true;
4285         }
4286       if (!useless_type_conversion_p (type, TREE_TYPE (arg)))
4287         {
4288           error ("Incompatible types in PHI argument %u", i);
4289           debug_generic_stmt (type);
4290           debug_generic_stmt (TREE_TYPE (arg));
4291           return true;
4292         }
4293     }
4294
4295   return false;
4296 }
4297
4298
4299 /* Verify a gimple debug statement STMT.
4300    Returns true if anything is wrong.  */
4301
4302 static bool
4303 verify_gimple_debug (gimple stmt ATTRIBUTE_UNUSED)
4304 {
4305   /* There isn't much that could be wrong in a gimple debug stmt.  A
4306      gimple debug bind stmt, for example, maps a tree, that's usually
4307      a VAR_DECL or a PARM_DECL, but that could also be some scalarized
4308      component or member of an aggregate type, to another tree, that
4309      can be an arbitrary expression.  These stmts expand into debug
4310      insns, and are converted to debug notes by var-tracking.c.  */
4311   return false;
4312 }
4313
4314
4315 /* Verify the GIMPLE statement STMT.  Returns true if there is an
4316    error, otherwise false.  */
4317
4318 static bool
4319 verify_types_in_gimple_stmt (gimple stmt)
4320 {
4321   switch (gimple_code (stmt))
4322     {
4323     case GIMPLE_ASSIGN:
4324       return verify_gimple_assign (stmt);
4325
4326     case GIMPLE_LABEL:
4327       return TREE_CODE (gimple_label_label (stmt)) != LABEL_DECL;
4328
4329     case GIMPLE_CALL:
4330       return verify_gimple_call (stmt);
4331
4332     case GIMPLE_COND:
4333       return verify_gimple_comparison (boolean_type_node,
4334                                        gimple_cond_lhs (stmt),
4335                                        gimple_cond_rhs (stmt));
4336
4337     case GIMPLE_GOTO:
4338       return verify_gimple_goto (stmt);
4339
4340     case GIMPLE_SWITCH:
4341       return verify_gimple_switch (stmt);
4342
4343     case GIMPLE_RETURN:
4344       return verify_gimple_return (stmt);
4345
4346     case GIMPLE_ASM:
4347       return false;
4348
4349     case GIMPLE_PHI:
4350       return verify_gimple_phi (stmt);
4351
4352     /* Tuples that do not have tree operands.  */
4353     case GIMPLE_NOP:
4354     case GIMPLE_PREDICT:
4355     case GIMPLE_RESX:
4356     case GIMPLE_EH_DISPATCH:
4357       return false;
4358
4359     CASE_GIMPLE_OMP:
4360       /* OpenMP directives are validated by the FE and never operated
4361          on by the optimizers.  Furthermore, GIMPLE_OMP_FOR may contain
4362          non-gimple expressions when the main index variable has had
4363          its address taken.  This does not affect the loop itself
4364          because the header of an GIMPLE_OMP_FOR is merely used to determine
4365          how to setup the parallel iteration.  */
4366       return false;
4367
4368     case GIMPLE_DEBUG:
4369       return verify_gimple_debug (stmt);
4370
4371     default:
4372       gcc_unreachable ();
4373     }
4374 }
4375
4376 /* Verify the GIMPLE statements inside the sequence STMTS.  */
4377
4378 static bool
4379 verify_types_in_gimple_seq_2 (gimple_seq stmts)
4380 {
4381   gimple_stmt_iterator ittr;
4382   bool err = false;
4383
4384   for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
4385     {
4386       gimple stmt = gsi_stmt (ittr);
4387
4388       switch (gimple_code (stmt))
4389         {
4390         case GIMPLE_BIND:
4391           err |= verify_types_in_gimple_seq_2 (gimple_bind_body (stmt));
4392           break;
4393
4394         case GIMPLE_TRY:
4395           err |= verify_types_in_gimple_seq_2 (gimple_try_eval (stmt));
4396           err |= verify_types_in_gimple_seq_2 (gimple_try_cleanup (stmt));
4397           break;
4398
4399         case GIMPLE_EH_FILTER:
4400           err |= verify_types_in_gimple_seq_2 (gimple_eh_filter_failure (stmt));
4401           break;
4402
4403         case GIMPLE_CATCH:
4404           err |= verify_types_in_gimple_seq_2 (gimple_catch_handler (stmt));
4405           break;
4406
4407         default:
4408           {
4409             bool err2 = verify_types_in_gimple_stmt (stmt);
4410             if (err2)
4411               debug_gimple_stmt (stmt);
4412             err |= err2;
4413           }
4414         }
4415     }
4416
4417   return err;
4418 }
4419
4420
4421 /* Verify the GIMPLE statements inside the statement list STMTS.  */
4422
4423 void
4424 verify_types_in_gimple_seq (gimple_seq stmts)
4425 {
4426   if (verify_types_in_gimple_seq_2 (stmts))
4427     internal_error ("verify_gimple failed");
4428 }
4429
4430
4431 /* Verify STMT, return true if STMT is not in GIMPLE form.
4432    TODO: Implement type checking.  */
4433
4434 static bool
4435 verify_stmt (gimple_stmt_iterator *gsi)
4436 {
4437   tree addr;
4438   struct walk_stmt_info wi;
4439   bool last_in_block = gsi_one_before_end_p (*gsi);
4440   gimple stmt = gsi_stmt (*gsi);
4441   int lp_nr;
4442
4443   if (is_gimple_omp (stmt))
4444     {
4445       /* OpenMP directives are validated by the FE and never operated
4446          on by the optimizers.  Furthermore, GIMPLE_OMP_FOR may contain
4447          non-gimple expressions when the main index variable has had
4448          its address taken.  This does not affect the loop itself
4449          because the header of an GIMPLE_OMP_FOR is merely used to determine
4450          how to setup the parallel iteration.  */
4451       return false;
4452     }
4453
4454   /* FIXME.  The C frontend passes unpromoted arguments in case it
4455      didn't see a function declaration before the call.  */
4456   if (is_gimple_call (stmt))
4457     {
4458       tree decl;
4459
4460       if (!is_gimple_call_addr (gimple_call_fn (stmt)))
4461         {
4462           error ("invalid function in call statement");
4463           return true;
4464         }
4465
4466       decl = gimple_call_fndecl (stmt);
4467       if (decl
4468           && TREE_CODE (decl) == FUNCTION_DECL
4469           && DECL_LOOPING_CONST_OR_PURE_P (decl)
4470           && (!DECL_PURE_P (decl))
4471           && (!TREE_READONLY (decl)))
4472         {
4473           error ("invalid pure const state for function");
4474           return true;
4475         }
4476     }
4477
4478   if (is_gimple_debug (stmt))
4479     return false;
4480
4481   memset (&wi, 0, sizeof (wi));
4482   addr = walk_gimple_op (gsi_stmt (*gsi), verify_expr, &wi);
4483   if (addr)
4484     {
4485       debug_generic_expr (addr);
4486       inform (gimple_location (gsi_stmt (*gsi)), "in statement");
4487       debug_gimple_stmt (stmt);
4488       return true;
4489     }
4490
4491   /* If the statement is marked as part of an EH region, then it is
4492      expected that the statement could throw.  Verify that when we
4493      have optimizations that simplify statements such that we prove
4494      that they cannot throw, that we update other data structures
4495      to match.  */
4496   lp_nr = lookup_stmt_eh_lp (stmt);
4497   if (lp_nr != 0)
4498     {
4499       if (!stmt_could_throw_p (stmt))
4500         {
4501           /* During IPA passes, ipa-pure-const sets nothrow flags on calls
4502              and they are updated on statements only after fixup_cfg
4503              is executed at beggining of expansion stage.  */
4504           if (cgraph_state != CGRAPH_STATE_IPA_SSA)
4505             {
4506               error ("statement marked for throw, but doesn%'t");
4507               goto fail;
4508             }
4509         }
4510       else if (lp_nr > 0 && !last_in_block && stmt_can_throw_internal (stmt))
4511         {
4512           error ("statement marked for throw in middle of block");
4513           goto fail;
4514         }
4515     }
4516
4517   return false;
4518
4519  fail:
4520   debug_gimple_stmt (stmt);
4521   return true;
4522 }
4523
4524
4525 /* Return true when the T can be shared.  */
4526
4527 static bool
4528 tree_node_can_be_shared (tree t)
4529 {
4530   if (IS_TYPE_OR_DECL_P (t)
4531       || is_gimple_min_invariant (t)
4532       || TREE_CODE (t) == SSA_NAME
4533       || t == error_mark_node
4534       || TREE_CODE (t) == IDENTIFIER_NODE)
4535     return true;
4536
4537   if (TREE_CODE (t) == CASE_LABEL_EXPR)
4538     return true;
4539
4540   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4541            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4542          || TREE_CODE (t) == COMPONENT_REF
4543          || TREE_CODE (t) == REALPART_EXPR
4544          || TREE_CODE (t) == IMAGPART_EXPR)
4545     t = TREE_OPERAND (t, 0);
4546
4547   if (DECL_P (t))
4548     return true;
4549
4550   return false;
4551 }
4552
4553
4554 /* Called via walk_gimple_stmt.  Verify tree sharing.  */
4555
4556 static tree
4557 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4558 {
4559   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4560   struct pointer_set_t *visited = (struct pointer_set_t *) wi->info;
4561
4562   if (tree_node_can_be_shared (*tp))
4563     {
4564       *walk_subtrees = false;
4565       return NULL;
4566     }
4567
4568   if (pointer_set_insert (visited, *tp))
4569     return *tp;
4570
4571   return NULL;
4572 }
4573
4574
4575 static bool eh_error_found;
4576 static int
4577 verify_eh_throw_stmt_node (void **slot, void *data)
4578 {
4579   struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4580   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4581
4582   if (!pointer_set_contains (visited, node->stmt))
4583     {
4584       error ("Dead STMT in EH table");
4585       debug_gimple_stmt (node->stmt);
4586       eh_error_found = true;
4587     }
4588   return 1;
4589 }
4590
4591
4592 /* Verify the GIMPLE statements in every basic block.  */
4593
4594 void
4595 verify_stmts (void)
4596 {
4597   basic_block bb;
4598   gimple_stmt_iterator gsi;
4599   bool err = false;
4600   struct pointer_set_t *visited, *visited_stmts;
4601   tree addr;
4602   struct walk_stmt_info wi;
4603
4604   timevar_push (TV_TREE_STMT_VERIFY);
4605   visited = pointer_set_create ();
4606   visited_stmts = pointer_set_create ();
4607
4608   memset (&wi, 0, sizeof (wi));
4609   wi.info = (void *) visited;
4610
4611   FOR_EACH_BB (bb)
4612     {
4613       gimple phi;
4614       size_t i;
4615
4616       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4617         {
4618           phi = gsi_stmt (gsi);
4619           pointer_set_insert (visited_stmts, phi);
4620           if (gimple_bb (phi) != bb)
4621             {
4622               error ("gimple_bb (phi) is set to a wrong basic block");
4623               err |= true;
4624             }
4625
4626           for (i = 0; i < gimple_phi_num_args (phi); i++)
4627             {
4628               tree t = gimple_phi_arg_def (phi, i);
4629               tree addr;
4630
4631               if (!t)
4632                 {
4633                   error ("missing PHI def");
4634                   debug_gimple_stmt (phi);
4635                   err |= true;
4636                   continue;
4637                 }
4638               /* Addressable variables do have SSA_NAMEs but they
4639                  are not considered gimple values.  */
4640               else if (TREE_CODE (t) != SSA_NAME
4641                        && TREE_CODE (t) != FUNCTION_DECL
4642                        && !is_gimple_min_invariant (t))
4643                 {
4644                   error ("PHI argument is not a GIMPLE value");
4645                   debug_gimple_stmt (phi);
4646                   debug_generic_expr (t);
4647                   err |= true;
4648                 }
4649
4650               addr = walk_tree (&t, verify_node_sharing, visited, NULL);
4651               if (addr)
4652                 {
4653                   error ("incorrect sharing of tree nodes");
4654                   debug_gimple_stmt (phi);
4655                   debug_generic_expr (addr);
4656                   err |= true;
4657                 }
4658             }
4659
4660 #ifdef ENABLE_TYPES_CHECKING
4661           if (verify_gimple_phi (phi))
4662             {
4663               debug_gimple_stmt (phi);
4664               err |= true;
4665             }
4666 #endif
4667         }
4668
4669       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
4670         {
4671           gimple stmt = gsi_stmt (gsi);
4672
4673           if (gimple_code (stmt) == GIMPLE_WITH_CLEANUP_EXPR
4674               || gimple_code (stmt) == GIMPLE_BIND)
4675             {
4676               error ("invalid GIMPLE statement");
4677               debug_gimple_stmt (stmt);
4678               err |= true;
4679             }
4680
4681           pointer_set_insert (visited_stmts, stmt);
4682
4683           if (gimple_bb (stmt) != bb)
4684             {
4685               error ("gimple_bb (stmt) is set to a wrong basic block");
4686               debug_gimple_stmt (stmt);
4687               err |= true;
4688             }
4689
4690           if (gimple_code (stmt) == GIMPLE_LABEL)
4691             {
4692               tree decl = gimple_label_label (stmt);
4693               int uid = LABEL_DECL_UID (decl);
4694
4695               if (uid == -1
4696                   || VEC_index (basic_block, label_to_block_map, uid) != bb)
4697                 {
4698                   error ("incorrect entry in label_to_block_map");
4699                   err |= true;
4700                 }
4701
4702               uid = EH_LANDING_PAD_NR (decl);
4703               if (uid)
4704                 {
4705                   eh_landing_pad lp = get_eh_landing_pad_from_number (uid);
4706                   if (decl != lp->post_landing_pad)
4707                     {
4708                       error ("incorrect setting of landing pad number");
4709                       err |= true;
4710                     }
4711                 }
4712             }
4713
4714           err |= verify_stmt (&gsi);
4715
4716 #ifdef ENABLE_TYPES_CHECKING
4717           if (verify_types_in_gimple_stmt (gsi_stmt (gsi)))
4718             {
4719               debug_gimple_stmt (stmt);
4720               err |= true;
4721             }
4722 #endif
4723           addr = walk_gimple_op (gsi_stmt (gsi), verify_node_sharing, &wi);
4724           if (addr)
4725             {
4726               error ("incorrect sharing of tree nodes");
4727               debug_gimple_stmt (stmt);
4728               debug_generic_expr (addr);
4729               err |= true;
4730             }
4731           gsi_next (&gsi);
4732         }
4733     }
4734
4735   eh_error_found = false;
4736   if (get_eh_throw_stmt_table (cfun))
4737     htab_traverse (get_eh_throw_stmt_table (cfun),
4738                    verify_eh_throw_stmt_node,
4739                    visited_stmts);
4740
4741   if (err | eh_error_found)
4742     internal_error ("verify_stmts failed");
4743
4744   pointer_set_destroy (visited);
4745   pointer_set_destroy (visited_stmts);
4746   verify_histograms ();
4747   timevar_pop (TV_TREE_STMT_VERIFY);
4748 }
4749
4750
4751 /* Verifies that the flow information is OK.  */
4752
4753 static int
4754 gimple_verify_flow_info (void)
4755 {
4756   int err = 0;
4757   basic_block bb;
4758   gimple_stmt_iterator gsi;
4759   gimple stmt;
4760   edge e;
4761   edge_iterator ei;
4762
4763   if (ENTRY_BLOCK_PTR->il.gimple)
4764     {
4765       error ("ENTRY_BLOCK has IL associated with it");
4766       err = 1;
4767     }
4768
4769   if (EXIT_BLOCK_PTR->il.gimple)
4770     {
4771       error ("EXIT_BLOCK has IL associated with it");
4772       err = 1;
4773     }
4774
4775   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4776     if (e->flags & EDGE_FALLTHRU)
4777       {
4778         error ("fallthru to exit from bb %d", e->src->index);
4779         err = 1;
4780       }
4781
4782   FOR_EACH_BB (bb)
4783     {
4784       bool found_ctrl_stmt = false;
4785
4786       stmt = NULL;
4787
4788       /* Skip labels on the start of basic block.  */
4789       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4790         {
4791           tree label;
4792           gimple prev_stmt = stmt;
4793
4794           stmt = gsi_stmt (gsi);
4795
4796           if (gimple_code (stmt) != GIMPLE_LABEL)
4797             break;
4798
4799           label = gimple_label_label (stmt);
4800           if (prev_stmt && DECL_NONLOCAL (label))
4801             {
4802               error ("nonlocal label ");
4803               print_generic_expr (stderr, label, 0);
4804               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4805                        bb->index);
4806               err = 1;
4807             }
4808
4809           if (label_to_block (label) != bb)
4810             {
4811               error ("label ");
4812               print_generic_expr (stderr, label, 0);
4813               fprintf (stderr, " to block does not match in bb %d",
4814                        bb->index);
4815               err = 1;
4816             }
4817
4818           if (decl_function_context (label) != current_function_decl)
4819             {
4820               error ("label ");
4821               print_generic_expr (stderr, label, 0);
4822               fprintf (stderr, " has incorrect context in bb %d",
4823                        bb->index);
4824               err = 1;
4825             }
4826         }
4827
4828       /* Verify that body of basic block BB is free of control flow.  */
4829       for (; !gsi_end_p (gsi); gsi_next (&gsi))
4830         {
4831           gimple stmt = gsi_stmt (gsi);
4832
4833           if (found_ctrl_stmt)
4834             {
4835               error ("control flow in the middle of basic block %d",
4836                      bb->index);
4837               err = 1;
4838             }
4839
4840           if (stmt_ends_bb_p (stmt))
4841             found_ctrl_stmt = true;
4842
4843           if (gimple_code (stmt) == GIMPLE_LABEL)
4844             {
4845               error ("label ");
4846               print_generic_expr (stderr, gimple_label_label (stmt), 0);
4847               fprintf (stderr, " in the middle of basic block %d", bb->index);
4848               err = 1;
4849             }
4850         }
4851
4852       gsi = gsi_last_bb (bb);
4853       if (gsi_end_p (gsi))
4854         continue;
4855
4856       stmt = gsi_stmt (gsi);
4857
4858       if (gimple_code (stmt) == GIMPLE_LABEL)
4859         continue;
4860
4861       err |= verify_eh_edges (stmt);
4862
4863       if (is_ctrl_stmt (stmt))
4864         {
4865           FOR_EACH_EDGE (e, ei, bb->succs)
4866             if (e->flags & EDGE_FALLTHRU)
4867               {
4868                 error ("fallthru edge after a control statement in bb %d",
4869                        bb->index);
4870                 err = 1;
4871               }
4872         }
4873
4874       if (gimple_code (stmt) != GIMPLE_COND)
4875         {
4876           /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4877              after anything else but if statement.  */
4878           FOR_EACH_EDGE (e, ei, bb->succs)
4879             if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4880               {
4881                 error ("true/false edge after a non-GIMPLE_COND in bb %d",
4882                        bb->index);
4883                 err = 1;
4884               }
4885         }
4886
4887       switch (gimple_code (stmt))
4888         {
4889         case GIMPLE_COND:
4890           {
4891             edge true_edge;
4892             edge false_edge;
4893
4894             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4895
4896             if (!true_edge
4897                 || !false_edge
4898                 || !(true_edge->flags & EDGE_TRUE_VALUE)
4899                 || !(false_edge->flags & EDGE_FALSE_VALUE)
4900                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4901                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4902                 || EDGE_COUNT (bb->succs) >= 3)
4903               {
4904                 error ("wrong outgoing edge flags at end of bb %d",
4905                        bb->index);
4906                 err = 1;
4907               }
4908           }
4909           break;
4910
4911         case GIMPLE_GOTO:
4912           if (simple_goto_p (stmt))
4913             {
4914               error ("explicit goto at end of bb %d", bb->index);
4915               err = 1;
4916             }
4917           else
4918             {
4919               /* FIXME.  We should double check that the labels in the
4920                  destination blocks have their address taken.  */
4921               FOR_EACH_EDGE (e, ei, bb->succs)
4922                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4923                                  | EDGE_FALSE_VALUE))
4924                     || !(e->flags & EDGE_ABNORMAL))
4925                   {
4926                     error ("wrong outgoing edge flags at end of bb %d",
4927                            bb->index);
4928                     err = 1;
4929                   }
4930             }
4931           break;
4932
4933         case GIMPLE_RETURN:
4934           if (!single_succ_p (bb)
4935               || (single_succ_edge (bb)->flags
4936                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
4937                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4938             {
4939               error ("wrong outgoing edge flags at end of bb %d", bb->index);
4940               err = 1;
4941             }
4942           if (single_succ (bb) != EXIT_BLOCK_PTR)
4943             {
4944               error ("return edge does not point to exit in bb %d",
4945                      bb->index);
4946               err = 1;
4947             }
4948           break;
4949
4950         case GIMPLE_SWITCH:
4951           {
4952             tree prev;
4953             edge e;
4954             size_t i, n;
4955
4956             n = gimple_switch_num_labels (stmt);
4957
4958             /* Mark all the destination basic blocks.  */
4959             for (i = 0; i < n; ++i)
4960               {
4961                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4962                 basic_block label_bb = label_to_block (lab);
4963                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4964                 label_bb->aux = (void *)1;
4965               }
4966
4967             /* Verify that the case labels are sorted.  */
4968             prev = gimple_switch_label (stmt, 0);
4969             for (i = 1; i < n; ++i)
4970               {
4971                 tree c = gimple_switch_label (stmt, i);
4972                 if (!CASE_LOW (c))
4973                   {
4974                     error ("found default case not at the start of "
4975                            "case vector");
4976                     err = 1;
4977                     continue;
4978                   }
4979                 if (CASE_LOW (prev)
4980                     && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4981                   {
4982                     error ("case labels not sorted: ");
4983                     print_generic_expr (stderr, prev, 0);
4984                     fprintf (stderr," is greater than ");
4985                     print_generic_expr (stderr, c, 0);
4986                     fprintf (stderr," but comes before it.\n");
4987                     err = 1;
4988                   }
4989                 prev = c;
4990               }
4991             /* VRP will remove the default case if it can prove it will
4992                never be executed.  So do not verify there always exists
4993                a default case here.  */
4994
4995             FOR_EACH_EDGE (e, ei, bb->succs)
4996               {
4997                 if (!e->dest->aux)
4998                   {
4999                     error ("extra outgoing edge %d->%d",
5000                            bb->index, e->dest->index);
5001                     err = 1;
5002                   }
5003
5004                 e->dest->aux = (void *)2;
5005                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
5006                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
5007                   {
5008                     error ("wrong outgoing edge flags at end of bb %d",
5009                            bb->index);
5010                     err = 1;
5011                   }
5012               }
5013
5014             /* Check that we have all of them.  */
5015             for (i = 0; i < n; ++i)
5016               {
5017                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
5018                 basic_block label_bb = label_to_block (lab);
5019
5020                 if (label_bb->aux != (void *)2)
5021                   {
5022                     error ("missing edge %i->%i", bb->index, label_bb->index);
5023                     err = 1;
5024                   }
5025               }
5026
5027             FOR_EACH_EDGE (e, ei, bb->succs)
5028               e->dest->aux = (void *)0;
5029           }
5030           break;
5031
5032         case GIMPLE_EH_DISPATCH:
5033           err |= verify_eh_dispatch_edge (stmt);
5034           break;
5035
5036         default:
5037           break;
5038         }
5039     }
5040
5041   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
5042     verify_dominators (CDI_DOMINATORS);
5043
5044   return err;
5045 }
5046
5047
5048 /* Updates phi nodes after creating a forwarder block joined
5049    by edge FALLTHRU.  */
5050
5051 static void
5052 gimple_make_forwarder_block (edge fallthru)
5053 {
5054   edge e;
5055   edge_iterator ei;
5056   basic_block dummy, bb;
5057   tree var;
5058   gimple_stmt_iterator gsi;
5059
5060   dummy = fallthru->src;
5061   bb = fallthru->dest;
5062
5063   if (single_pred_p (bb))
5064     return;
5065
5066   /* If we redirected a branch we must create new PHI nodes at the
5067      start of BB.  */
5068   for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
5069     {
5070       gimple phi, new_phi;
5071
5072       phi = gsi_stmt (gsi);
5073       var = gimple_phi_result (phi);
5074       new_phi = create_phi_node (var, bb);
5075       SSA_NAME_DEF_STMT (var) = new_phi;
5076       gimple_phi_set_result (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
5077       add_phi_arg (new_phi, gimple_phi_result (phi), fallthru,
5078                    UNKNOWN_LOCATION);
5079     }
5080
5081   /* Add the arguments we have stored on edges.  */
5082   FOR_EACH_EDGE (e, ei, bb->preds)
5083     {
5084       if (e == fallthru)
5085         continue;
5086
5087       flush_pending_stmts (e);
5088     }
5089 }
5090
5091
5092 /* Return a non-special label in the head of basic block BLOCK.
5093    Create one if it doesn't exist.  */
5094
5095 tree
5096 gimple_block_label (basic_block bb)
5097 {
5098   gimple_stmt_iterator i, s = gsi_start_bb (bb);
5099   bool first = true;
5100   tree label;
5101   gimple stmt;
5102
5103   for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
5104     {
5105       stmt = gsi_stmt (i);
5106       if (gimple_code (stmt) != GIMPLE_LABEL)
5107         break;
5108       label = gimple_label_label (stmt);
5109       if (!DECL_NONLOCAL (label))
5110         {
5111           if (!first)
5112             gsi_move_before (&i, &s);
5113           return label;
5114         }
5115     }
5116
5117   label = create_artificial_label (UNKNOWN_LOCATION);
5118   stmt = gimple_build_label (label);
5119   gsi_insert_before (&s, stmt, GSI_NEW_STMT);
5120   return label;
5121 }
5122
5123
5124 /* Attempt to perform edge redirection by replacing a possibly complex
5125    jump instruction by a goto or by removing the jump completely.
5126    This can apply only if all edges now point to the same block.  The
5127    parameters and return values are equivalent to
5128    redirect_edge_and_branch.  */
5129
5130 static edge
5131 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
5132 {
5133   basic_block src = e->src;
5134   gimple_stmt_iterator i;
5135   gimple stmt;
5136
5137   /* We can replace or remove a complex jump only when we have exactly
5138      two edges.  */
5139   if (EDGE_COUNT (src->succs) != 2
5140       /* Verify that all targets will be TARGET.  Specifically, the
5141          edge that is not E must also go to TARGET.  */
5142       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
5143     return NULL;
5144
5145   i = gsi_last_bb (src);
5146   if (gsi_end_p (i))
5147     return NULL;
5148
5149   stmt = gsi_stmt (i);
5150
5151   if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
5152     {
5153       gsi_remove (&i, true);
5154       e = ssa_redirect_edge (e, target);
5155       e->flags = EDGE_FALLTHRU;
5156       return e;
5157     }
5158
5159   return NULL;
5160 }
5161
5162
5163 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
5164    edge representing the redirected branch.  */
5165
5166 static edge
5167 gimple_redirect_edge_and_branch (edge e, basic_block dest)
5168 {
5169   basic_block bb = e->src;
5170   gimple_stmt_iterator gsi;
5171   edge ret;
5172   gimple stmt;
5173
5174   if (e->flags & EDGE_ABNORMAL)
5175     return NULL;
5176
5177   if (e->dest == dest)
5178     return NULL;
5179
5180   if (e->flags & EDGE_EH)
5181     return redirect_eh_edge (e, dest);
5182
5183   if (e->src != ENTRY_BLOCK_PTR)
5184     {
5185       ret = gimple_try_redirect_by_replacing_jump (e, dest);
5186       if (ret)
5187         return ret;
5188     }
5189
5190   gsi = gsi_last_bb (bb);
5191   stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
5192
5193   switch (stmt ? gimple_code (stmt) : GIMPLE_ERROR_MARK)
5194     {
5195     case GIMPLE_COND:
5196       /* For COND_EXPR, we only need to redirect the edge.  */
5197       break;
5198
5199     case GIMPLE_GOTO:
5200       /* No non-abnormal edges should lead from a non-simple goto, and
5201          simple ones should be represented implicitly.  */
5202       gcc_unreachable ();
5203
5204     case GIMPLE_SWITCH:
5205       {
5206         tree label = gimple_block_label (dest);
5207         tree cases = get_cases_for_edge (e, stmt);
5208
5209         /* If we have a list of cases associated with E, then use it
5210            as it's a lot faster than walking the entire case vector.  */
5211         if (cases)
5212           {
5213             edge e2 = find_edge (e->src, dest);
5214             tree last, first;
5215
5216             first = cases;
5217             while (cases)
5218               {
5219                 last = cases;
5220                 CASE_LABEL (cases) = label;
5221                 cases = TREE_CHAIN (cases);
5222               }
5223
5224             /* If there was already an edge in the CFG, then we need
5225                to move all the cases associated with E to E2.  */
5226             if (e2)
5227               {
5228                 tree cases2 = get_cases_for_edge (e2, stmt);
5229
5230                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
5231                 TREE_CHAIN (cases2) = first;
5232               }
5233           }
5234         else
5235           {
5236             size_t i, n = gimple_switch_num_labels (stmt);
5237
5238             for (i = 0; i < n; i++)
5239               {
5240                 tree elt = gimple_switch_label (stmt, i);
5241                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
5242                   CASE_LABEL (elt) = label;
5243               }
5244           }
5245       }
5246       break;
5247
5248     case GIMPLE_ASM:
5249       {
5250         int i, n = gimple_asm_nlabels (stmt);
5251         tree label = gimple_block_label (dest);
5252
5253         for (i = 0; i < n; ++i)
5254           {
5255             tree cons = gimple_asm_label_op (stmt, i);
5256             if (label_to_block (TREE_VALUE (cons)) == e->dest)
5257               TREE_VALUE (cons) = label;
5258           }
5259       }
5260       break;
5261
5262     case GIMPLE_RETURN:
5263       gsi_remove (&gsi, true);
5264       e->flags |= EDGE_FALLTHRU;
5265       break;
5266
5267     case GIMPLE_OMP_RETURN:
5268     case GIMPLE_OMP_CONTINUE:
5269     case GIMPLE_OMP_SECTIONS_SWITCH:
5270     case GIMPLE_OMP_FOR:
5271       /* The edges from OMP constructs can be simply redirected.  */
5272       break;
5273
5274     case GIMPLE_EH_DISPATCH:
5275       if (!(e->flags & EDGE_FALLTHRU))
5276         redirect_eh_dispatch_edge (stmt, e, dest);
5277       break;
5278
5279     default:
5280       /* Otherwise it must be a fallthru edge, and we don't need to
5281          do anything besides redirecting it.  */
5282       gcc_assert (e->flags & EDGE_FALLTHRU);
5283       break;
5284     }
5285
5286   /* Update/insert PHI nodes as necessary.  */
5287
5288   /* Now update the edges in the CFG.  */
5289   e = ssa_redirect_edge (e, dest);
5290
5291   return e;
5292 }
5293
5294 /* Returns true if it is possible to remove edge E by redirecting
5295    it to the destination of the other edge from E->src.  */
5296
5297 static bool
5298 gimple_can_remove_branch_p (const_edge e)
5299 {
5300   if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
5301     return false;
5302
5303   return true;
5304 }
5305
5306 /* Simple wrapper, as we can always redirect fallthru edges.  */
5307
5308 static basic_block
5309 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
5310 {
5311   e = gimple_redirect_edge_and_branch (e, dest);
5312   gcc_assert (e);
5313
5314   return NULL;
5315 }
5316
5317
5318 /* Splits basic block BB after statement STMT (but at least after the
5319    labels).  If STMT is NULL, BB is split just after the labels.  */
5320
5321 static basic_block
5322 gimple_split_block (basic_block bb, void *stmt)
5323 {
5324   gimple_stmt_iterator gsi;
5325   gimple_stmt_iterator gsi_tgt;
5326   gimple act;
5327   gimple_seq list;
5328   basic_block new_bb;
5329   edge e;
5330   edge_iterator ei;
5331
5332   new_bb = create_empty_bb (bb);
5333
5334   /* Redirect the outgoing edges.  */
5335   new_bb->succs = bb->succs;
5336   bb->succs = NULL;
5337   FOR_EACH_EDGE (e, ei, new_bb->succs)
5338     e->src = new_bb;
5339
5340   if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
5341     stmt = NULL;
5342
5343   /* Move everything from GSI to the new basic block.  */
5344   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5345     {
5346       act = gsi_stmt (gsi);
5347       if (gimple_code (act) == GIMPLE_LABEL)
5348         continue;
5349
5350       if (!stmt)
5351         break;
5352
5353       if (stmt == act)
5354         {
5355           gsi_next (&gsi);
5356           break;
5357         }
5358     }
5359
5360   if (gsi_end_p (gsi))
5361     return new_bb;
5362
5363   /* Split the statement list - avoid re-creating new containers as this
5364      brings ugly quadratic memory consumption in the inliner.
5365      (We are still quadratic since we need to update stmt BB pointers,
5366      sadly.)  */
5367   list = gsi_split_seq_before (&gsi);
5368   set_bb_seq (new_bb, list);
5369   for (gsi_tgt = gsi_start (list);
5370        !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
5371     gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
5372
5373   return new_bb;
5374 }
5375
5376
5377 /* Moves basic block BB after block AFTER.  */
5378
5379 static bool
5380 gimple_move_block_after (basic_block bb, basic_block after)
5381 {
5382   if (bb->prev_bb == after)
5383     return true;
5384
5385   unlink_block (bb);
5386   link_block (bb, after);
5387
5388   return true;
5389 }
5390
5391
5392 /* Return true if basic_block can be duplicated.  */
5393
5394 static bool
5395 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5396 {
5397   return true;
5398 }
5399
5400 /* Create a duplicate of the basic block BB.  NOTE: This does not
5401    preserve SSA form.  */
5402
5403 static basic_block
5404 gimple_duplicate_bb (basic_block bb)
5405 {
5406   basic_block new_bb;
5407   gimple_stmt_iterator gsi, gsi_tgt;
5408   gimple_seq phis = phi_nodes (bb);
5409   gimple phi, stmt, copy;
5410
5411   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
5412
5413   /* Copy the PHI nodes.  We ignore PHI node arguments here because
5414      the incoming edges have not been setup yet.  */
5415   for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
5416     {
5417       phi = gsi_stmt (gsi);
5418       copy = create_phi_node (gimple_phi_result (phi), new_bb);
5419       create_new_def_for (gimple_phi_result (copy), copy,
5420                           gimple_phi_result_ptr (copy));
5421     }
5422
5423   gsi_tgt = gsi_start_bb (new_bb);
5424   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5425     {
5426       def_operand_p def_p;
5427       ssa_op_iter op_iter;
5428
5429       stmt = gsi_stmt (gsi);
5430       if (gimple_code (stmt) == GIMPLE_LABEL)
5431         continue;
5432
5433       /* Create a new copy of STMT and duplicate STMT's virtual
5434          operands.  */
5435       copy = gimple_copy (stmt);
5436       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
5437
5438       maybe_duplicate_eh_stmt (copy, stmt);
5439       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5440
5441       /* Create new names for all the definitions created by COPY and
5442          add replacement mappings for each new name.  */
5443       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5444         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5445     }
5446
5447   return new_bb;
5448 }
5449
5450 /* Adds phi node arguments for edge E_COPY after basic block duplication.  */
5451
5452 static void
5453 add_phi_args_after_copy_edge (edge e_copy)
5454 {
5455   basic_block bb, bb_copy = e_copy->src, dest;
5456   edge e;
5457   edge_iterator ei;
5458   gimple phi, phi_copy;
5459   tree def;
5460   gimple_stmt_iterator psi, psi_copy;
5461
5462   if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
5463     return;
5464
5465   bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5466
5467   if (e_copy->dest->flags & BB_DUPLICATED)
5468     dest = get_bb_original (e_copy->dest);
5469   else
5470     dest = e_copy->dest;
5471
5472   e = find_edge (bb, dest);
5473   if (!e)
5474     {
5475       /* During loop unrolling the target of the latch edge is copied.
5476          In this case we are not looking for edge to dest, but to
5477          duplicated block whose original was dest.  */
5478       FOR_EACH_EDGE (e, ei, bb->succs)
5479         {
5480           if ((e->dest->flags & BB_DUPLICATED)
5481               && get_bb_original (e->dest) == dest)
5482             break;
5483         }
5484
5485       gcc_assert (e != NULL);
5486     }
5487
5488   for (psi = gsi_start_phis (e->dest),
5489        psi_copy = gsi_start_phis (e_copy->dest);
5490        !gsi_end_p (psi);
5491        gsi_next (&psi), gsi_next (&psi_copy))
5492     {
5493       phi = gsi_stmt (psi);
5494       phi_copy = gsi_stmt (psi_copy);
5495       def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5496       add_phi_arg (phi_copy, def, e_copy,
5497                    gimple_phi_arg_location_from_edge (phi, e));
5498     }
5499 }
5500
5501
5502 /* Basic block BB_COPY was created by code duplication.  Add phi node
5503    arguments for edges going out of BB_COPY.  The blocks that were
5504    duplicated have BB_DUPLICATED set.  */
5505
5506 void
5507 add_phi_args_after_copy_bb (basic_block bb_copy)
5508 {
5509   edge e_copy;
5510   edge_iterator ei;
5511
5512   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5513     {
5514       add_phi_args_after_copy_edge (e_copy);
5515     }
5516 }
5517
5518 /* Blocks in REGION_COPY array of length N_REGION were created by
5519    duplication of basic blocks.  Add phi node arguments for edges
5520    going from these blocks.  If E_COPY is not NULL, also add
5521    phi node arguments for its destination.*/
5522
5523 void
5524 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5525                          edge e_copy)
5526 {
5527   unsigned i;
5528
5529   for (i = 0; i < n_region; i++)
5530     region_copy[i]->flags |= BB_DUPLICATED;
5531
5532   for (i = 0; i < n_region; i++)
5533     add_phi_args_after_copy_bb (region_copy[i]);
5534   if (e_copy)
5535     add_phi_args_after_copy_edge (e_copy);
5536
5537   for (i = 0; i < n_region; i++)
5538     region_copy[i]->flags &= ~BB_DUPLICATED;
5539 }
5540
5541 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5542    important exit edge EXIT.  By important we mean that no SSA name defined
5543    inside region is live over the other exit edges of the region.  All entry
5544    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
5545    to the duplicate of the region.  SSA form, dominance and loop information
5546    is updated.  The new basic blocks are stored to REGION_COPY in the same
5547    order as they had in REGION, provided that REGION_COPY is not NULL.
5548    The function returns false if it is unable to copy the region,
5549    true otherwise.  */
5550
5551 bool
5552 gimple_duplicate_sese_region (edge entry, edge exit,
5553                             basic_block *region, unsigned n_region,
5554                             basic_block *region_copy)
5555 {
5556   unsigned i;
5557   bool free_region_copy = false, copying_header = false;
5558   struct loop *loop = entry->dest->loop_father;
5559   edge exit_copy;
5560   VEC (basic_block, heap) *doms;
5561   edge redirected;
5562   int total_freq = 0, entry_freq = 0;
5563   gcov_type total_count = 0, entry_count = 0;
5564
5565   if (!can_copy_bbs_p (region, n_region))
5566     return false;
5567
5568   /* Some sanity checking.  Note that we do not check for all possible
5569      missuses of the functions.  I.e. if you ask to copy something weird,
5570      it will work, but the state of structures probably will not be
5571      correct.  */
5572   for (i = 0; i < n_region; i++)
5573     {
5574       /* We do not handle subloops, i.e. all the blocks must belong to the
5575          same loop.  */
5576       if (region[i]->loop_father != loop)
5577         return false;
5578
5579       if (region[i] != entry->dest
5580           && region[i] == loop->header)
5581         return false;
5582     }
5583
5584   set_loop_copy (loop, loop);
5585
5586   /* In case the function is used for loop header copying (which is the primary
5587      use), ensure that EXIT and its copy will be new latch and entry edges.  */
5588   if (loop->header == entry->dest)
5589     {
5590       copying_header = true;
5591       set_loop_copy (loop, loop_outer (loop));
5592
5593       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5594         return false;
5595
5596       for (i = 0; i < n_region; i++)
5597         if (region[i] != exit->src
5598             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5599           return false;
5600     }
5601
5602   if (!region_copy)
5603     {
5604       region_copy = XNEWVEC (basic_block, n_region);
5605       free_region_copy = true;
5606     }
5607
5608   gcc_assert (!need_ssa_update_p (cfun));
5609
5610   /* Record blocks outside the region that are dominated by something
5611      inside.  */
5612   doms = NULL;
5613   initialize_original_copy_tables ();
5614
5615   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5616
5617   if (entry->dest->count)
5618     {
5619       total_count = entry->dest->count;
5620       entry_count = entry->count;
5621       /* Fix up corner cases, to avoid division by zero or creation of negative
5622          frequencies.  */
5623       if (entry_count > total_count)
5624         entry_count = total_count;
5625     }
5626   else
5627     {
5628       total_freq = entry->dest->frequency;
5629       entry_freq = EDGE_FREQUENCY (entry);
5630       /* Fix up corner cases, to avoid division by zero or creation of negative
5631          frequencies.  */
5632       if (total_freq == 0)
5633         total_freq = 1;
5634       else if (entry_freq > total_freq)
5635         entry_freq = total_freq;
5636     }
5637
5638   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5639             split_edge_bb_loc (entry));
5640   if (total_count)
5641     {
5642       scale_bbs_frequencies_gcov_type (region, n_region,
5643                                        total_count - entry_count,
5644                                        total_count);
5645       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5646                                        total_count);
5647     }
5648   else
5649     {
5650       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5651                                  total_freq);
5652       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5653     }
5654
5655   if (copying_header)
5656     {
5657       loop->header = exit->dest;
5658       loop->latch = exit->src;
5659     }
5660
5661   /* Redirect the entry and add the phi node arguments.  */
5662   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5663   gcc_assert (redirected != NULL);
5664   flush_pending_stmts (entry);
5665
5666   /* Concerning updating of dominators:  We must recount dominators
5667      for entry block and its copy.  Anything that is outside of the
5668      region, but was dominated by something inside needs recounting as
5669      well.  */
5670   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5671   VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
5672   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5673   VEC_free (basic_block, heap, doms);
5674
5675   /* Add the other PHI node arguments.  */
5676   add_phi_args_after_copy (region_copy, n_region, NULL);
5677
5678   /* Update the SSA web.  */
5679   update_ssa (TODO_update_ssa);
5680
5681   if (free_region_copy)
5682     free (region_copy);
5683
5684   free_original_copy_tables ();
5685   return true;
5686 }
5687
5688 /* Duplicates REGION consisting of N_REGION blocks.  The new blocks
5689    are stored to REGION_COPY in the same order in that they appear
5690    in REGION, if REGION_COPY is not NULL.  ENTRY is the entry to
5691    the region, EXIT an exit from it.  The condition guarding EXIT
5692    is moved to ENTRY.  Returns true if duplication succeeds, false
5693    otherwise.
5694
5695    For example,
5696
5697    some_code;
5698    if (cond)
5699      A;
5700    else
5701      B;
5702
5703    is transformed to
5704
5705    if (cond)
5706      {
5707        some_code;
5708        A;
5709      }
5710    else
5711      {
5712        some_code;
5713        B;
5714      }
5715 */
5716
5717 bool
5718 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
5719                           basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
5720                           basic_block *region_copy ATTRIBUTE_UNUSED)
5721 {
5722   unsigned i;
5723   bool free_region_copy = false;
5724   struct loop *loop = exit->dest->loop_father;
5725   struct loop *orig_loop = entry->dest->loop_father;
5726   basic_block switch_bb, entry_bb, nentry_bb;
5727   VEC (basic_block, heap) *doms;
5728   int total_freq = 0, exit_freq = 0;
5729   gcov_type total_count = 0, exit_count = 0;
5730   edge exits[2], nexits[2], e;
5731   gimple_stmt_iterator gsi;
5732   gimple cond_stmt;
5733   edge sorig, snew;
5734
5735   gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5736   exits[0] = exit;
5737   exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5738
5739   if (!can_copy_bbs_p (region, n_region))
5740     return false;
5741
5742   /* Some sanity checking.  Note that we do not check for all possible
5743      missuses of the functions.  I.e. if you ask to copy something weird
5744      (e.g., in the example, if there is a jump from inside to the middle
5745      of some_code, or come_code defines some of the values used in cond)
5746      it will work, but the resulting code will not be correct.  */
5747   for (i = 0; i < n_region; i++)
5748     {
5749       /* We do not handle subloops, i.e. all the blocks must belong to the
5750          same loop.  */
5751       if (region[i]->loop_father != orig_loop)
5752         return false;
5753
5754       if (region[i] == orig_loop->latch)
5755         return false;
5756     }
5757
5758   initialize_original_copy_tables ();
5759   set_loop_copy (orig_loop, loop);
5760
5761   if (!region_copy)
5762     {
5763       region_copy = XNEWVEC (basic_block, n_region);
5764       free_region_copy = true;
5765     }
5766
5767   gcc_assert (!need_ssa_update_p (cfun));
5768
5769   /* Record blocks outside the region that are dominated by something
5770      inside.  */
5771   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5772
5773   if (exit->src->count)
5774     {
5775       total_count = exit->src->count;
5776       exit_count = exit->count;
5777       /* Fix up corner cases, to avoid division by zero or creation of negative
5778          frequencies.  */
5779       if (exit_count > total_count)
5780         exit_count = total_count;
5781     }
5782   else
5783     {
5784       total_freq = exit->src->frequency;
5785       exit_freq = EDGE_FREQUENCY (exit);
5786       /* Fix up corner cases, to avoid division by zero or creation of negative
5787          frequencies.  */
5788       if (total_freq == 0)
5789         total_freq = 1;
5790       if (exit_freq > total_freq)
5791         exit_freq = total_freq;
5792     }
5793
5794   copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5795             split_edge_bb_loc (exit));
5796   if (total_count)
5797     {
5798       scale_bbs_frequencies_gcov_type (region, n_region,
5799                                        total_count - exit_count,
5800                                        total_count);
5801       scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5802                                        total_count);
5803     }
5804   else
5805     {
5806       scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5807                                  total_freq);
5808       scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5809     }
5810
5811   /* Create the switch block, and put the exit condition to it.  */
5812   entry_bb = entry->dest;
5813   nentry_bb = get_bb_copy (entry_bb);
5814   if (!last_stmt (entry->src)
5815       || !stmt_ends_bb_p (last_stmt (entry->src)))
5816     switch_bb = entry->src;
5817   else
5818     switch_bb = split_edge (entry);
5819   set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5820
5821   gsi = gsi_last_bb (switch_bb);
5822   cond_stmt = last_stmt (exit->src);
5823   gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
5824   cond_stmt = gimple_copy (cond_stmt);
5825   gimple_cond_set_lhs (cond_stmt, unshare_expr (gimple_cond_lhs (cond_stmt)));
5826   gimple_cond_set_rhs (cond_stmt, unshare_expr (gimple_cond_rhs (cond_stmt)));
5827   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
5828
5829   sorig = single_succ_edge (switch_bb);
5830   sorig->flags = exits[1]->flags;
5831   snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5832
5833   /* Register the new edge from SWITCH_BB in loop exit lists.  */
5834   rescan_loop_exit (snew, true, false);
5835
5836   /* Add the PHI node arguments.  */
5837   add_phi_args_after_copy (region_copy, n_region, snew);
5838
5839   /* Get rid of now superfluous conditions and associated edges (and phi node
5840      arguments).  */
5841   e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5842   PENDING_STMT (e) = NULL;
5843   e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
5844   PENDING_STMT (e) = NULL;
5845
5846   /* Anything that is outside of the region, but was dominated by something
5847      inside needs to update dominance info.  */
5848   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5849   VEC_free (basic_block, heap, doms);
5850
5851   /* Update the SSA web.  */
5852   update_ssa (TODO_update_ssa);
5853
5854   if (free_region_copy)
5855     free (region_copy);
5856
5857   free_original_copy_tables ();
5858   return true;
5859 }
5860
5861 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
5862    adding blocks when the dominator traversal reaches EXIT.  This
5863    function silently assumes that ENTRY strictly dominates EXIT.  */
5864
5865 void
5866 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5867                               VEC(basic_block,heap) **bbs_p)
5868 {
5869   basic_block son;
5870
5871   for (son = first_dom_son (CDI_DOMINATORS, entry);
5872        son;
5873        son = next_dom_son (CDI_DOMINATORS, son))
5874     {
5875       VEC_safe_push (basic_block, heap, *bbs_p, son);
5876       if (son != exit)
5877         gather_blocks_in_sese_region (son, exit, bbs_p);
5878     }
5879 }
5880
5881 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5882    The duplicates are recorded in VARS_MAP.  */
5883
5884 static void
5885 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5886                            tree to_context)
5887 {
5888   tree t = *tp, new_t;
5889   struct function *f = DECL_STRUCT_FUNCTION (to_context);
5890   void **loc;
5891
5892   if (DECL_CONTEXT (t) == to_context)
5893     return;
5894
5895   loc = pointer_map_contains (vars_map, t);
5896
5897   if (!loc)
5898     {
5899       loc = pointer_map_insert (vars_map, t);
5900
5901       if (SSA_VAR_P (t))
5902         {
5903           new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5904           f->local_decls = tree_cons (NULL_TREE, new_t, f->local_decls);
5905         }
5906       else
5907         {
5908           gcc_assert (TREE_CODE (t) == CONST_DECL);
5909           new_t = copy_node (t);
5910         }
5911       DECL_CONTEXT (new_t) = to_context;
5912
5913       *loc = new_t;
5914     }
5915   else
5916     new_t = (tree) *loc;
5917
5918   *tp = new_t;
5919 }
5920
5921
5922 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5923    VARS_MAP maps old ssa names and var_decls to the new ones.  */
5924
5925 static tree
5926 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5927                   tree to_context)
5928 {
5929   void **loc;
5930   tree new_name, decl = SSA_NAME_VAR (name);
5931
5932   gcc_assert (is_gimple_reg (name));
5933
5934   loc = pointer_map_contains (vars_map, name);
5935
5936   if (!loc)
5937     {
5938       replace_by_duplicate_decl (&decl, vars_map, to_context);
5939
5940       push_cfun (DECL_STRUCT_FUNCTION (to_context));
5941       if (gimple_in_ssa_p (cfun))
5942         add_referenced_var (decl);
5943
5944       new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5945       if (SSA_NAME_IS_DEFAULT_DEF (name))
5946         set_default_def (decl, new_name);
5947       pop_cfun ();
5948
5949       loc = pointer_map_insert (vars_map, name);
5950       *loc = new_name;
5951     }
5952   else
5953     new_name = (tree) *loc;
5954
5955   return new_name;
5956 }
5957
5958 struct move_stmt_d
5959 {
5960   tree orig_block;
5961   tree new_block;
5962   tree from_context;
5963   tree to_context;
5964   struct pointer_map_t *vars_map;
5965   htab_t new_label_map;
5966   struct pointer_map_t *eh_map;
5967   bool remap_decls_p;
5968 };
5969
5970 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
5971    contained in *TP if it has been ORIG_BLOCK previously and change the
5972    DECL_CONTEXT of every local variable referenced in *TP.  */
5973
5974 static tree
5975 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
5976 {
5977   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
5978   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5979   tree t = *tp;
5980
5981   if (EXPR_P (t))
5982     /* We should never have TREE_BLOCK set on non-statements.  */
5983     gcc_assert (!TREE_BLOCK (t));
5984
5985   else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
5986     {
5987       if (TREE_CODE (t) == SSA_NAME)
5988         *tp = replace_ssa_name (t, p->vars_map, p->to_context);
5989       else if (TREE_CODE (t) == LABEL_DECL)
5990         {
5991           if (p->new_label_map)
5992             {
5993               struct tree_map in, *out;
5994               in.base.from = t;
5995               out = (struct tree_map *)
5996                 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
5997               if (out)
5998                 *tp = t = out->to;
5999             }
6000
6001           DECL_CONTEXT (t) = p->to_context;
6002         }
6003       else if (p->remap_decls_p)
6004         {
6005           /* Replace T with its duplicate.  T should no longer appear in the
6006              parent function, so this looks wasteful; however, it may appear
6007              in referenced_vars, and more importantly, as virtual operands of
6008              statements, and in alias lists of other variables.  It would be
6009              quite difficult to expunge it from all those places.  ??? It might
6010              suffice to do this for addressable variables.  */
6011           if ((TREE_CODE (t) == VAR_DECL
6012                && !is_global_var (t))
6013               || TREE_CODE (t) == CONST_DECL)
6014             replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
6015
6016           if (SSA_VAR_P (t)
6017               && gimple_in_ssa_p (cfun))
6018             {
6019               push_cfun (DECL_STRUCT_FUNCTION (p->to_context));
6020               add_referenced_var (*tp);
6021               pop_cfun ();
6022             }
6023         }
6024       *walk_subtrees = 0;
6025     }
6026   else if (TYPE_P (t))
6027     *walk_subtrees = 0;
6028
6029   return NULL_TREE;
6030 }
6031
6032 /* Helper for move_stmt_r.  Given an EH region number for the source
6033    function, map that to the duplicate EH regio number in the dest.  */
6034
6035 static int
6036 move_stmt_eh_region_nr (int old_nr, struct move_stmt_d *p)
6037 {
6038   eh_region old_r, new_r;
6039   void **slot;
6040
6041   old_r = get_eh_region_from_number (old_nr);
6042   slot = pointer_map_contains (p->eh_map, old_r);
6043   new_r = (eh_region) *slot;
6044
6045   return new_r->index;
6046 }
6047
6048 /* Similar, but operate on INTEGER_CSTs.  */
6049
6050 static tree
6051 move_stmt_eh_region_tree_nr (tree old_t_nr, struct move_stmt_d *p)
6052 {
6053   int old_nr, new_nr;
6054
6055   old_nr = tree_low_cst (old_t_nr, 0);
6056   new_nr = move_stmt_eh_region_nr (old_nr, p);
6057
6058   return build_int_cst (NULL, new_nr);
6059 }
6060
6061 /* Like move_stmt_op, but for gimple statements.
6062
6063    Helper for move_block_to_fn.  Set GIMPLE_BLOCK in every expression
6064    contained in the current statement in *GSI_P and change the
6065    DECL_CONTEXT of every local variable referenced in the current
6066    statement.  */
6067
6068 static tree
6069 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
6070              struct walk_stmt_info *wi)
6071 {
6072   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
6073   gimple stmt = gsi_stmt (*gsi_p);
6074   tree block = gimple_block (stmt);
6075
6076   if (p->orig_block == NULL_TREE
6077       || block == p->orig_block
6078       || block == NULL_TREE)
6079     gimple_set_block (stmt, p->new_block);
6080 #ifdef ENABLE_CHECKING
6081   else if (block != p->new_block)
6082     {
6083       while (block && block != p->orig_block)
6084         block = BLOCK_SUPERCONTEXT (block);
6085       gcc_assert (block);
6086     }
6087 #endif
6088
6089   switch (gimple_code (stmt))
6090     {
6091     case GIMPLE_CALL:
6092       /* Remap the region numbers for __builtin_eh_{pointer,filter}.  */
6093       {
6094         tree r, fndecl = gimple_call_fndecl (stmt);
6095         if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
6096           switch (DECL_FUNCTION_CODE (fndecl))
6097             {
6098             case BUILT_IN_EH_COPY_VALUES:
6099               r = gimple_call_arg (stmt, 1);
6100               r = move_stmt_eh_region_tree_nr (r, p);
6101               gimple_call_set_arg (stmt, 1, r);
6102               /* FALLTHRU */
6103
6104             case BUILT_IN_EH_POINTER:
6105             case BUILT_IN_EH_FILTER:
6106               r = gimple_call_arg (stmt, 0);
6107               r = move_stmt_eh_region_tree_nr (r, p);
6108               gimple_call_set_arg (stmt, 0, r);
6109               break;
6110
6111             default:
6112               break;
6113             }
6114       }
6115       break;
6116
6117     case GIMPLE_RESX:
6118       {
6119         int r = gimple_resx_region (stmt);
6120         r = move_stmt_eh_region_nr (r, p);
6121         gimple_resx_set_region (stmt, r);
6122       }
6123       break;
6124
6125     case GIMPLE_EH_DISPATCH:
6126       {
6127         int r = gimple_eh_dispatch_region (stmt);
6128         r = move_stmt_eh_region_nr (r, p);
6129         gimple_eh_dispatch_set_region (stmt, r);
6130       }
6131       break;
6132
6133     case GIMPLE_OMP_RETURN:
6134     case GIMPLE_OMP_CONTINUE:
6135       break;
6136     default:
6137       if (is_gimple_omp (stmt))
6138         {
6139           /* Do not remap variables inside OMP directives.  Variables
6140              referenced in clauses and directive header belong to the
6141              parent function and should not be moved into the child
6142              function.  */
6143           bool save_remap_decls_p = p->remap_decls_p;
6144           p->remap_decls_p = false;
6145           *handled_ops_p = true;
6146
6147           walk_gimple_seq (gimple_omp_body (stmt), move_stmt_r,
6148                            move_stmt_op, wi);
6149
6150           p->remap_decls_p = save_remap_decls_p;
6151         }
6152       break;
6153     }
6154
6155   return NULL_TREE;
6156 }
6157
6158 /* Marks virtual operands of all statements in basic blocks BBS for
6159    renaming.  */
6160
6161 void
6162 mark_virtual_ops_in_bb (basic_block bb)
6163 {
6164   gimple_stmt_iterator gsi;
6165
6166   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6167     mark_virtual_ops_for_renaming (gsi_stmt (gsi));
6168
6169   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
6170     mark_virtual_ops_for_renaming (gsi_stmt (gsi));
6171 }
6172
6173 /* Move basic block BB from function CFUN to function DEST_FN.  The
6174    block is moved out of the original linked list and placed after
6175    block AFTER in the new list.  Also, the block is removed from the
6176    original array of blocks and placed in DEST_FN's array of blocks.
6177    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
6178    updated to reflect the moved edges.
6179
6180    The local variables are remapped to new instances, VARS_MAP is used
6181    to record the mapping.  */
6182
6183 static void
6184 move_block_to_fn (struct function *dest_cfun, basic_block bb,
6185                   basic_block after, bool update_edge_count_p,
6186                   struct move_stmt_d *d)
6187 {
6188   struct control_flow_graph *cfg;
6189   edge_iterator ei;
6190   edge e;
6191   gimple_stmt_iterator si;
6192   unsigned old_len, new_len;
6193
6194   /* Remove BB from dominance structures.  */
6195   delete_from_dominance_info (CDI_DOMINATORS, bb);
6196   if (current_loops)
6197     remove_bb_from_loops (bb);
6198
6199   /* Link BB to the new linked list.  */
6200   move_block_after (bb, after);
6201
6202   /* Update the edge count in the corresponding flowgraphs.  */
6203   if (update_edge_count_p)
6204     FOR_EACH_EDGE (e, ei, bb->succs)
6205       {
6206         cfun->cfg->x_n_edges--;
6207         dest_cfun->cfg->x_n_edges++;
6208       }
6209
6210   /* Remove BB from the original basic block array.  */
6211   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
6212   cfun->cfg->x_n_basic_blocks--;
6213
6214   /* Grow DEST_CFUN's basic block array if needed.  */
6215   cfg = dest_cfun->cfg;
6216   cfg->x_n_basic_blocks++;
6217   if (bb->index >= cfg->x_last_basic_block)
6218     cfg->x_last_basic_block = bb->index + 1;
6219
6220   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
6221   if ((unsigned) cfg->x_last_basic_block >= old_len)
6222     {
6223       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
6224       VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
6225                              new_len);
6226     }
6227
6228   VEC_replace (basic_block, cfg->x_basic_block_info,
6229                bb->index, bb);
6230
6231   /* Remap the variables in phi nodes.  */
6232   for (si = gsi_start_phis (bb); !gsi_end_p (si); )
6233     {
6234       gimple phi = gsi_stmt (si);
6235       use_operand_p use;
6236       tree op = PHI_RESULT (phi);
6237       ssa_op_iter oi;
6238
6239       if (!is_gimple_reg (op))
6240         {
6241           /* Remove the phi nodes for virtual operands (alias analysis will be
6242              run for the new function, anyway).  */
6243           remove_phi_node (&si, true);
6244           continue;
6245         }
6246
6247       SET_PHI_RESULT (phi,
6248                       replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6249       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
6250         {
6251           op = USE_FROM_PTR (use);
6252           if (TREE_CODE (op) == SSA_NAME)
6253             SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6254         }
6255
6256       gsi_next (&si);
6257     }
6258
6259   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6260     {
6261       gimple stmt = gsi_stmt (si);
6262       struct walk_stmt_info wi;
6263
6264       memset (&wi, 0, sizeof (wi));
6265       wi.info = d;
6266       walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
6267
6268       if (gimple_code (stmt) == GIMPLE_LABEL)
6269         {
6270           tree label = gimple_label_label (stmt);
6271           int uid = LABEL_DECL_UID (label);
6272
6273           gcc_assert (uid > -1);
6274
6275           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
6276           if (old_len <= (unsigned) uid)
6277             {
6278               new_len = 3 * uid / 2 + 1;
6279               VEC_safe_grow_cleared (basic_block, gc,
6280                                      cfg->x_label_to_block_map, new_len);
6281             }
6282
6283           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
6284           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
6285
6286           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
6287
6288           if (uid >= dest_cfun->cfg->last_label_uid)
6289             dest_cfun->cfg->last_label_uid = uid + 1;
6290         }
6291
6292       maybe_duplicate_eh_stmt_fn (dest_cfun, stmt, cfun, stmt, d->eh_map, 0);
6293       remove_stmt_from_eh_lp_fn (cfun, stmt);
6294
6295       gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
6296       gimple_remove_stmt_histograms (cfun, stmt);
6297
6298       /* We cannot leave any operands allocated from the operand caches of
6299          the current function.  */
6300       free_stmt_operands (stmt);
6301       push_cfun (dest_cfun);
6302       update_stmt (stmt);
6303       pop_cfun ();
6304     }
6305
6306   FOR_EACH_EDGE (e, ei, bb->succs)
6307     if (e->goto_locus)
6308       {
6309         tree block = e->goto_block;
6310         if (d->orig_block == NULL_TREE
6311             || block == d->orig_block)
6312           e->goto_block = d->new_block;
6313 #ifdef ENABLE_CHECKING
6314         else if (block != d->new_block)
6315           {
6316             while (block && block != d->orig_block)
6317               block = BLOCK_SUPERCONTEXT (block);
6318             gcc_assert (block);
6319           }
6320 #endif
6321       }
6322 }
6323
6324 /* Examine the statements in BB (which is in SRC_CFUN); find and return
6325    the outermost EH region.  Use REGION as the incoming base EH region.  */
6326
6327 static eh_region
6328 find_outermost_region_in_block (struct function *src_cfun,
6329                                 basic_block bb, eh_region region)
6330 {
6331   gimple_stmt_iterator si;
6332
6333   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6334     {
6335       gimple stmt = gsi_stmt (si);
6336       eh_region stmt_region;
6337       int lp_nr;
6338
6339       lp_nr = lookup_stmt_eh_lp_fn (src_cfun, stmt);
6340       stmt_region = get_eh_region_from_lp_number_fn (src_cfun, lp_nr);
6341       if (stmt_region)
6342         {
6343           if (region == NULL)
6344             region = stmt_region;
6345           else if (stmt_region != region)
6346             {
6347               region = eh_region_outermost (src_cfun, stmt_region, region);
6348               gcc_assert (region != NULL);
6349             }
6350         }
6351     }
6352
6353   return region;
6354 }
6355
6356 static tree
6357 new_label_mapper (tree decl, void *data)
6358 {
6359   htab_t hash = (htab_t) data;
6360   struct tree_map *m;
6361   void **slot;
6362
6363   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
6364
6365   m = XNEW (struct tree_map);
6366   m->hash = DECL_UID (decl);
6367   m->base.from = decl;
6368   m->to = create_artificial_label (UNKNOWN_LOCATION);
6369   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
6370   if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
6371     cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
6372
6373   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
6374   gcc_assert (*slot == NULL);
6375
6376   *slot = m;
6377
6378   return m->to;
6379 }
6380
6381 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
6382    subblocks.  */
6383
6384 static void
6385 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map,
6386                                   tree to_context)
6387 {
6388   tree *tp, t;
6389
6390   for (tp = &BLOCK_VARS (block); *tp; tp = &TREE_CHAIN (*tp))
6391     {
6392       t = *tp;
6393       if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL)
6394         continue;
6395       replace_by_duplicate_decl (&t, vars_map, to_context);
6396       if (t != *tp)
6397         {
6398           if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
6399             {
6400               SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
6401               DECL_HAS_VALUE_EXPR_P (t) = 1;
6402             }
6403           TREE_CHAIN (t) = TREE_CHAIN (*tp);
6404           *tp = t;
6405         }
6406     }
6407
6408   for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
6409     replace_block_vars_by_duplicates (block, vars_map, to_context);
6410 }
6411
6412 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
6413    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
6414    single basic block in the original CFG and the new basic block is
6415    returned.  DEST_CFUN must not have a CFG yet.
6416
6417    Note that the region need not be a pure SESE region.  Blocks inside
6418    the region may contain calls to abort/exit.  The only restriction
6419    is that ENTRY_BB should be the only entry point and it must
6420    dominate EXIT_BB.
6421
6422    Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
6423    functions outermost BLOCK, move all subblocks of ORIG_BLOCK
6424    to the new function.
6425
6426    All local variables referenced in the region are assumed to be in
6427    the corresponding BLOCK_VARS and unexpanded variable lists
6428    associated with DEST_CFUN.  */
6429
6430 basic_block
6431 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
6432                         basic_block exit_bb, tree orig_block)
6433 {
6434   VEC(basic_block,heap) *bbs, *dom_bbs;
6435   basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
6436   basic_block after, bb, *entry_pred, *exit_succ, abb;
6437   struct function *saved_cfun = cfun;
6438   int *entry_flag, *exit_flag;
6439   unsigned *entry_prob, *exit_prob;
6440   unsigned i, num_entry_edges, num_exit_edges;
6441   edge e;
6442   edge_iterator ei;
6443   htab_t new_label_map;
6444   struct pointer_map_t *vars_map, *eh_map;
6445   struct loop *loop = entry_bb->loop_father;
6446   struct move_stmt_d d;
6447
6448   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
6449      region.  */
6450   gcc_assert (entry_bb != exit_bb
6451               && (!exit_bb
6452                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
6453
6454   /* Collect all the blocks in the region.  Manually add ENTRY_BB
6455      because it won't be added by dfs_enumerate_from.  */
6456   bbs = NULL;
6457   VEC_safe_push (basic_block, heap, bbs, entry_bb);
6458   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
6459
6460   /* The blocks that used to be dominated by something in BBS will now be
6461      dominated by the new block.  */
6462   dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
6463                                      VEC_address (basic_block, bbs),
6464                                      VEC_length (basic_block, bbs));
6465
6466   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
6467      the predecessor edges to ENTRY_BB and the successor edges to
6468      EXIT_BB so that we can re-attach them to the new basic block that
6469      will replace the region.  */
6470   num_entry_edges = EDGE_COUNT (entry_bb->preds);
6471   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
6472   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
6473   entry_prob = XNEWVEC (unsigned, num_entry_edges);
6474   i = 0;
6475   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
6476     {
6477       entry_prob[i] = e->probability;
6478       entry_flag[i] = e->flags;
6479       entry_pred[i++] = e->src;
6480       remove_edge (e);
6481     }
6482
6483   if (exit_bb)
6484     {
6485       num_exit_edges = EDGE_COUNT (exit_bb->succs);
6486       exit_succ = (basic_block *) xcalloc (num_exit_edges,
6487                                            sizeof (basic_block));
6488       exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
6489       exit_prob = XNEWVEC (unsigned, num_exit_edges);
6490       i = 0;
6491       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6492         {
6493           exit_prob[i] = e->probability;
6494           exit_flag[i] = e->flags;
6495           exit_succ[i++] = e->dest;
6496           remove_edge (e);
6497         }
6498     }
6499   else
6500     {
6501       num_exit_edges = 0;
6502       exit_succ = NULL;
6503       exit_flag = NULL;
6504       exit_prob = NULL;
6505     }
6506
6507   /* Switch context to the child function to initialize DEST_FN's CFG.  */
6508   gcc_assert (dest_cfun->cfg == NULL);
6509   push_cfun (dest_cfun);
6510
6511   init_empty_tree_cfg ();
6512
6513   /* Initialize EH information for the new function.  */
6514   eh_map = NULL;
6515   new_label_map = NULL;
6516   if (saved_cfun->eh)
6517     {
6518       eh_region region = NULL;
6519
6520       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
6521         region = find_outermost_region_in_block (saved_cfun, bb, region);
6522
6523       init_eh_for_function ();
6524       if (region != NULL)
6525         {
6526           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6527           eh_map = duplicate_eh_regions (saved_cfun, region, 0,
6528                                          new_label_mapper, new_label_map);
6529         }
6530     }
6531
6532   pop_cfun ();
6533
6534   /* Move blocks from BBS into DEST_CFUN.  */
6535   gcc_assert (VEC_length (basic_block, bbs) >= 2);
6536   after = dest_cfun->cfg->x_entry_block_ptr;
6537   vars_map = pointer_map_create ();
6538
6539   memset (&d, 0, sizeof (d));
6540   d.orig_block = orig_block;
6541   d.new_block = DECL_INITIAL (dest_cfun->decl);
6542   d.from_context = cfun->decl;
6543   d.to_context = dest_cfun->decl;
6544   d.vars_map = vars_map;
6545   d.new_label_map = new_label_map;
6546   d.eh_map = eh_map;
6547   d.remap_decls_p = true;
6548
6549   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
6550     {
6551       /* No need to update edge counts on the last block.  It has
6552          already been updated earlier when we detached the region from
6553          the original CFG.  */
6554       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d);
6555       after = bb;
6556     }
6557
6558   /* Rewire BLOCK_SUBBLOCKS of orig_block.  */
6559   if (orig_block)
6560     {
6561       tree block;
6562       gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6563                   == NULL_TREE);
6564       BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6565         = BLOCK_SUBBLOCKS (orig_block);
6566       for (block = BLOCK_SUBBLOCKS (orig_block);
6567            block; block = BLOCK_CHAIN (block))
6568         BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
6569       BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
6570     }
6571
6572   replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
6573                                     vars_map, dest_cfun->decl);
6574
6575   if (new_label_map)
6576     htab_delete (new_label_map);
6577   if (eh_map)
6578     pointer_map_destroy (eh_map);
6579   pointer_map_destroy (vars_map);
6580
6581   /* Rewire the entry and exit blocks.  The successor to the entry
6582      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6583      the child function.  Similarly, the predecessor of DEST_FN's
6584      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
6585      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6586      various CFG manipulation function get to the right CFG.
6587
6588      FIXME, this is silly.  The CFG ought to become a parameter to
6589      these helpers.  */
6590   push_cfun (dest_cfun);
6591   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6592   if (exit_bb)
6593     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
6594   pop_cfun ();
6595
6596   /* Back in the original function, the SESE region has disappeared,
6597      create a new basic block in its place.  */
6598   bb = create_empty_bb (entry_pred[0]);
6599   if (current_loops)
6600     add_bb_to_loop (bb, loop);
6601   for (i = 0; i < num_entry_edges; i++)
6602     {
6603       e = make_edge (entry_pred[i], bb, entry_flag[i]);
6604       e->probability = entry_prob[i];
6605     }
6606
6607   for (i = 0; i < num_exit_edges; i++)
6608     {
6609       e = make_edge (bb, exit_succ[i], exit_flag[i]);
6610       e->probability = exit_prob[i];
6611     }
6612
6613   set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6614   for (i = 0; VEC_iterate (basic_block, dom_bbs, i, abb); i++)
6615     set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6616   VEC_free (basic_block, heap, dom_bbs);
6617
6618   if (exit_bb)
6619     {
6620       free (exit_prob);
6621       free (exit_flag);
6622       free (exit_succ);
6623     }
6624   free (entry_prob);
6625   free (entry_flag);
6626   free (entry_pred);
6627   VEC_free (basic_block, heap, bbs);
6628
6629   return bb;
6630 }
6631
6632
6633 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree-pass.h)
6634    */
6635
6636 void
6637 dump_function_to_file (tree fn, FILE *file, int flags)
6638 {
6639   tree arg, vars, var;
6640   struct function *dsf;
6641   bool ignore_topmost_bind = false, any_var = false;
6642   basic_block bb;
6643   tree chain;
6644
6645   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
6646
6647   arg = DECL_ARGUMENTS (fn);
6648   while (arg)
6649     {
6650       print_generic_expr (file, TREE_TYPE (arg), dump_flags);
6651       fprintf (file, " ");
6652       print_generic_expr (file, arg, dump_flags);
6653       if (flags & TDF_VERBOSE)
6654         print_node (file, "", arg, 4);
6655       if (TREE_CHAIN (arg))
6656         fprintf (file, ", ");
6657       arg = TREE_CHAIN (arg);
6658     }
6659   fprintf (file, ")\n");
6660
6661   if (flags & TDF_VERBOSE)
6662     print_node (file, "", fn, 2);
6663
6664   dsf = DECL_STRUCT_FUNCTION (fn);
6665   if (dsf && (flags & TDF_EH))
6666     dump_eh_tree (file, dsf);
6667
6668   if (flags & TDF_RAW && !gimple_has_body_p (fn))
6669     {
6670       dump_node (fn, TDF_SLIM | flags, file);
6671       return;
6672     }
6673
6674   /* Switch CFUN to point to FN.  */
6675   push_cfun (DECL_STRUCT_FUNCTION (fn));
6676
6677   /* When GIMPLE is lowered, the variables are no longer available in
6678      BIND_EXPRs, so display them separately.  */
6679   if (cfun && cfun->decl == fn && cfun->local_decls)
6680     {
6681       ignore_topmost_bind = true;
6682
6683       fprintf (file, "{\n");
6684       for (vars = cfun->local_decls; vars; vars = TREE_CHAIN (vars))
6685         {
6686           var = TREE_VALUE (vars);
6687
6688           print_generic_decl (file, var, flags);
6689           if (flags & TDF_VERBOSE)
6690             print_node (file, "", var, 4);
6691           fprintf (file, "\n");
6692
6693           any_var = true;
6694         }
6695     }
6696
6697   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
6698     {
6699       /* If the CFG has been built, emit a CFG-based dump.  */
6700       check_bb_profile (ENTRY_BLOCK_PTR, file);
6701       if (!ignore_topmost_bind)
6702         fprintf (file, "{\n");
6703
6704       if (any_var && n_basic_blocks)
6705         fprintf (file, "\n");
6706
6707       FOR_EACH_BB (bb)
6708         gimple_dump_bb (bb, file, 2, flags);
6709
6710       fprintf (file, "}\n");
6711       check_bb_profile (EXIT_BLOCK_PTR, file);
6712     }
6713   else if (DECL_SAVED_TREE (fn) == NULL)
6714     {
6715       /* The function is now in GIMPLE form but the CFG has not been
6716          built yet.  Emit the single sequence of GIMPLE statements
6717          that make up its body.  */
6718       gimple_seq body = gimple_body (fn);
6719
6720       if (gimple_seq_first_stmt (body)
6721           && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
6722           && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
6723         print_gimple_seq (file, body, 0, flags);
6724       else
6725         {
6726           if (!ignore_topmost_bind)
6727             fprintf (file, "{\n");
6728
6729           if (any_var)
6730             fprintf (file, "\n");
6731
6732           print_gimple_seq (file, body, 2, flags);
6733           fprintf (file, "}\n");
6734         }
6735     }
6736   else
6737     {
6738       int indent;
6739
6740       /* Make a tree based dump.  */
6741       chain = DECL_SAVED_TREE (fn);
6742
6743       if (chain && TREE_CODE (chain) == BIND_EXPR)
6744         {
6745           if (ignore_topmost_bind)
6746             {
6747               chain = BIND_EXPR_BODY (chain);
6748               indent = 2;
6749             }
6750           else
6751             indent = 0;
6752         }
6753       else
6754         {
6755           if (!ignore_topmost_bind)
6756             fprintf (file, "{\n");
6757           indent = 2;
6758         }
6759
6760       if (any_var)
6761         fprintf (file, "\n");
6762
6763       print_generic_stmt_indented (file, chain, flags, indent);
6764       if (ignore_topmost_bind)
6765         fprintf (file, "}\n");
6766     }
6767
6768   fprintf (file, "\n\n");
6769
6770   /* Restore CFUN.  */
6771   pop_cfun ();
6772 }
6773
6774
6775 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
6776
6777 void
6778 debug_function (tree fn, int flags)
6779 {
6780   dump_function_to_file (fn, stderr, flags);
6781 }
6782
6783
6784 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
6785
6786 static void
6787 print_pred_bbs (FILE *file, basic_block bb)
6788 {
6789   edge e;
6790   edge_iterator ei;
6791
6792   FOR_EACH_EDGE (e, ei, bb->preds)
6793     fprintf (file, "bb_%d ", e->src->index);
6794 }
6795
6796
6797 /* Print on FILE the indexes for the successors of basic_block BB.  */
6798
6799 static void
6800 print_succ_bbs (FILE *file, basic_block bb)
6801 {
6802   edge e;
6803   edge_iterator ei;
6804
6805   FOR_EACH_EDGE (e, ei, bb->succs)
6806     fprintf (file, "bb_%d ", e->dest->index);
6807 }
6808
6809 /* Print to FILE the basic block BB following the VERBOSITY level.  */
6810
6811 void
6812 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6813 {
6814   char *s_indent = (char *) alloca ((size_t) indent + 1);
6815   memset ((void *) s_indent, ' ', (size_t) indent);
6816   s_indent[indent] = '\0';
6817
6818   /* Print basic_block's header.  */
6819   if (verbosity >= 2)
6820     {
6821       fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
6822       print_pred_bbs (file, bb);
6823       fprintf (file, "}, succs = {");
6824       print_succ_bbs (file, bb);
6825       fprintf (file, "})\n");
6826     }
6827
6828   /* Print basic_block's body.  */
6829   if (verbosity >= 3)
6830     {
6831       fprintf (file, "%s  {\n", s_indent);
6832       gimple_dump_bb (bb, file, indent + 4, TDF_VOPS|TDF_MEMSYMS);
6833       fprintf (file, "%s  }\n", s_indent);
6834     }
6835 }
6836
6837 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6838
6839 /* Pretty print LOOP on FILE, indented INDENT spaces.  Following
6840    VERBOSITY level this outputs the contents of the loop, or just its
6841    structure.  */
6842
6843 static void
6844 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6845 {
6846   char *s_indent;
6847   basic_block bb;
6848
6849   if (loop == NULL)
6850     return;
6851
6852   s_indent = (char *) alloca ((size_t) indent + 1);
6853   memset ((void *) s_indent, ' ', (size_t) indent);
6854   s_indent[indent] = '\0';
6855
6856   /* Print loop's header.  */
6857   fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent,
6858            loop->num, loop->header->index, loop->latch->index);
6859   fprintf (file, ", niter = ");
6860   print_generic_expr (file, loop->nb_iterations, 0);
6861
6862   if (loop->any_upper_bound)
6863     {
6864       fprintf (file, ", upper_bound = ");
6865       dump_double_int (file, loop->nb_iterations_upper_bound, true);
6866     }
6867
6868   if (loop->any_estimate)
6869     {
6870       fprintf (file, ", estimate = ");
6871       dump_double_int (file, loop->nb_iterations_estimate, true);
6872     }
6873   fprintf (file, ")\n");
6874
6875   /* Print loop's body.  */
6876   if (verbosity >= 1)
6877     {
6878       fprintf (file, "%s{\n", s_indent);
6879       FOR_EACH_BB (bb)
6880         if (bb->loop_father == loop)
6881           print_loops_bb (file, bb, indent, verbosity);
6882
6883       print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
6884       fprintf (file, "%s}\n", s_indent);
6885     }
6886 }
6887
6888 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6889    spaces.  Following VERBOSITY level this outputs the contents of the
6890    loop, or just its structure.  */
6891
6892 static void
6893 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
6894 {
6895   if (loop == NULL)
6896     return;
6897
6898   print_loop (file, loop, indent, verbosity);
6899   print_loop_and_siblings (file, loop->next, indent, verbosity);
6900 }
6901
6902 /* Follow a CFG edge from the entry point of the program, and on entry
6903    of a loop, pretty print the loop structure on FILE.  */
6904
6905 void
6906 print_loops (FILE *file, int verbosity)
6907 {
6908   basic_block bb;
6909
6910   bb = ENTRY_BLOCK_PTR;
6911   if (bb && bb->loop_father)
6912     print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
6913 }
6914
6915
6916 /* Debugging loops structure at tree level, at some VERBOSITY level.  */
6917
6918 void
6919 debug_loops (int verbosity)
6920 {
6921   print_loops (stderr, verbosity);
6922 }
6923
6924 /* Print on stderr the code of LOOP, at some VERBOSITY level.  */
6925
6926 void
6927 debug_loop (struct loop *loop, int verbosity)
6928 {
6929   print_loop (stderr, loop, 0, verbosity);
6930 }
6931
6932 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6933    level.  */
6934
6935 void
6936 debug_loop_num (unsigned num, int verbosity)
6937 {
6938   debug_loop (get_loop (num), verbosity);
6939 }
6940
6941 /* Return true if BB ends with a call, possibly followed by some
6942    instructions that must stay with the call.  Return false,
6943    otherwise.  */
6944
6945 static bool
6946 gimple_block_ends_with_call_p (basic_block bb)
6947 {
6948   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
6949   return is_gimple_call (gsi_stmt (gsi));
6950 }
6951
6952
6953 /* Return true if BB ends with a conditional branch.  Return false,
6954    otherwise.  */
6955
6956 static bool
6957 gimple_block_ends_with_condjump_p (const_basic_block bb)
6958 {
6959   gimple stmt = last_stmt (CONST_CAST_BB (bb));
6960   return (stmt && gimple_code (stmt) == GIMPLE_COND);
6961 }
6962
6963
6964 /* Return true if we need to add fake edge to exit at statement T.
6965    Helper function for gimple_flow_call_edges_add.  */
6966
6967 static bool
6968 need_fake_edge_p (gimple t)
6969 {
6970   tree fndecl = NULL_TREE;
6971   int call_flags = 0;
6972
6973   /* NORETURN and LONGJMP calls already have an edge to exit.
6974      CONST and PURE calls do not need one.
6975      We don't currently check for CONST and PURE here, although
6976      it would be a good idea, because those attributes are
6977      figured out from the RTL in mark_constant_function, and
6978      the counter incrementation code from -fprofile-arcs
6979      leads to different results from -fbranch-probabilities.  */
6980   if (is_gimple_call (t))
6981     {
6982       fndecl = gimple_call_fndecl (t);
6983       call_flags = gimple_call_flags (t);
6984     }
6985
6986   if (is_gimple_call (t)
6987       && fndecl
6988       && DECL_BUILT_IN (fndecl)
6989       && (call_flags & ECF_NOTHROW)
6990       && !(call_flags & ECF_RETURNS_TWICE)
6991       /* fork() doesn't really return twice, but the effect of
6992          wrapping it in __gcov_fork() which calls __gcov_flush()
6993          and clears the counters before forking has the same
6994          effect as returning twice.  Force a fake edge.  */
6995       && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
6996            && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK))
6997     return false;
6998
6999   if (is_gimple_call (t)
7000       && !(call_flags & ECF_NORETURN))
7001     return true;
7002
7003   if (gimple_code (t) == GIMPLE_ASM
7004        && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
7005     return true;
7006
7007   return false;
7008 }
7009
7010
7011 /* Add fake edges to the function exit for any non constant and non
7012    noreturn calls, volatile inline assembly in the bitmap of blocks
7013    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
7014    the number of blocks that were split.
7015
7016    The goal is to expose cases in which entering a basic block does
7017    not imply that all subsequent instructions must be executed.  */
7018
7019 static int
7020 gimple_flow_call_edges_add (sbitmap blocks)
7021 {
7022   int i;
7023   int blocks_split = 0;
7024   int last_bb = last_basic_block;
7025   bool check_last_block = false;
7026
7027   if (n_basic_blocks == NUM_FIXED_BLOCKS)
7028     return 0;
7029
7030   if (! blocks)
7031     check_last_block = true;
7032   else
7033     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
7034
7035   /* In the last basic block, before epilogue generation, there will be
7036      a fallthru edge to EXIT.  Special care is required if the last insn
7037      of the last basic block is a call because make_edge folds duplicate
7038      edges, which would result in the fallthru edge also being marked
7039      fake, which would result in the fallthru edge being removed by
7040      remove_fake_edges, which would result in an invalid CFG.
7041
7042      Moreover, we can't elide the outgoing fake edge, since the block
7043      profiler needs to take this into account in order to solve the minimal
7044      spanning tree in the case that the call doesn't return.
7045
7046      Handle this by adding a dummy instruction in a new last basic block.  */
7047   if (check_last_block)
7048     {
7049       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
7050       gimple_stmt_iterator gsi = gsi_last_bb (bb);
7051       gimple t = NULL;
7052
7053       if (!gsi_end_p (gsi))
7054         t = gsi_stmt (gsi);
7055
7056       if (t && need_fake_edge_p (t))
7057         {
7058           edge e;
7059
7060           e = find_edge (bb, EXIT_BLOCK_PTR);
7061           if (e)
7062             {
7063               gsi_insert_on_edge (e, gimple_build_nop ());
7064               gsi_commit_edge_inserts ();
7065             }
7066         }
7067     }
7068
7069   /* Now add fake edges to the function exit for any non constant
7070      calls since there is no way that we can determine if they will
7071      return or not...  */
7072   for (i = 0; i < last_bb; i++)
7073     {
7074       basic_block bb = BASIC_BLOCK (i);
7075       gimple_stmt_iterator gsi;
7076       gimple stmt, last_stmt;
7077
7078       if (!bb)
7079         continue;
7080
7081       if (blocks && !TEST_BIT (blocks, i))
7082         continue;
7083
7084       gsi = gsi_last_bb (bb);
7085       if (!gsi_end_p (gsi))
7086         {
7087           last_stmt = gsi_stmt (gsi);
7088           do
7089             {
7090               stmt = gsi_stmt (gsi);
7091               if (need_fake_edge_p (stmt))
7092                 {
7093                   edge e;
7094
7095                   /* The handling above of the final block before the
7096                      epilogue should be enough to verify that there is
7097                      no edge to the exit block in CFG already.
7098                      Calling make_edge in such case would cause us to
7099                      mark that edge as fake and remove it later.  */
7100 #ifdef ENABLE_CHECKING
7101                   if (stmt == last_stmt)
7102                     {
7103                       e = find_edge (bb, EXIT_BLOCK_PTR);
7104                       gcc_assert (e == NULL);
7105                     }
7106 #endif
7107
7108                   /* Note that the following may create a new basic block
7109                      and renumber the existing basic blocks.  */
7110                   if (stmt != last_stmt)
7111                     {
7112                       e = split_block (bb, stmt);
7113                       if (e)
7114                         blocks_split++;
7115                     }
7116                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
7117                 }
7118               gsi_prev (&gsi);
7119             }
7120           while (!gsi_end_p (gsi));
7121         }
7122     }
7123
7124   if (blocks_split)
7125     verify_flow_info ();
7126
7127   return blocks_split;
7128 }
7129
7130 /* Purge dead abnormal call edges from basic block BB.  */
7131
7132 bool
7133 gimple_purge_dead_abnormal_call_edges (basic_block bb)
7134 {
7135   bool changed = gimple_purge_dead_eh_edges (bb);
7136
7137   if (cfun->has_nonlocal_label)
7138     {
7139       gimple stmt = last_stmt (bb);
7140       edge_iterator ei;
7141       edge e;
7142
7143       if (!(stmt && stmt_can_make_abnormal_goto (stmt)))
7144         for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7145           {
7146             if (e->flags & EDGE_ABNORMAL)
7147               {
7148                 remove_edge (e);
7149                 changed = true;
7150               }
7151             else
7152               ei_next (&ei);
7153           }
7154
7155       /* See gimple_purge_dead_eh_edges below.  */
7156       if (changed)
7157         free_dominance_info (CDI_DOMINATORS);
7158     }
7159
7160   return changed;
7161 }
7162
7163 /* Removes edge E and all the blocks dominated by it, and updates dominance
7164    information.  The IL in E->src needs to be updated separately.
7165    If dominance info is not available, only the edge E is removed.*/
7166
7167 void
7168 remove_edge_and_dominated_blocks (edge e)
7169 {
7170   VEC (basic_block, heap) *bbs_to_remove = NULL;
7171   VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
7172   bitmap df, df_idom;
7173   edge f;
7174   edge_iterator ei;
7175   bool none_removed = false;
7176   unsigned i;
7177   basic_block bb, dbb;
7178   bitmap_iterator bi;
7179
7180   if (!dom_info_available_p (CDI_DOMINATORS))
7181     {
7182       remove_edge (e);
7183       return;
7184     }
7185
7186   /* No updating is needed for edges to exit.  */
7187   if (e->dest == EXIT_BLOCK_PTR)
7188     {
7189       if (cfgcleanup_altered_bbs)
7190         bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7191       remove_edge (e);
7192       return;
7193     }
7194
7195   /* First, we find the basic blocks to remove.  If E->dest has a predecessor
7196      that is not dominated by E->dest, then this set is empty.  Otherwise,
7197      all the basic blocks dominated by E->dest are removed.
7198
7199      Also, to DF_IDOM we store the immediate dominators of the blocks in
7200      the dominance frontier of E (i.e., of the successors of the
7201      removed blocks, if there are any, and of E->dest otherwise).  */
7202   FOR_EACH_EDGE (f, ei, e->dest->preds)
7203     {
7204       if (f == e)
7205         continue;
7206
7207       if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
7208         {
7209           none_removed = true;
7210           break;
7211         }
7212     }
7213
7214   df = BITMAP_ALLOC (NULL);
7215   df_idom = BITMAP_ALLOC (NULL);
7216
7217   if (none_removed)
7218     bitmap_set_bit (df_idom,
7219                     get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
7220   else
7221     {
7222       bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest);
7223       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
7224         {
7225           FOR_EACH_EDGE (f, ei, bb->succs)
7226             {
7227               if (f->dest != EXIT_BLOCK_PTR)
7228                 bitmap_set_bit (df, f->dest->index);
7229             }
7230         }
7231       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
7232         bitmap_clear_bit (df, bb->index);
7233
7234       EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
7235         {
7236           bb = BASIC_BLOCK (i);
7237           bitmap_set_bit (df_idom,
7238                           get_immediate_dominator (CDI_DOMINATORS, bb)->index);
7239         }
7240     }
7241
7242   if (cfgcleanup_altered_bbs)
7243     {
7244       /* Record the set of the altered basic blocks.  */
7245       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7246       bitmap_ior_into (cfgcleanup_altered_bbs, df);
7247     }
7248
7249   /* Remove E and the cancelled blocks.  */
7250   if (none_removed)
7251     remove_edge (e);
7252   else
7253     {
7254       /* Walk backwards so as to get a chance to substitute all
7255          released DEFs into debug stmts.  See
7256          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
7257          details.  */
7258       for (i = VEC_length (basic_block, bbs_to_remove); i-- > 0; )
7259         delete_basic_block (VEC_index (basic_block, bbs_to_remove, i));
7260     }
7261
7262   /* Update the dominance information.  The immediate dominator may change only
7263      for blocks whose immediate dominator belongs to DF_IDOM:
7264
7265      Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
7266      removal.  Let Z the arbitrary block such that idom(Z) = Y and
7267      Z dominates X after the removal.  Before removal, there exists a path P
7268      from Y to X that avoids Z.  Let F be the last edge on P that is
7269      removed, and let W = F->dest.  Before removal, idom(W) = Y (since Y
7270      dominates W, and because of P, Z does not dominate W), and W belongs to
7271      the dominance frontier of E.  Therefore, Y belongs to DF_IDOM.  */
7272   EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
7273     {
7274       bb = BASIC_BLOCK (i);
7275       for (dbb = first_dom_son (CDI_DOMINATORS, bb);
7276            dbb;
7277            dbb = next_dom_son (CDI_DOMINATORS, dbb))
7278         VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
7279     }
7280
7281   iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
7282
7283   BITMAP_FREE (df);
7284   BITMAP_FREE (df_idom);
7285   VEC_free (basic_block, heap, bbs_to_remove);
7286   VEC_free (basic_block, heap, bbs_to_fix_dom);
7287 }
7288
7289 /* Purge dead EH edges from basic block BB.  */
7290
7291 bool
7292 gimple_purge_dead_eh_edges (basic_block bb)
7293 {
7294   bool changed = false;
7295   edge e;
7296   edge_iterator ei;
7297   gimple stmt = last_stmt (bb);
7298
7299   if (stmt && stmt_can_throw_internal (stmt))
7300     return false;
7301
7302   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7303     {
7304       if (e->flags & EDGE_EH)
7305         {
7306           remove_edge_and_dominated_blocks (e);
7307           changed = true;
7308         }
7309       else
7310         ei_next (&ei);
7311     }
7312
7313   return changed;
7314 }
7315
7316 bool
7317 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
7318 {
7319   bool changed = false;
7320   unsigned i;
7321   bitmap_iterator bi;
7322
7323   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7324     {
7325       basic_block bb = BASIC_BLOCK (i);
7326
7327       /* Earlier gimple_purge_dead_eh_edges could have removed
7328          this basic block already.  */
7329       gcc_assert (bb || changed);
7330       if (bb != NULL)
7331         changed |= gimple_purge_dead_eh_edges (bb);
7332     }
7333
7334   return changed;
7335 }
7336
7337 /* This function is called whenever a new edge is created or
7338    redirected.  */
7339
7340 static void
7341 gimple_execute_on_growing_pred (edge e)
7342 {
7343   basic_block bb = e->dest;
7344
7345   if (phi_nodes (bb))
7346     reserve_phi_args_for_new_edge (bb);
7347 }
7348
7349 /* This function is called immediately before edge E is removed from
7350    the edge vector E->dest->preds.  */
7351
7352 static void
7353 gimple_execute_on_shrinking_pred (edge e)
7354 {
7355   if (phi_nodes (e->dest))
7356     remove_phi_args (e);
7357 }
7358
7359 /*---------------------------------------------------------------------------
7360   Helper functions for Loop versioning
7361   ---------------------------------------------------------------------------*/
7362
7363 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
7364    of 'first'. Both of them are dominated by 'new_head' basic block. When
7365    'new_head' was created by 'second's incoming edge it received phi arguments
7366    on the edge by split_edge(). Later, additional edge 'e' was created to
7367    connect 'new_head' and 'first'. Now this routine adds phi args on this
7368    additional edge 'e' that new_head to second edge received as part of edge
7369    splitting.  */
7370
7371 static void
7372 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
7373                                   basic_block new_head, edge e)
7374 {
7375   gimple phi1, phi2;
7376   gimple_stmt_iterator psi1, psi2;
7377   tree def;
7378   edge e2 = find_edge (new_head, second);
7379
7380   /* Because NEW_HEAD has been created by splitting SECOND's incoming
7381      edge, we should always have an edge from NEW_HEAD to SECOND.  */
7382   gcc_assert (e2 != NULL);
7383
7384   /* Browse all 'second' basic block phi nodes and add phi args to
7385      edge 'e' for 'first' head. PHI args are always in correct order.  */
7386
7387   for (psi2 = gsi_start_phis (second),
7388        psi1 = gsi_start_phis (first);
7389        !gsi_end_p (psi2) && !gsi_end_p (psi1);
7390        gsi_next (&psi2),  gsi_next (&psi1))
7391     {
7392       phi1 = gsi_stmt (psi1);
7393       phi2 = gsi_stmt (psi2);
7394       def = PHI_ARG_DEF (phi2, e2->dest_idx);
7395       add_phi_arg (phi1, def, e, gimple_phi_arg_location_from_edge (phi2, e2));
7396     }
7397 }
7398
7399
7400 /* Adds a if else statement to COND_BB with condition COND_EXPR.
7401    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
7402    the destination of the ELSE part.  */
7403
7404 static void
7405 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
7406                                basic_block second_head ATTRIBUTE_UNUSED,
7407                                basic_block cond_bb, void *cond_e)
7408 {
7409   gimple_stmt_iterator gsi;
7410   gimple new_cond_expr;
7411   tree cond_expr = (tree) cond_e;
7412   edge e0;
7413
7414   /* Build new conditional expr */
7415   new_cond_expr = gimple_build_cond_from_tree (cond_expr,
7416                                                NULL_TREE, NULL_TREE);
7417
7418   /* Add new cond in cond_bb.  */
7419   gsi = gsi_last_bb (cond_bb);
7420   gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
7421
7422   /* Adjust edges appropriately to connect new head with first head
7423      as well as second head.  */
7424   e0 = single_succ_edge (cond_bb);
7425   e0->flags &= ~EDGE_FALLTHRU;
7426   e0->flags |= EDGE_FALSE_VALUE;
7427 }
7428
7429 struct cfg_hooks gimple_cfg_hooks = {
7430   "gimple",
7431   gimple_verify_flow_info,
7432   gimple_dump_bb,               /* dump_bb  */
7433   create_bb,                    /* create_basic_block  */
7434   gimple_redirect_edge_and_branch, /* redirect_edge_and_branch  */
7435   gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force  */
7436   gimple_can_remove_branch_p,   /* can_remove_branch_p  */
7437   remove_bb,                    /* delete_basic_block  */
7438   gimple_split_block,           /* split_block  */
7439   gimple_move_block_after,      /* move_block_after  */
7440   gimple_can_merge_blocks_p,    /* can_merge_blocks_p  */
7441   gimple_merge_blocks,          /* merge_blocks  */
7442   gimple_predict_edge,          /* predict_edge  */
7443   gimple_predicted_by_p,                /* predicted_by_p  */
7444   gimple_can_duplicate_bb_p,    /* can_duplicate_block_p  */
7445   gimple_duplicate_bb,          /* duplicate_block  */
7446   gimple_split_edge,            /* split_edge  */
7447   gimple_make_forwarder_block,  /* make_forward_block  */
7448   NULL,                         /* tidy_fallthru_edge  */
7449   gimple_block_ends_with_call_p,/* block_ends_with_call_p */
7450   gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
7451   gimple_flow_call_edges_add,     /* flow_call_edges_add */
7452   gimple_execute_on_growing_pred,       /* execute_on_growing_pred */
7453   gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
7454   gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
7455   gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
7456   gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
7457   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
7458   flush_pending_stmts           /* flush_pending_stmts */
7459 };
7460
7461
7462 /* Split all critical edges.  */
7463
7464 static unsigned int
7465 split_critical_edges (void)
7466 {
7467   basic_block bb;
7468   edge e;
7469   edge_iterator ei;
7470
7471   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
7472      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
7473      mappings around the calls to split_edge.  */
7474   start_recording_case_labels ();
7475   FOR_ALL_BB (bb)
7476     {
7477       FOR_EACH_EDGE (e, ei, bb->succs)
7478         {
7479           if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
7480             split_edge (e);
7481           /* PRE inserts statements to edges and expects that
7482              since split_critical_edges was done beforehand, committing edge
7483              insertions will not split more edges.  In addition to critical
7484              edges we must split edges that have multiple successors and
7485              end by control flow statements, such as RESX.
7486              Go ahead and split them too.  This matches the logic in
7487              gimple_find_edge_insert_loc.  */
7488           else if ((!single_pred_p (e->dest)
7489                     || !gimple_seq_empty_p (phi_nodes (e->dest))
7490                     || e->dest == EXIT_BLOCK_PTR)
7491                    && e->src != ENTRY_BLOCK_PTR
7492                    && !(e->flags & EDGE_ABNORMAL))
7493             {
7494               gimple_stmt_iterator gsi;
7495
7496               gsi = gsi_last_bb (e->src);
7497               if (!gsi_end_p (gsi)
7498                   && stmt_ends_bb_p (gsi_stmt (gsi))
7499                   && gimple_code (gsi_stmt (gsi)) != GIMPLE_RETURN)
7500                 split_edge (e);
7501             }
7502         }
7503     }
7504   end_recording_case_labels ();
7505   return 0;
7506 }
7507
7508 struct gimple_opt_pass pass_split_crit_edges =
7509 {
7510  {
7511   GIMPLE_PASS,
7512   "crited",                          /* name */
7513   NULL,                          /* gate */
7514   split_critical_edges,          /* execute */
7515   NULL,                          /* sub */
7516   NULL,                          /* next */
7517   0,                             /* static_pass_number */
7518   TV_TREE_SPLIT_EDGES,           /* tv_id */
7519   PROP_cfg,                      /* properties required */
7520   PROP_no_crit_edges,            /* properties_provided */
7521   0,                             /* properties_destroyed */
7522   0,                             /* todo_flags_start */
7523   TODO_dump_func | TODO_verify_flow  /* todo_flags_finish */
7524  }
7525 };
7526
7527
7528 /* Build a ternary operation and gimplify it.  Emit code before GSI.
7529    Return the gimple_val holding the result.  */
7530
7531 tree
7532 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
7533                  tree type, tree a, tree b, tree c)
7534 {
7535   tree ret;
7536   location_t loc = gimple_location (gsi_stmt (*gsi));
7537
7538   ret = fold_build3_loc (loc, code, type, a, b, c);
7539   STRIP_NOPS (ret);
7540
7541   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7542                                    GSI_SAME_STMT);
7543 }
7544
7545 /* Build a binary operation and gimplify it.  Emit code before GSI.
7546    Return the gimple_val holding the result.  */
7547
7548 tree
7549 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
7550                  tree type, tree a, tree b)
7551 {
7552   tree ret;
7553
7554   ret = fold_build2_loc (gimple_location (gsi_stmt (*gsi)), code, type, a, b);
7555   STRIP_NOPS (ret);
7556
7557   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7558                                    GSI_SAME_STMT);
7559 }
7560
7561 /* Build a unary operation and gimplify it.  Emit code before GSI.
7562    Return the gimple_val holding the result.  */
7563
7564 tree
7565 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
7566                  tree a)
7567 {
7568   tree ret;
7569
7570   ret = fold_build1_loc (gimple_location (gsi_stmt (*gsi)), code, type, a);
7571   STRIP_NOPS (ret);
7572
7573   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7574                                    GSI_SAME_STMT);
7575 }
7576
7577
7578 \f
7579 /* Emit return warnings.  */
7580
7581 static unsigned int
7582 execute_warn_function_return (void)
7583 {
7584   source_location location;
7585   gimple last;
7586   edge e;
7587   edge_iterator ei;
7588
7589   /* If we have a path to EXIT, then we do return.  */
7590   if (TREE_THIS_VOLATILE (cfun->decl)
7591       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
7592     {
7593       location = UNKNOWN_LOCATION;
7594       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7595         {
7596           last = last_stmt (e->src);
7597           if (gimple_code (last) == GIMPLE_RETURN
7598               && (location = gimple_location (last)) != UNKNOWN_LOCATION)
7599             break;
7600         }
7601       if (location == UNKNOWN_LOCATION)
7602         location = cfun->function_end_locus;
7603       warning_at (location, 0, "%<noreturn%> function does return");
7604     }
7605
7606   /* If we see "return;" in some basic block, then we do reach the end
7607      without returning a value.  */
7608   else if (warn_return_type
7609            && !TREE_NO_WARNING (cfun->decl)
7610            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
7611            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
7612     {
7613       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7614         {
7615           gimple last = last_stmt (e->src);
7616           if (gimple_code (last) == GIMPLE_RETURN
7617               && gimple_return_retval (last) == NULL
7618               && !gimple_no_warning_p (last))
7619             {
7620               location = gimple_location (last);
7621               if (location == UNKNOWN_LOCATION)
7622                   location = cfun->function_end_locus;
7623               warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
7624               TREE_NO_WARNING (cfun->decl) = 1;
7625               break;
7626             }
7627         }
7628     }
7629   return 0;
7630 }
7631
7632
7633 /* Given a basic block B which ends with a conditional and has
7634    precisely two successors, determine which of the edges is taken if
7635    the conditional is true and which is taken if the conditional is
7636    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
7637
7638 void
7639 extract_true_false_edges_from_block (basic_block b,
7640                                      edge *true_edge,
7641                                      edge *false_edge)
7642 {
7643   edge e = EDGE_SUCC (b, 0);
7644
7645   if (e->flags & EDGE_TRUE_VALUE)
7646     {
7647       *true_edge = e;
7648       *false_edge = EDGE_SUCC (b, 1);
7649     }
7650   else
7651     {
7652       *false_edge = e;
7653       *true_edge = EDGE_SUCC (b, 1);
7654     }
7655 }
7656
7657 struct gimple_opt_pass pass_warn_function_return =
7658 {
7659  {
7660   GIMPLE_PASS,
7661   NULL,                                 /* name */
7662   NULL,                                 /* gate */
7663   execute_warn_function_return,         /* execute */
7664   NULL,                                 /* sub */
7665   NULL,                                 /* next */
7666   0,                                    /* static_pass_number */
7667   TV_NONE,                              /* tv_id */
7668   PROP_cfg,                             /* properties_required */
7669   0,                                    /* properties_provided */
7670   0,                                    /* properties_destroyed */
7671   0,                                    /* todo_flags_start */
7672   0                                     /* todo_flags_finish */
7673  }
7674 };
7675
7676 /* Emit noreturn warnings.  */
7677
7678 static unsigned int
7679 execute_warn_function_noreturn (void)
7680 {
7681   if (warn_missing_noreturn
7682       && !TREE_THIS_VOLATILE (cfun->decl)
7683       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
7684       && !lang_hooks.missing_noreturn_ok_p (cfun->decl))
7685     warning_at (DECL_SOURCE_LOCATION (cfun->decl), OPT_Wmissing_noreturn,
7686                 "function might be possible candidate "
7687                 "for attribute %<noreturn%>");
7688   return 0;
7689 }
7690
7691 struct gimple_opt_pass pass_warn_function_noreturn =
7692 {
7693  {
7694   GIMPLE_PASS,
7695   NULL,                                 /* name */
7696   NULL,                                 /* gate */
7697   execute_warn_function_noreturn,       /* execute */
7698   NULL,                                 /* sub */
7699   NULL,                                 /* next */
7700   0,                                    /* static_pass_number */
7701   TV_NONE,                              /* tv_id */
7702   PROP_cfg,                             /* properties_required */
7703   0,                                    /* properties_provided */
7704   0,                                    /* properties_destroyed */
7705   0,                                    /* todo_flags_start */
7706   0                                     /* todo_flags_finish */
7707  }
7708 };
7709
7710
7711 /* Walk a gimplified function and warn for functions whose return value is
7712    ignored and attribute((warn_unused_result)) is set.  This is done before
7713    inlining, so we don't have to worry about that.  */
7714
7715 static void
7716 do_warn_unused_result (gimple_seq seq)
7717 {
7718   tree fdecl, ftype;
7719   gimple_stmt_iterator i;
7720
7721   for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
7722     {
7723       gimple g = gsi_stmt (i);
7724
7725       switch (gimple_code (g))
7726         {
7727         case GIMPLE_BIND:
7728           do_warn_unused_result (gimple_bind_body (g));
7729           break;
7730         case GIMPLE_TRY:
7731           do_warn_unused_result (gimple_try_eval (g));
7732           do_warn_unused_result (gimple_try_cleanup (g));
7733           break;
7734         case GIMPLE_CATCH:
7735           do_warn_unused_result (gimple_catch_handler (g));
7736           break;
7737         case GIMPLE_EH_FILTER:
7738           do_warn_unused_result (gimple_eh_filter_failure (g));
7739           break;
7740
7741         case GIMPLE_CALL:
7742           if (gimple_call_lhs (g))
7743             break;
7744
7745           /* This is a naked call, as opposed to a GIMPLE_CALL with an
7746              LHS.  All calls whose value is ignored should be
7747              represented like this.  Look for the attribute.  */
7748           fdecl = gimple_call_fndecl (g);
7749           ftype = TREE_TYPE (TREE_TYPE (gimple_call_fn (g)));
7750
7751           if (lookup_attribute ("warn_unused_result", TYPE_ATTRIBUTES (ftype)))
7752             {
7753               location_t loc = gimple_location (g);
7754
7755               if (fdecl)
7756                 warning_at (loc, OPT_Wunused_result,
7757                             "ignoring return value of %qD, "
7758                             "declared with attribute warn_unused_result",
7759                             fdecl);
7760               else
7761                 warning_at (loc, OPT_Wunused_result,
7762                             "ignoring return value of function "
7763                             "declared with attribute warn_unused_result");
7764             }
7765           break;
7766
7767         default:
7768           /* Not a container, not a call, or a call whose value is used.  */
7769           break;
7770         }
7771     }
7772 }
7773
7774 static unsigned int
7775 run_warn_unused_result (void)
7776 {
7777   do_warn_unused_result (gimple_body (current_function_decl));
7778   return 0;
7779 }
7780
7781 static bool
7782 gate_warn_unused_result (void)
7783 {
7784   return flag_warn_unused_result;
7785 }
7786
7787 struct gimple_opt_pass pass_warn_unused_result =
7788 {
7789   {
7790     GIMPLE_PASS,
7791     "*warn_unused_result",              /* name */
7792     gate_warn_unused_result,            /* gate */
7793     run_warn_unused_result,             /* execute */
7794     NULL,                               /* sub */
7795     NULL,                               /* next */
7796     0,                                  /* static_pass_number */
7797     TV_NONE,                            /* tv_id */
7798     PROP_gimple_any,                    /* properties_required */
7799     0,                                  /* properties_provided */
7800     0,                                  /* properties_destroyed */
7801     0,                                  /* todo_flags_start */
7802     0,                                  /* todo_flags_finish */
7803   }
7804 };
7805