gcc/tree-cfg.c

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