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;
3814
3815       if (!is_gimple_call_addr (gimple_call_fn (stmt)))
3816         {
3817           error ("invalid function in call statement");
3818           return true;
3819         }
3820
3821       decl = gimple_call_fndecl (stmt);
3822       if (decl
3823           && TREE_CODE (decl) == FUNCTION_DECL
3824           && DECL_LOOPING_CONST_OR_PURE_P (decl)
3825           && (!DECL_PURE_P (decl))
3826           && (!TREE_READONLY (decl)))
3827         {
3828           error ("invalid pure const state for function");
3829           return true;
3830         }
3831     }
3832
3833   memset (&wi, 0, sizeof (wi));
3834   addr = walk_gimple_op (gsi_stmt (*gsi), verify_expr, &wi);
3835   if (addr)
3836     {
3837       debug_generic_expr (addr);
3838       inform ("in statement");
3839       debug_gimple_stmt (stmt);
3840       return true;
3841     }
3842
3843   /* If the statement is marked as part of an EH region, then it is
3844      expected that the statement could throw.  Verify that when we
3845      have optimizations that simplify statements such that we prove
3846      that they cannot throw, that we update other data structures
3847      to match.  */
3848   if (lookup_stmt_eh_region (stmt) >= 0)
3849     {
3850       if (!stmt_could_throw_p (stmt))
3851         {
3852           error ("statement marked for throw, but doesn%'t");
3853           goto fail;
3854         }
3855       if (!last_in_block && stmt_can_throw_internal (stmt))
3856         {
3857           error ("statement marked for throw in middle of block");
3858           goto fail;
3859         }
3860     }
3861
3862   return false;
3863
3864  fail:
3865   debug_gimple_stmt (stmt);
3866   return true;
3867 }
3868
3869
3870 /* Return true when the T can be shared.  */
3871
3872 static bool
3873 tree_node_can_be_shared (tree t)
3874 {
3875   if (IS_TYPE_OR_DECL_P (t)
3876       || is_gimple_min_invariant (t)
3877       || TREE_CODE (t) == SSA_NAME
3878       || t == error_mark_node
3879       || TREE_CODE (t) == IDENTIFIER_NODE)
3880     return true;
3881
3882   if (TREE_CODE (t) == CASE_LABEL_EXPR)
3883     return true;
3884
3885   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3886            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
3887          || TREE_CODE (t) == COMPONENT_REF
3888          || TREE_CODE (t) == REALPART_EXPR
3889          || TREE_CODE (t) == IMAGPART_EXPR)
3890     t = TREE_OPERAND (t, 0);
3891
3892   if (DECL_P (t))
3893     return true;
3894
3895   return false;
3896 }
3897
3898
3899 /* Called via walk_gimple_stmt.  Verify tree sharing.  */
3900
3901 static tree
3902 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
3903 {
3904   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
3905   struct pointer_set_t *visited = (struct pointer_set_t *) wi->info;
3906
3907   if (tree_node_can_be_shared (*tp))
3908     {
3909       *walk_subtrees = false;
3910       return NULL;
3911     }
3912
3913   if (pointer_set_insert (visited, *tp))
3914     return *tp;
3915
3916   return NULL;
3917 }
3918
3919
3920 static bool eh_error_found;
3921 static int
3922 verify_eh_throw_stmt_node (void **slot, void *data)
3923 {
3924   struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
3925   struct pointer_set_t *visited = (struct pointer_set_t *) data;
3926
3927   if (!pointer_set_contains (visited, node->stmt))
3928     {
3929       error ("Dead STMT in EH table");
3930       debug_gimple_stmt (node->stmt);
3931       eh_error_found = true;
3932     }
3933   return 0;
3934 }
3935
3936
3937 /* Verify the GIMPLE statements in every basic block.  */
3938
3939 void
3940 verify_stmts (void)
3941 {
3942   basic_block bb;
3943   gimple_stmt_iterator gsi;
3944   bool err = false;
3945   struct pointer_set_t *visited, *visited_stmts;
3946   tree addr;
3947   struct walk_stmt_info wi;
3948
3949   timevar_push (TV_TREE_STMT_VERIFY);
3950   visited = pointer_set_create ();
3951   visited_stmts = pointer_set_create ();
3952
3953   memset (&wi, 0, sizeof (wi));
3954   wi.info = (void *) visited;
3955
3956   FOR_EACH_BB (bb)
3957     {
3958       gimple phi;
3959       size_t i;
3960
3961       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3962         {
3963           phi = gsi_stmt (gsi);
3964           pointer_set_insert (visited_stmts, phi);
3965           if (gimple_bb (phi) != bb)
3966             {
3967               error ("gimple_bb (phi) is set to a wrong basic block");
3968               err |= true;
3969             }
3970
3971           for (i = 0; i < gimple_phi_num_args (phi); i++)
3972             {
3973               tree t = gimple_phi_arg_def (phi, i);
3974               tree addr;
3975
3976               if (!t)
3977                 {
3978                   error ("missing PHI def");
3979                   debug_gimple_stmt (phi);
3980                   err |= true;
3981                   continue;
3982                 }
3983               /* Addressable variables do have SSA_NAMEs but they
3984                  are not considered gimple values.  */
3985               else if (TREE_CODE (t) != SSA_NAME
3986                        && TREE_CODE (t) != FUNCTION_DECL
3987                        && !is_gimple_min_invariant (t))
3988                 {
3989                   error ("PHI argument is not a GIMPLE value");
3990                   debug_gimple_stmt (phi);
3991                   debug_generic_expr (t);
3992                   err |= true;
3993                 }
3994
3995               addr = walk_tree (&t, verify_node_sharing, visited, NULL);
3996               if (addr)
3997                 {
3998                   error ("incorrect sharing of tree nodes");
3999                   debug_gimple_stmt (phi);
4000                   debug_generic_expr (addr);
4001                   err |= true;
4002                 }
4003             }
4004         }
4005
4006       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
4007         {
4008           gimple stmt = gsi_stmt (gsi);
4009
4010           if (gimple_code (stmt) == GIMPLE_WITH_CLEANUP_EXPR
4011               || gimple_code (stmt) == GIMPLE_BIND)
4012             {
4013               error ("invalid GIMPLE statement");
4014               debug_gimple_stmt (stmt);
4015               err |= true;
4016             }
4017
4018           pointer_set_insert (visited_stmts, stmt);
4019
4020           if (gimple_bb (stmt) != bb)
4021             {
4022               error ("gimple_bb (stmt) is set to a wrong basic block");
4023               err |= true;
4024             }
4025
4026           if (gimple_code (stmt) == GIMPLE_LABEL)
4027             {
4028               tree decl = gimple_label_label (stmt);
4029               int uid = LABEL_DECL_UID (decl);
4030
4031               if (uid == -1
4032                   || VEC_index (basic_block, label_to_block_map, uid) != bb)
4033                 {
4034                   error ("incorrect entry in label_to_block_map.\n");
4035                   err |= true;
4036                 }
4037             }
4038
4039           err |= verify_stmt (&gsi);
4040           addr = walk_gimple_op (gsi_stmt (gsi), verify_node_sharing, &wi);
4041           if (addr)
4042             {
4043               error ("incorrect sharing of tree nodes");
4044               debug_gimple_stmt (stmt);
4045               debug_generic_expr (addr);
4046               err |= true;
4047             }
4048           gsi_next (&gsi);
4049         }
4050     }
4051
4052   eh_error_found = false;
4053   if (get_eh_throw_stmt_table (cfun))
4054     htab_traverse (get_eh_throw_stmt_table (cfun),
4055                    verify_eh_throw_stmt_node,
4056                    visited_stmts);
4057
4058   if (err | eh_error_found)
4059     internal_error ("verify_stmts failed");
4060
4061   pointer_set_destroy (visited);
4062   pointer_set_destroy (visited_stmts);
4063   verify_histograms ();
4064   timevar_pop (TV_TREE_STMT_VERIFY);
4065 }
4066
4067
4068 /* Verifies that the flow information is OK.  */
4069
4070 static int
4071 gimple_verify_flow_info (void)
4072 {
4073   int err = 0;
4074   basic_block bb;
4075   gimple_stmt_iterator gsi;
4076   gimple stmt;
4077   edge e;
4078   edge_iterator ei;
4079
4080   if (ENTRY_BLOCK_PTR->il.gimple)
4081     {
4082       error ("ENTRY_BLOCK has IL associated with it");
4083       err = 1;
4084     }
4085
4086   if (EXIT_BLOCK_PTR->il.gimple)
4087     {
4088       error ("EXIT_BLOCK has IL associated with it");
4089       err = 1;
4090     }
4091
4092   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4093     if (e->flags & EDGE_FALLTHRU)
4094       {
4095         error ("fallthru to exit from bb %d", e->src->index);
4096         err = 1;
4097       }
4098
4099   FOR_EACH_BB (bb)
4100     {
4101       bool found_ctrl_stmt = false;
4102
4103       stmt = NULL;
4104
4105       /* Skip labels on the start of basic block.  */
4106       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4107         {
4108           tree label;
4109           gimple prev_stmt = stmt;
4110
4111           stmt = gsi_stmt (gsi);
4112
4113           if (gimple_code (stmt) != GIMPLE_LABEL)
4114             break;
4115
4116           label = gimple_label_label (stmt);
4117           if (prev_stmt && DECL_NONLOCAL (label))
4118             {
4119               error ("nonlocal label ");
4120               print_generic_expr (stderr, label, 0);
4121               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4122                        bb->index);
4123               err = 1;
4124             }
4125
4126           if (label_to_block (label) != bb)
4127             {
4128               error ("label ");
4129               print_generic_expr (stderr, label, 0);
4130               fprintf (stderr, " to block does not match in bb %d",
4131                        bb->index);
4132               err = 1;
4133             }
4134
4135           if (decl_function_context (label) != current_function_decl)
4136             {
4137               error ("label ");
4138               print_generic_expr (stderr, label, 0);
4139               fprintf (stderr, " has incorrect context in bb %d",
4140                        bb->index);
4141               err = 1;
4142             }
4143         }
4144
4145       /* Verify that body of basic block BB is free of control flow.  */
4146       for (; !gsi_end_p (gsi); gsi_next (&gsi))
4147         {
4148           gimple stmt = gsi_stmt (gsi);
4149
4150           if (found_ctrl_stmt)
4151             {
4152               error ("control flow in the middle of basic block %d",
4153                      bb->index);
4154               err = 1;
4155             }
4156
4157           if (stmt_ends_bb_p (stmt))
4158             found_ctrl_stmt = true;
4159
4160           if (gimple_code (stmt) == GIMPLE_LABEL)
4161             {
4162               error ("label ");
4163               print_generic_expr (stderr, gimple_label_label (stmt), 0);
4164               fprintf (stderr, " in the middle of basic block %d", bb->index);
4165               err = 1;
4166             }
4167         }
4168
4169       gsi = gsi_last_bb (bb);
4170       if (gsi_end_p (gsi))
4171         continue;
4172
4173       stmt = gsi_stmt (gsi);
4174
4175       err |= verify_eh_edges (stmt);
4176
4177       if (is_ctrl_stmt (stmt))
4178         {
4179           FOR_EACH_EDGE (e, ei, bb->succs)
4180             if (e->flags & EDGE_FALLTHRU)
4181               {
4182                 error ("fallthru edge after a control statement in bb %d",
4183                        bb->index);
4184                 err = 1;
4185               }
4186         }
4187
4188       if (gimple_code (stmt) != GIMPLE_COND)
4189         {
4190           /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4191              after anything else but if statement.  */
4192           FOR_EACH_EDGE (e, ei, bb->succs)
4193             if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4194               {
4195                 error ("true/false edge after a non-GIMPLE_COND in bb %d",
4196                        bb->index);
4197                 err = 1;
4198               }
4199         }
4200
4201       switch (gimple_code (stmt))
4202         {
4203         case GIMPLE_COND:
4204           {
4205             edge true_edge;
4206             edge false_edge;
4207
4208             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4209
4210             if (!true_edge
4211                 || !false_edge
4212                 || !(true_edge->flags & EDGE_TRUE_VALUE)
4213                 || !(false_edge->flags & EDGE_FALSE_VALUE)
4214                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4215                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4216                 || EDGE_COUNT (bb->succs) >= 3)
4217               {
4218                 error ("wrong outgoing edge flags at end of bb %d",
4219                        bb->index);
4220                 err = 1;
4221               }
4222           }
4223           break;
4224
4225         case GIMPLE_GOTO:
4226           if (simple_goto_p (stmt))
4227             {
4228               error ("explicit goto at end of bb %d", bb->index);
4229               err = 1;
4230             }
4231           else
4232             {
4233               /* FIXME.  We should double check that the labels in the
4234                  destination blocks have their address taken.  */
4235               FOR_EACH_EDGE (e, ei, bb->succs)
4236                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4237                                  | EDGE_FALSE_VALUE))
4238                     || !(e->flags & EDGE_ABNORMAL))
4239                   {
4240                     error ("wrong outgoing edge flags at end of bb %d",
4241                            bb->index);
4242                     err = 1;
4243                   }
4244             }
4245           break;
4246
4247         case GIMPLE_RETURN:
4248           if (!single_succ_p (bb)
4249               || (single_succ_edge (bb)->flags
4250                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
4251                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4252             {
4253               error ("wrong outgoing edge flags at end of bb %d", bb->index);
4254               err = 1;
4255             }
4256           if (single_succ (bb) != EXIT_BLOCK_PTR)
4257             {
4258               error ("return edge does not point to exit in bb %d",
4259                      bb->index);
4260               err = 1;
4261             }
4262           break;
4263
4264         case GIMPLE_SWITCH:
4265           {
4266             tree prev;
4267             edge e;
4268             size_t i, n;
4269
4270             n = gimple_switch_num_labels (stmt);
4271
4272             /* Mark all the destination basic blocks.  */
4273             for (i = 0; i < n; ++i)
4274               {
4275                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4276                 basic_block label_bb = label_to_block (lab);
4277                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4278                 label_bb->aux = (void *)1;
4279               }
4280
4281             /* Verify that the case labels are sorted.  */
4282             prev = gimple_switch_label (stmt, 0);
4283             for (i = 1; i < n; ++i)
4284               {
4285                 tree c = gimple_switch_label (stmt, i);
4286                 if (!CASE_LOW (c))
4287                   {
4288                     error ("found default case not at the start of "
4289                            "case vector");
4290                     err = 1;
4291                     continue;
4292                   }
4293                 if (CASE_LOW (prev)
4294                     && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4295                   {
4296                     error ("case labels not sorted: ");
4297                     print_generic_expr (stderr, prev, 0);
4298                     fprintf (stderr," is greater than ");
4299                     print_generic_expr (stderr, c, 0);
4300                     fprintf (stderr," but comes before it.\n");
4301                     err = 1;
4302                   }
4303                 prev = c;
4304               }
4305             /* VRP will remove the default case if it can prove it will
4306                never be executed.  So do not verify there always exists
4307                a default case here.  */
4308
4309             FOR_EACH_EDGE (e, ei, bb->succs)
4310               {
4311                 if (!e->dest->aux)
4312                   {
4313                     error ("extra outgoing edge %d->%d",
4314                            bb->index, e->dest->index);
4315                     err = 1;
4316                   }
4317
4318                 e->dest->aux = (void *)2;
4319                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
4320                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4321                   {
4322                     error ("wrong outgoing edge flags at end of bb %d",
4323                            bb->index);
4324                     err = 1;
4325                   }
4326               }
4327
4328             /* Check that we have all of them.  */
4329             for (i = 0; i < n; ++i)
4330               {
4331                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4332                 basic_block label_bb = label_to_block (lab);
4333
4334                 if (label_bb->aux != (void *)2)
4335                   {
4336                     error ("missing edge %i->%i", bb->index, label_bb->index);
4337                     err = 1;
4338                   }
4339               }
4340
4341             FOR_EACH_EDGE (e, ei, bb->succs)
4342               e->dest->aux = (void *)0;
4343           }
4344
4345         default: ;
4346         }
4347     }
4348
4349   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
4350     verify_dominators (CDI_DOMINATORS);
4351
4352   return err;
4353 }
4354
4355
4356 /* Updates phi nodes after creating a forwarder block joined
4357    by edge FALLTHRU.  */
4358
4359 static void
4360 gimple_make_forwarder_block (edge fallthru)
4361 {
4362   edge e;
4363   edge_iterator ei;
4364   basic_block dummy, bb;
4365   tree var;
4366   gimple_stmt_iterator gsi;
4367
4368   dummy = fallthru->src;
4369   bb = fallthru->dest;
4370
4371   if (single_pred_p (bb))
4372     return;
4373
4374   /* If we redirected a branch we must create new PHI nodes at the
4375      start of BB.  */
4376   for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
4377     {
4378       gimple phi, new_phi;
4379
4380       phi = gsi_stmt (gsi);
4381       var = gimple_phi_result (phi);
4382       new_phi = create_phi_node (var, bb);
4383       SSA_NAME_DEF_STMT (var) = new_phi;
4384       gimple_phi_set_result (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
4385       add_phi_arg (new_phi, gimple_phi_result (phi), fallthru);
4386     }
4387
4388   /* Add the arguments we have stored on edges.  */
4389   FOR_EACH_EDGE (e, ei, bb->preds)
4390     {
4391       if (e == fallthru)
4392         continue;
4393
4394       flush_pending_stmts (e);
4395     }
4396 }
4397
4398
4399 /* Return a non-special label in the head of basic block BLOCK.
4400    Create one if it doesn't exist.  */
4401
4402 tree
4403 gimple_block_label (basic_block bb)
4404 {
4405   gimple_stmt_iterator i, s = gsi_start_bb (bb);
4406   bool first = true;
4407   tree label;
4408   gimple stmt;
4409
4410   for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
4411     {
4412       stmt = gsi_stmt (i);
4413       if (gimple_code (stmt) != GIMPLE_LABEL)
4414         break;
4415       label = gimple_label_label (stmt);
4416       if (!DECL_NONLOCAL (label))
4417         {
4418           if (!first)
4419             gsi_move_before (&i, &s);
4420           return label;
4421         }
4422     }
4423
4424   label = create_artificial_label ();
4425   stmt = gimple_build_label (label);
4426   gsi_insert_before (&s, stmt, GSI_NEW_STMT);
4427   return label;
4428 }
4429
4430
4431 /* Attempt to perform edge redirection by replacing a possibly complex
4432    jump instruction by a goto or by removing the jump completely.
4433    This can apply only if all edges now point to the same block.  The
4434    parameters and return values are equivalent to
4435    redirect_edge_and_branch.  */
4436
4437 static edge
4438 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
4439 {
4440   basic_block src = e->src;
4441   gimple_stmt_iterator i;
4442   gimple stmt;
4443
4444   /* We can replace or remove a complex jump only when we have exactly
4445      two edges.  */
4446   if (EDGE_COUNT (src->succs) != 2
4447       /* Verify that all targets will be TARGET.  Specifically, the
4448          edge that is not E must also go to TARGET.  */
4449       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4450     return NULL;
4451
4452   i = gsi_last_bb (src);
4453   if (gsi_end_p (i))
4454     return NULL;
4455
4456   stmt = gsi_stmt (i);
4457
4458   if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
4459     {
4460       gsi_remove (&i, true);
4461       e = ssa_redirect_edge (e, target);
4462       e->flags = EDGE_FALLTHRU;
4463       return e;
4464     }
4465
4466   return NULL;
4467 }
4468
4469
4470 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4471    edge representing the redirected branch.  */
4472
4473 static edge
4474 gimple_redirect_edge_and_branch (edge e, basic_block dest)
4475 {
4476   basic_block bb = e->src;
4477   gimple_stmt_iterator gsi;
4478   edge ret;
4479   gimple stmt;
4480
4481   if (e->flags & EDGE_ABNORMAL)
4482     return NULL;
4483
4484   if (e->src != ENTRY_BLOCK_PTR
4485       && (ret = gimple_try_redirect_by_replacing_jump (e, dest)))
4486     return ret;
4487
4488   if (e->dest == dest)
4489     return NULL;
4490
4491   gsi = gsi_last_bb (bb);
4492   stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
4493
4494   switch (stmt ? gimple_code (stmt) : ERROR_MARK)
4495     {
4496     case GIMPLE_COND:
4497       /* For COND_EXPR, we only need to redirect the edge.  */
4498       break;
4499
4500     case GIMPLE_GOTO:
4501       /* No non-abnormal edges should lead from a non-simple goto, and
4502          simple ones should be represented implicitly.  */
4503       gcc_unreachable ();
4504
4505     case GIMPLE_SWITCH:
4506       {
4507         tree label = gimple_block_label (dest);
4508         tree cases = get_cases_for_edge (e, stmt);
4509
4510         /* If we have a list of cases associated with E, then use it
4511            as it's a lot faster than walking the entire case vector.  */
4512         if (cases)
4513           {
4514             edge e2 = find_edge (e->src, dest);
4515             tree last, first;
4516
4517             first = cases;
4518             while (cases)
4519               {
4520                 last = cases;
4521                 CASE_LABEL (cases) = label;
4522                 cases = TREE_CHAIN (cases);
4523               }
4524
4525             /* If there was already an edge in the CFG, then we need
4526                to move all the cases associated with E to E2.  */
4527             if (e2)
4528               {
4529                 tree cases2 = get_cases_for_edge (e2, stmt);
4530
4531                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4532                 TREE_CHAIN (cases2) = first;
4533               }
4534           }
4535         else
4536           {
4537             size_t i, n = gimple_switch_num_labels (stmt);
4538
4539             for (i = 0; i < n; i++)
4540               {
4541                 tree elt = gimple_switch_label (stmt, i);
4542                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4543                   CASE_LABEL (elt) = label;
4544               }
4545           }
4546
4547         break;
4548       }
4549
4550     case GIMPLE_RETURN:
4551       gsi_remove (&gsi, true);
4552       e->flags |= EDGE_FALLTHRU;
4553       break;
4554
4555     case GIMPLE_OMP_RETURN:
4556     case GIMPLE_OMP_CONTINUE:
4557     case GIMPLE_OMP_SECTIONS_SWITCH:
4558     case GIMPLE_OMP_FOR:
4559       /* The edges from OMP constructs can be simply redirected.  */
4560       break;
4561
4562     default:
4563       /* Otherwise it must be a fallthru edge, and we don't need to
4564          do anything besides redirecting it.  */
4565       gcc_assert (e->flags & EDGE_FALLTHRU);
4566       break;
4567     }
4568
4569   /* Update/insert PHI nodes as necessary.  */
4570
4571   /* Now update the edges in the CFG.  */
4572   e = ssa_redirect_edge (e, dest);
4573
4574   return e;
4575 }
4576
4577 /* Returns true if it is possible to remove edge E by redirecting
4578    it to the destination of the other edge from E->src.  */
4579
4580 static bool
4581 gimple_can_remove_branch_p (const_edge e)
4582 {
4583   if (e->flags & EDGE_ABNORMAL)
4584     return false;
4585
4586   return true;
4587 }
4588
4589 /* Simple wrapper, as we can always redirect fallthru edges.  */
4590
4591 static basic_block
4592 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
4593 {
4594   e = gimple_redirect_edge_and_branch (e, dest);
4595   gcc_assert (e);
4596
4597   return NULL;
4598 }
4599
4600
4601 /* Splits basic block BB after statement STMT (but at least after the
4602    labels).  If STMT is NULL, BB is split just after the labels.  */
4603
4604 static basic_block
4605 gimple_split_block (basic_block bb, void *stmt)
4606 {
4607   gimple_stmt_iterator gsi;
4608   gimple_stmt_iterator gsi_tgt;
4609   gimple act;
4610   gimple_seq list;
4611   basic_block new_bb;
4612   edge e;
4613   edge_iterator ei;
4614
4615   new_bb = create_empty_bb (bb);
4616
4617   /* Redirect the outgoing edges.  */
4618   new_bb->succs = bb->succs;
4619   bb->succs = NULL;
4620   FOR_EACH_EDGE (e, ei, new_bb->succs)
4621     e->src = new_bb;
4622
4623   if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
4624     stmt = NULL;
4625
4626   /* Move everything from GSI to the new basic block.  */
4627   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4628     {
4629       act = gsi_stmt (gsi);
4630       if (gimple_code (act) == GIMPLE_LABEL)
4631         continue;
4632
4633       if (!stmt)
4634         break;
4635
4636       if (stmt == act)
4637         {
4638           gsi_next (&gsi);
4639           break;
4640         }
4641     }
4642
4643   if (gsi_end_p (gsi))
4644     return new_bb;
4645
4646   /* Split the statement list - avoid re-creating new containers as this
4647      brings ugly quadratic memory consumption in the inliner.
4648      (We are still quadratic since we need to update stmt BB pointers,
4649      sadly.)  */
4650   list = gsi_split_seq_before (&gsi);
4651   set_bb_seq (new_bb, list);
4652   for (gsi_tgt = gsi_start (list);
4653        !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
4654     gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
4655
4656   return new_bb;
4657 }
4658
4659
4660 /* Moves basic block BB after block AFTER.  */
4661
4662 static bool
4663 gimple_move_block_after (basic_block bb, basic_block after)
4664 {
4665   if (bb->prev_bb == after)
4666     return true;
4667
4668   unlink_block (bb);
4669   link_block (bb, after);
4670
4671   return true;
4672 }
4673
4674
4675 /* Return true if basic_block can be duplicated.  */
4676
4677 static bool
4678 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
4679 {
4680   return true;
4681 }
4682
4683 /* Create a duplicate of the basic block BB.  NOTE: This does not
4684    preserve SSA form.  */
4685
4686 static basic_block
4687 gimple_duplicate_bb (basic_block bb)
4688 {
4689   basic_block new_bb;
4690   gimple_stmt_iterator gsi, gsi_tgt;
4691   gimple_seq phis = phi_nodes (bb);
4692   gimple phi, stmt, copy;
4693
4694   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4695
4696   /* Copy the PHI nodes.  We ignore PHI node arguments here because
4697      the incoming edges have not been setup yet.  */
4698   for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
4699     {
4700       phi = gsi_stmt (gsi);
4701       copy = create_phi_node (gimple_phi_result (phi), new_bb);
4702       create_new_def_for (gimple_phi_result (copy), copy,
4703                           gimple_phi_result_ptr (copy));
4704     }
4705
4706   gsi_tgt = gsi_start_bb (new_bb);
4707   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4708     {
4709       def_operand_p def_p;
4710       ssa_op_iter op_iter;
4711       int region;
4712
4713       stmt = gsi_stmt (gsi);
4714       if (gimple_code (stmt) == GIMPLE_LABEL)
4715         continue;
4716
4717       /* Create a new copy of STMT and duplicate STMT's virtual
4718          operands.  */
4719       copy = gimple_copy (stmt);
4720       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
4721       copy_virtual_operands (copy, stmt);
4722       region = lookup_stmt_eh_region (stmt);
4723       if (region >= 0)
4724         add_stmt_to_eh_region (copy, region);
4725       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
4726
4727       /* Create new names for all the definitions created by COPY and
4728          add replacement mappings for each new name.  */
4729       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
4730         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
4731     }
4732
4733   return new_bb;
4734 }
4735
4736 /* Adds phi node arguments for edge E_COPY after basic block duplication.  */
4737
4738 static void
4739 add_phi_args_after_copy_edge (edge e_copy)
4740 {
4741   basic_block bb, bb_copy = e_copy->src, dest;
4742   edge e;
4743   edge_iterator ei;
4744   gimple phi, phi_copy;
4745   tree def;
4746   gimple_stmt_iterator psi, psi_copy;
4747
4748   if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
4749     return;
4750
4751   bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
4752
4753   if (e_copy->dest->flags & BB_DUPLICATED)
4754     dest = get_bb_original (e_copy->dest);
4755   else
4756     dest = e_copy->dest;
4757
4758   e = find_edge (bb, dest);
4759   if (!e)
4760     {
4761       /* During loop unrolling the target of the latch edge is copied.
4762          In this case we are not looking for edge to dest, but to
4763          duplicated block whose original was dest.  */
4764       FOR_EACH_EDGE (e, ei, bb->succs)
4765         {
4766           if ((e->dest->flags & BB_DUPLICATED)
4767               && get_bb_original (e->dest) == dest)
4768             break;
4769         }
4770
4771       gcc_assert (e != NULL);
4772     }
4773
4774   for (psi = gsi_start_phis (e->dest),
4775        psi_copy = gsi_start_phis (e_copy->dest);
4776        !gsi_end_p (psi);
4777        gsi_next (&psi), gsi_next (&psi_copy))
4778     {
4779       phi = gsi_stmt (psi);
4780       phi_copy = gsi_stmt (psi_copy);
4781       def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4782       add_phi_arg (phi_copy, def, e_copy);
4783     }
4784 }
4785
4786
4787 /* Basic block BB_COPY was created by code duplication.  Add phi node
4788    arguments for edges going out of BB_COPY.  The blocks that were
4789    duplicated have BB_DUPLICATED set.  */
4790
4791 void
4792 add_phi_args_after_copy_bb (basic_block bb_copy)
4793 {
4794   edge e_copy;
4795   edge_iterator ei;
4796
4797   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
4798     {
4799       add_phi_args_after_copy_edge (e_copy);
4800     }
4801 }
4802
4803 /* Blocks in REGION_COPY array of length N_REGION were created by
4804    duplication of basic blocks.  Add phi node arguments for edges
4805    going from these blocks.  If E_COPY is not NULL, also add
4806    phi node arguments for its destination.*/
4807
4808 void
4809 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
4810                          edge e_copy)
4811 {
4812   unsigned i;
4813
4814   for (i = 0; i < n_region; i++)
4815     region_copy[i]->flags |= BB_DUPLICATED;
4816
4817   for (i = 0; i < n_region; i++)
4818     add_phi_args_after_copy_bb (region_copy[i]);
4819   if (e_copy)
4820     add_phi_args_after_copy_edge (e_copy);
4821
4822   for (i = 0; i < n_region; i++)
4823     region_copy[i]->flags &= ~BB_DUPLICATED;
4824 }
4825
4826 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
4827    important exit edge EXIT.  By important we mean that no SSA name defined
4828    inside region is live over the other exit edges of the region.  All entry
4829    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
4830    to the duplicate of the region.  SSA form, dominance and loop information
4831    is updated.  The new basic blocks are stored to REGION_COPY in the same
4832    order as they had in REGION, provided that REGION_COPY is not NULL.
4833    The function returns false if it is unable to copy the region,
4834    true otherwise.  */
4835
4836 bool
4837 gimple_duplicate_sese_region (edge entry, edge exit,
4838                             basic_block *region, unsigned n_region,
4839                             basic_block *region_copy)
4840 {
4841   unsigned i;
4842   bool free_region_copy = false, copying_header = false;
4843   struct loop *loop = entry->dest->loop_father;
4844   edge exit_copy;
4845   VEC (basic_block, heap) *doms;
4846   edge redirected;
4847   int total_freq = 0, entry_freq = 0;
4848   gcov_type total_count = 0, entry_count = 0;
4849
4850   if (!can_copy_bbs_p (region, n_region))
4851     return false;
4852
4853   /* Some sanity checking.  Note that we do not check for all possible
4854      missuses of the functions.  I.e. if you ask to copy something weird,
4855      it will work, but the state of structures probably will not be
4856      correct.  */
4857   for (i = 0; i < n_region; i++)
4858     {
4859       /* We do not handle subloops, i.e. all the blocks must belong to the
4860          same loop.  */
4861       if (region[i]->loop_father != loop)
4862         return false;
4863
4864       if (region[i] != entry->dest
4865           && region[i] == loop->header)
4866         return false;
4867     }
4868
4869   set_loop_copy (loop, loop);
4870
4871   /* In case the function is used for loop header copying (which is the primary
4872      use), ensure that EXIT and its copy will be new latch and entry edges.  */
4873   if (loop->header == entry->dest)
4874     {
4875       copying_header = true;
4876       set_loop_copy (loop, loop_outer (loop));
4877
4878       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
4879         return false;
4880
4881       for (i = 0; i < n_region; i++)
4882         if (region[i] != exit->src
4883             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
4884           return false;
4885     }
4886
4887   if (!region_copy)
4888     {
4889       region_copy = XNEWVEC (basic_block, n_region);
4890       free_region_copy = true;
4891     }
4892
4893   gcc_assert (!need_ssa_update_p ());
4894
4895   /* Record blocks outside the region that are dominated by something
4896      inside.  */
4897   doms = NULL;
4898   initialize_original_copy_tables ();
4899
4900   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
4901
4902   if (entry->dest->count)
4903     {
4904       total_count = entry->dest->count;
4905       entry_count = entry->count;
4906       /* Fix up corner cases, to avoid division by zero or creation of negative
4907          frequencies.  */
4908       if (entry_count > total_count)
4909         entry_count = total_count;
4910     }
4911   else
4912     {
4913       total_freq = entry->dest->frequency;
4914       entry_freq = EDGE_FREQUENCY (entry);
4915       /* Fix up corner cases, to avoid division by zero or creation of negative
4916          frequencies.  */
4917       if (total_freq == 0)
4918         total_freq = 1;
4919       else if (entry_freq > total_freq)
4920         entry_freq = total_freq;
4921     }
4922
4923   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
4924             split_edge_bb_loc (entry));
4925   if (total_count)
4926     {
4927       scale_bbs_frequencies_gcov_type (region, n_region,
4928                                        total_count - entry_count,
4929                                        total_count);
4930       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
4931                                        total_count);
4932     }
4933   else
4934     {
4935       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
4936                                  total_freq);
4937       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
4938     }
4939
4940   if (copying_header)
4941     {
4942       loop->header = exit->dest;
4943       loop->latch = exit->src;
4944     }
4945
4946   /* Redirect the entry and add the phi node arguments.  */
4947   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
4948   gcc_assert (redirected != NULL);
4949   flush_pending_stmts (entry);
4950
4951   /* Concerning updating of dominators:  We must recount dominators
4952      for entry block and its copy.  Anything that is outside of the
4953      region, but was dominated by something inside needs recounting as
4954      well.  */
4955   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
4956   VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
4957   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
4958   VEC_free (basic_block, heap, doms);
4959
4960   /* Add the other PHI node arguments.  */
4961   add_phi_args_after_copy (region_copy, n_region, NULL);
4962
4963   /* Update the SSA web.  */
4964   update_ssa (TODO_update_ssa);
4965
4966   if (free_region_copy)
4967     free (region_copy);
4968
4969   free_original_copy_tables ();
4970   return true;
4971 }
4972
4973 /* Duplicates REGION consisting of N_REGION blocks.  The new blocks
4974    are stored to REGION_COPY in the same order in that they appear
4975    in REGION, if REGION_COPY is not NULL.  ENTRY is the entry to
4976    the region, EXIT an exit from it.  The condition guarding EXIT
4977    is moved to ENTRY.  Returns true if duplication succeeds, false
4978    otherwise.
4979
4980    For example,
4981
4982    some_code;
4983    if (cond)
4984      A;
4985    else
4986      B;
4987
4988    is transformed to
4989
4990    if (cond)
4991      {
4992        some_code;
4993        A;
4994      }
4995    else
4996      {
4997        some_code;
4998        B;
4999      }
5000 */
5001
5002 bool
5003 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
5004                           basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
5005                           basic_block *region_copy ATTRIBUTE_UNUSED)
5006 {
5007   unsigned i;
5008   bool free_region_copy = false;
5009   struct loop *loop = exit->dest->loop_father;
5010   struct loop *orig_loop = entry->dest->loop_father;
5011   basic_block switch_bb, entry_bb, nentry_bb;
5012   VEC (basic_block, heap) *doms;
5013   int total_freq = 0, exit_freq = 0;
5014   gcov_type total_count = 0, exit_count = 0;
5015   edge exits[2], nexits[2], e;
5016   gimple_stmt_iterator gsi;
5017   gimple cond_stmt;
5018   edge sorig, snew;
5019
5020   gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5021   exits[0] = exit;
5022   exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5023
5024   if (!can_copy_bbs_p (region, n_region))
5025     return false;
5026
5027   /* Some sanity checking.  Note that we do not check for all possible
5028      missuses of the functions.  I.e. if you ask to copy something weird
5029      (e.g., in the example, if there is a jump from inside to the middle
5030      of some_code, or come_code defines some of the values used in cond)
5031      it will work, but the resulting code will not be correct.  */
5032   for (i = 0; i < n_region; i++)
5033     {
5034       /* We do not handle subloops, i.e. all the blocks must belong to the
5035          same loop.  */
5036       if (region[i]->loop_father != orig_loop)
5037         return false;
5038
5039       if (region[i] == orig_loop->latch)
5040         return false;
5041     }
5042
5043   initialize_original_copy_tables ();
5044   set_loop_copy (orig_loop, loop);
5045
5046   if (!region_copy)
5047     {
5048       region_copy = XNEWVEC (basic_block, n_region);
5049       free_region_copy = true;
5050     }
5051
5052   gcc_assert (!need_ssa_update_p ());
5053
5054   /* Record blocks outside the region that are dominated by something
5055      inside.  */
5056   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5057
5058   if (exit->src->count)
5059     {
5060       total_count = exit->src->count;
5061       exit_count = exit->count;
5062       /* Fix up corner cases, to avoid division by zero or creation of negative
5063          frequencies.  */
5064       if (exit_count > total_count)
5065         exit_count = total_count;
5066     }
5067   else
5068     {
5069       total_freq = exit->src->frequency;
5070       exit_freq = EDGE_FREQUENCY (exit);
5071       /* Fix up corner cases, to avoid division by zero or creation of negative
5072          frequencies.  */
5073       if (total_freq == 0)
5074         total_freq = 1;
5075       if (exit_freq > total_freq)
5076         exit_freq = total_freq;
5077     }
5078
5079   copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5080             split_edge_bb_loc (exit));
5081   if (total_count)
5082     {
5083       scale_bbs_frequencies_gcov_type (region, n_region,
5084                                        total_count - exit_count,
5085                                        total_count);
5086       scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5087                                        total_count);
5088     }
5089   else
5090     {
5091       scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5092                                  total_freq);
5093       scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5094     }
5095
5096   /* Create the switch block, and put the exit condition to it.  */
5097   entry_bb = entry->dest;
5098   nentry_bb = get_bb_copy (entry_bb);
5099   if (!last_stmt (entry->src)
5100       || !stmt_ends_bb_p (last_stmt (entry->src)))
5101     switch_bb = entry->src;
5102   else
5103     switch_bb = split_edge (entry);
5104   set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5105
5106   gsi = gsi_last_bb (switch_bb);
5107   cond_stmt = last_stmt (exit->src);
5108   gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
5109   cond_stmt = gimple_copy (cond_stmt);
5110   gimple_cond_set_lhs (cond_stmt, unshare_expr (gimple_cond_lhs (cond_stmt)));
5111   gimple_cond_set_rhs (cond_stmt, unshare_expr (gimple_cond_rhs (cond_stmt)));
5112   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
5113
5114   sorig = single_succ_edge (switch_bb);
5115   sorig->flags = exits[1]->flags;
5116   snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5117
5118   /* Register the new edge from SWITCH_BB in loop exit lists.  */
5119   rescan_loop_exit (snew, true, false);
5120
5121   /* Add the PHI node arguments.  */
5122   add_phi_args_after_copy (region_copy, n_region, snew);
5123
5124   /* Get rid of now superfluous conditions and associated edges (and phi node
5125      arguments).  */
5126   e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5127   PENDING_STMT (e) = NULL;
5128   e = redirect_edge_and_branch (nexits[1], nexits[0]->dest);
5129   PENDING_STMT (e) = NULL;
5130
5131   /* Anything that is outside of the region, but was dominated by something
5132      inside needs to update dominance info.  */
5133   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5134   VEC_free (basic_block, heap, doms);
5135
5136   /* Update the SSA web.  */
5137   update_ssa (TODO_update_ssa);
5138
5139   if (free_region_copy)
5140     free (region_copy);
5141
5142   free_original_copy_tables ();
5143   return true;
5144 }
5145
5146 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
5147    adding blocks when the dominator traversal reaches EXIT.  This
5148    function silently assumes that ENTRY strictly dominates EXIT.  */
5149
5150 void
5151 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5152                               VEC(basic_block,heap) **bbs_p)
5153 {
5154   basic_block son;
5155
5156   for (son = first_dom_son (CDI_DOMINATORS, entry);
5157        son;
5158        son = next_dom_son (CDI_DOMINATORS, son))
5159     {
5160       VEC_safe_push (basic_block, heap, *bbs_p, son);
5161       if (son != exit)
5162         gather_blocks_in_sese_region (son, exit, bbs_p);
5163     }
5164 }
5165
5166 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5167    The duplicates are recorded in VARS_MAP.  */
5168
5169 static void
5170 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5171                            tree to_context)
5172 {
5173   tree t = *tp, new_t;
5174   struct function *f = DECL_STRUCT_FUNCTION (to_context);
5175   void **loc;
5176
5177   if (DECL_CONTEXT (t) == to_context)
5178     return;
5179
5180   loc = pointer_map_contains (vars_map, t);
5181
5182   if (!loc)
5183     {
5184       loc = pointer_map_insert (vars_map, t);
5185
5186       if (SSA_VAR_P (t))
5187         {
5188           new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5189           f->local_decls = tree_cons (NULL_TREE, new_t, f->local_decls);
5190         }
5191       else
5192         {
5193           gcc_assert (TREE_CODE (t) == CONST_DECL);
5194           new_t = copy_node (t);
5195         }
5196       DECL_CONTEXT (new_t) = to_context;
5197
5198       *loc = new_t;
5199     }
5200   else
5201     new_t = (tree) *loc;
5202
5203   *tp = new_t;
5204 }
5205
5206
5207 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5208    VARS_MAP maps old ssa names and var_decls to the new ones.  */
5209
5210 static tree
5211 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5212                   tree to_context)
5213 {
5214   void **loc;
5215   tree new_name, decl = SSA_NAME_VAR (name);
5216
5217   gcc_assert (is_gimple_reg (name));
5218
5219   loc = pointer_map_contains (vars_map, name);
5220
5221   if (!loc)
5222     {
5223       replace_by_duplicate_decl (&decl, vars_map, to_context);
5224
5225       push_cfun (DECL_STRUCT_FUNCTION (to_context));
5226       if (gimple_in_ssa_p (cfun))
5227         add_referenced_var (decl);
5228
5229       new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5230       if (SSA_NAME_IS_DEFAULT_DEF (name))
5231         set_default_def (decl, new_name);
5232       pop_cfun ();
5233
5234       loc = pointer_map_insert (vars_map, name);
5235       *loc = new_name;
5236     }
5237   else
5238     new_name = (tree) *loc;
5239
5240   return new_name;
5241 }
5242
5243 struct move_stmt_d
5244 {
5245   tree orig_block;
5246   tree new_block;
5247   tree from_context;
5248   tree to_context;
5249   struct pointer_map_t *vars_map;
5250   htab_t new_label_map;
5251   bool remap_decls_p;
5252 };
5253
5254 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
5255    contained in *TP if it has been ORIG_BLOCK previously and change the
5256    DECL_CONTEXT of every local variable referenced in *TP.  */
5257
5258 static tree
5259 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
5260 {
5261   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
5262   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5263   tree t = *tp;
5264
5265   if (EXPR_P (t))
5266     /* We should never have TREE_BLOCK set on non-statements.  */
5267     gcc_assert (!TREE_BLOCK (t));
5268
5269   else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
5270     {
5271       if (TREE_CODE (t) == SSA_NAME)
5272         *tp = replace_ssa_name (t, p->vars_map, p->to_context);
5273       else if (TREE_CODE (t) == LABEL_DECL)
5274         {
5275           if (p->new_label_map)
5276             {
5277               struct tree_map in, *out;
5278               in.base.from = t;
5279               out = (struct tree_map *)
5280                 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
5281               if (out)
5282                 *tp = t = out->to;
5283             }
5284
5285           DECL_CONTEXT (t) = p->to_context;
5286         }
5287       else if (p->remap_decls_p)
5288         {
5289           /* Replace T with its duplicate.  T should no longer appear in the
5290              parent function, so this looks wasteful; however, it may appear
5291              in referenced_vars, and more importantly, as virtual operands of
5292              statements, and in alias lists of other variables.  It would be
5293              quite difficult to expunge it from all those places.  ??? It might
5294              suffice to do this for addressable variables.  */
5295           if ((TREE_CODE (t) == VAR_DECL
5296                && !is_global_var (t))
5297               || TREE_CODE (t) == CONST_DECL)
5298             replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
5299
5300           if (SSA_VAR_P (t)
5301               && gimple_in_ssa_p (cfun))
5302             {
5303               push_cfun (DECL_STRUCT_FUNCTION (p->to_context));
5304               add_referenced_var (*tp);
5305               pop_cfun ();
5306             }
5307         }
5308       *walk_subtrees = 0;
5309     }
5310   else if (TYPE_P (t))
5311     *walk_subtrees = 0;
5312
5313   return NULL_TREE;
5314 }
5315
5316 /* Like move_stmt_op, but for gimple statements.
5317
5318    Helper for move_block_to_fn.  Set GIMPLE_BLOCK in every expression
5319    contained in the current statement in *GSI_P and change the
5320    DECL_CONTEXT of every local variable referenced in the current
5321    statement.  */
5322
5323 static tree
5324 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
5325              struct walk_stmt_info *wi)
5326 {
5327   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5328   gimple stmt = gsi_stmt (*gsi_p);
5329   tree block = gimple_block (stmt);
5330
5331   if (p->orig_block == NULL_TREE
5332       || block == p->orig_block
5333       || block == NULL_TREE)
5334     gimple_set_block (stmt, p->new_block);
5335 #ifdef ENABLE_CHECKING
5336   else if (block != p->new_block)
5337     {
5338       while (block && block != p->orig_block)
5339         block = BLOCK_SUPERCONTEXT (block);
5340       gcc_assert (block);
5341     }
5342 #endif
5343
5344   if (is_gimple_omp (stmt)
5345       && gimple_code (stmt) != GIMPLE_OMP_RETURN
5346       && gimple_code (stmt) != GIMPLE_OMP_CONTINUE)
5347     {
5348       /* Do not remap variables inside OMP directives.  Variables
5349          referenced in clauses and directive header belong to the
5350          parent function and should not be moved into the child
5351          function.  */
5352       bool save_remap_decls_p = p->remap_decls_p;
5353       p->remap_decls_p = false;
5354       *handled_ops_p = true;
5355
5356       walk_gimple_seq (gimple_omp_body (stmt), move_stmt_r, move_stmt_op, wi);
5357
5358       p->remap_decls_p = save_remap_decls_p;
5359     }
5360
5361   return NULL_TREE;
5362 }
5363
5364 /* Marks virtual operands of all statements in basic blocks BBS for
5365    renaming.  */
5366
5367 void
5368 mark_virtual_ops_in_bb (basic_block bb)
5369 {
5370   gimple_stmt_iterator gsi;
5371
5372   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5373     mark_virtual_ops_for_renaming (gsi_stmt (gsi));
5374
5375   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5376     mark_virtual_ops_for_renaming (gsi_stmt (gsi));
5377 }
5378
5379 /* Marks virtual operands of all statements in basic blocks BBS for
5380    renaming.  */
5381
5382 static void
5383 mark_virtual_ops_in_region (VEC (basic_block,heap) *bbs)
5384 {
5385   basic_block bb;
5386   unsigned i;
5387
5388   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5389     mark_virtual_ops_in_bb (bb);
5390 }
5391
5392 /* Move basic block BB from function CFUN to function DEST_FN.  The
5393    block is moved out of the original linked list and placed after
5394    block AFTER in the new list.  Also, the block is removed from the
5395    original array of blocks and placed in DEST_FN's array of blocks.
5396    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
5397    updated to reflect the moved edges.
5398
5399    The local variables are remapped to new instances, VARS_MAP is used
5400    to record the mapping.  */
5401
5402 static void
5403 move_block_to_fn (struct function *dest_cfun, basic_block bb,
5404                   basic_block after, bool update_edge_count_p,
5405                   struct move_stmt_d *d, int eh_offset)
5406 {
5407   struct control_flow_graph *cfg;
5408   edge_iterator ei;
5409   edge e;
5410   gimple_stmt_iterator si;
5411   unsigned old_len, new_len;
5412
5413   /* Remove BB from dominance structures.  */
5414   delete_from_dominance_info (CDI_DOMINATORS, bb);
5415   if (current_loops)
5416     remove_bb_from_loops (bb);
5417
5418   /* Link BB to the new linked list.  */
5419   move_block_after (bb, after);
5420
5421   /* Update the edge count in the corresponding flowgraphs.  */
5422   if (update_edge_count_p)
5423     FOR_EACH_EDGE (e, ei, bb->succs)
5424       {
5425         cfun->cfg->x_n_edges--;
5426         dest_cfun->cfg->x_n_edges++;
5427       }
5428
5429   /* Remove BB from the original basic block array.  */
5430   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
5431   cfun->cfg->x_n_basic_blocks--;
5432
5433   /* Grow DEST_CFUN's basic block array if needed.  */
5434   cfg = dest_cfun->cfg;
5435   cfg->x_n_basic_blocks++;
5436   if (bb->index >= cfg->x_last_basic_block)
5437     cfg->x_last_basic_block = bb->index + 1;
5438
5439   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
5440   if ((unsigned) cfg->x_last_basic_block >= old_len)
5441     {
5442       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
5443       VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
5444                              new_len);
5445     }
5446
5447   VEC_replace (basic_block, cfg->x_basic_block_info,
5448                bb->index, bb);
5449
5450   /* Remap the variables in phi nodes.  */
5451   for (si = gsi_start_phis (bb); !gsi_end_p (si); )
5452     {
5453       gimple phi = gsi_stmt (si);
5454       use_operand_p use;
5455       tree op = PHI_RESULT (phi);
5456       ssa_op_iter oi;
5457
5458       if (!is_gimple_reg (op))
5459         {
5460           /* Remove the phi nodes for virtual operands (alias analysis will be
5461              run for the new function, anyway).  */
5462           remove_phi_node (&si, true);
5463           continue;
5464         }
5465
5466       SET_PHI_RESULT (phi,
5467                       replace_ssa_name (op, d->vars_map, dest_cfun->decl));
5468       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
5469         {
5470           op = USE_FROM_PTR (use);
5471           if (TREE_CODE (op) == SSA_NAME)
5472             SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
5473         }
5474
5475       gsi_next (&si);
5476     }
5477
5478   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
5479     {
5480       gimple stmt = gsi_stmt (si);
5481       int region;
5482       struct walk_stmt_info wi;
5483
5484       memset (&wi, 0, sizeof (wi));
5485       wi.info = d;
5486       walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
5487
5488       if (gimple_code (stmt) == GIMPLE_LABEL)
5489         {
5490           tree label = gimple_label_label (stmt);
5491           int uid = LABEL_DECL_UID (label);
5492
5493           gcc_assert (uid > -1);
5494
5495           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
5496           if (old_len <= (unsigned) uid)
5497             {
5498               new_len = 3 * uid / 2;
5499               VEC_safe_grow_cleared (basic_block, gc,
5500                                      cfg->x_label_to_block_map, new_len);
5501             }
5502
5503           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
5504           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
5505
5506           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
5507
5508           if (uid >= dest_cfun->cfg->last_label_uid)
5509             dest_cfun->cfg->last_label_uid = uid + 1;
5510         }
5511       else if (gimple_code (stmt) == GIMPLE_RESX && eh_offset != 0)
5512         gimple_resx_set_region (stmt, gimple_resx_region (stmt) + eh_offset);
5513
5514       region = lookup_stmt_eh_region (stmt);
5515       if (region >= 0)
5516         {
5517           add_stmt_to_eh_region_fn (dest_cfun, stmt, region + eh_offset);
5518           remove_stmt_from_eh_region (stmt);
5519           gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
5520           gimple_remove_stmt_histograms (cfun, stmt);
5521         }
5522
5523       /* We cannot leave any operands allocated from the operand caches of
5524          the current function.  */
5525       free_stmt_operands (stmt);
5526       push_cfun (dest_cfun);
5527       update_stmt (stmt);
5528       pop_cfun ();
5529     }
5530 }
5531
5532 /* Examine the statements in BB (which is in SRC_CFUN); find and return
5533    the outermost EH region.  Use REGION as the incoming base EH region.  */
5534
5535 static int
5536 find_outermost_region_in_block (struct function *src_cfun,
5537                                 basic_block bb, int region)
5538 {
5539   gimple_stmt_iterator si;
5540
5541   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
5542     {
5543       gimple stmt = gsi_stmt (si);
5544       int stmt_region;
5545
5546       if (gimple_code (stmt) == GIMPLE_RESX)
5547         stmt_region = gimple_resx_region (stmt);
5548       else
5549         stmt_region = lookup_stmt_eh_region_fn (src_cfun, stmt);
5550       if (stmt_region > 0)
5551         {
5552           if (region < 0)
5553             region = stmt_region;
5554           else if (stmt_region != region)
5555             {
5556               region = eh_region_outermost (src_cfun, stmt_region, region);
5557               gcc_assert (region != -1);
5558             }
5559         }
5560     }
5561
5562   return region;
5563 }
5564
5565 static tree
5566 new_label_mapper (tree decl, void *data)
5567 {
5568   htab_t hash = (htab_t) data;
5569   struct tree_map *m;
5570   void **slot;
5571
5572   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
5573
5574   m = XNEW (struct tree_map);
5575   m->hash = DECL_UID (decl);
5576   m->base.from = decl;
5577   m->to = create_artificial_label ();
5578   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
5579   if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
5580     cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
5581
5582   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
5583   gcc_assert (*slot == NULL);
5584
5585   *slot = m;
5586
5587   return m->to;
5588 }
5589
5590 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
5591    subblocks.  */
5592
5593 static void
5594 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map,
5595                                   tree to_context)
5596 {
5597   tree *tp, t;
5598
5599   for (tp = &BLOCK_VARS (block); *tp; tp = &TREE_CHAIN (*tp))
5600     {
5601       t = *tp;
5602       replace_by_duplicate_decl (&t, vars_map, to_context);
5603       if (t != *tp)
5604         {
5605           if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
5606             {
5607               SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
5608               DECL_HAS_VALUE_EXPR_P (t) = 1;
5609             }
5610           TREE_CHAIN (t) = TREE_CHAIN (*tp);
5611           *tp = t;
5612         }
5613     }
5614
5615   for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
5616     replace_block_vars_by_duplicates (block, vars_map, to_context);
5617 }
5618
5619 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
5620    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
5621    single basic block in the original CFG and the new basic block is
5622    returned.  DEST_CFUN must not have a CFG yet.
5623
5624    Note that the region need not be a pure SESE region.  Blocks inside
5625    the region may contain calls to abort/exit.  The only restriction
5626    is that ENTRY_BB should be the only entry point and it must
5627    dominate EXIT_BB.
5628
5629    Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
5630    functions outermost BLOCK, move all subblocks of ORIG_BLOCK
5631    to the new function.
5632
5633    All local variables referenced in the region are assumed to be in
5634    the corresponding BLOCK_VARS and unexpanded variable lists
5635    associated with DEST_CFUN.  */
5636
5637 basic_block
5638 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
5639                         basic_block exit_bb, tree orig_block)
5640 {
5641   VEC(basic_block,heap) *bbs, *dom_bbs;
5642   basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
5643   basic_block after, bb, *entry_pred, *exit_succ, abb;
5644   struct function *saved_cfun = cfun;
5645   int *entry_flag, *exit_flag, eh_offset;
5646   unsigned *entry_prob, *exit_prob;
5647   unsigned i, num_entry_edges, num_exit_edges;
5648   edge e;
5649   edge_iterator ei;
5650   htab_t new_label_map;
5651   struct pointer_map_t *vars_map;
5652   struct loop *loop = entry_bb->loop_father;
5653   struct move_stmt_d d;
5654
5655   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
5656      region.  */
5657   gcc_assert (entry_bb != exit_bb
5658               && (!exit_bb
5659                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
5660
5661   /* Collect all the blocks in the region.  Manually add ENTRY_BB
5662      because it won't be added by dfs_enumerate_from.  */
5663   bbs = NULL;
5664   VEC_safe_push (basic_block, heap, bbs, entry_bb);
5665   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
5666
5667   /* The blocks that used to be dominated by something in BBS will now be
5668      dominated by the new block.  */
5669   dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
5670                                      VEC_address (basic_block, bbs),
5671                                      VEC_length (basic_block, bbs));
5672
5673   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
5674      the predecessor edges to ENTRY_BB and the successor edges to
5675      EXIT_BB so that we can re-attach them to the new basic block that
5676      will replace the region.  */
5677   num_entry_edges = EDGE_COUNT (entry_bb->preds);
5678   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
5679   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
5680   entry_prob = XNEWVEC (unsigned, num_entry_edges);
5681   i = 0;
5682   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
5683     {
5684       entry_prob[i] = e->probability;
5685       entry_flag[i] = e->flags;
5686       entry_pred[i++] = e->src;
5687       remove_edge (e);
5688     }
5689
5690   if (exit_bb)
5691     {
5692       num_exit_edges = EDGE_COUNT (exit_bb->succs);
5693       exit_succ = (basic_block *) xcalloc (num_exit_edges,
5694                                            sizeof (basic_block));
5695       exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
5696       exit_prob = XNEWVEC (unsigned, num_exit_edges);
5697       i = 0;
5698       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
5699         {
5700           exit_prob[i] = e->probability;
5701           exit_flag[i] = e->flags;
5702           exit_succ[i++] = e->dest;
5703           remove_edge (e);
5704         }
5705     }
5706   else
5707     {
5708       num_exit_edges = 0;
5709       exit_succ = NULL;
5710       exit_flag = NULL;
5711       exit_prob = NULL;
5712     }
5713
5714   /* Switch context to the child function to initialize DEST_FN's CFG.  */
5715   gcc_assert (dest_cfun->cfg == NULL);
5716   push_cfun (dest_cfun);
5717
5718   init_empty_tree_cfg ();
5719
5720   /* Initialize EH information for the new function.  */
5721   eh_offset = 0;
5722   new_label_map = NULL;
5723   if (saved_cfun->eh)
5724     {
5725       int region = -1;
5726
5727       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5728         region = find_outermost_region_in_block (saved_cfun, bb, region);
5729
5730       init_eh_for_function ();
5731       if (region != -1)
5732         {
5733           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
5734           eh_offset = duplicate_eh_regions (saved_cfun, new_label_mapper,
5735                                             new_label_map, region, 0);
5736         }
5737     }
5738
5739   pop_cfun ();
5740
5741   /* The ssa form for virtual operands in the source function will have to
5742      be repaired.  We do not care for the real operands -- the sese region
5743      must be closed with respect to those.  */
5744   mark_virtual_ops_in_region (bbs);
5745
5746   /* Move blocks from BBS into DEST_CFUN.  */
5747   gcc_assert (VEC_length (basic_block, bbs) >= 2);
5748   after = dest_cfun->cfg->x_entry_block_ptr;
5749   vars_map = pointer_map_create ();
5750
5751   memset (&d, 0, sizeof (d));
5752   d.vars_map = vars_map;
5753   d.from_context = cfun->decl;
5754   d.to_context = dest_cfun->decl;
5755   d.new_label_map = new_label_map;
5756   d.remap_decls_p = true;
5757   d.orig_block = orig_block;
5758   d.new_block = DECL_INITIAL (dest_cfun->decl);
5759
5760   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
5761     {
5762       /* No need to update edge counts on the last block.  It has
5763          already been updated earlier when we detached the region from
5764          the original CFG.  */
5765       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d, eh_offset);
5766       after = bb;
5767     }
5768
5769   /* Rewire BLOCK_SUBBLOCKS of orig_block.  */
5770   if (orig_block)
5771     {
5772       tree block;
5773       gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
5774                   == NULL_TREE);
5775       BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
5776         = BLOCK_SUBBLOCKS (orig_block);
5777       for (block = BLOCK_SUBBLOCKS (orig_block);
5778            block; block = BLOCK_CHAIN (block))
5779         BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
5780       BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
5781     }
5782
5783   replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
5784                                     vars_map, dest_cfun->decl);
5785
5786   if (new_label_map)
5787     htab_delete (new_label_map);
5788   pointer_map_destroy (vars_map);
5789
5790   /* Rewire the entry and exit blocks.  The successor to the entry
5791      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
5792      the child function.  Similarly, the predecessor of DEST_FN's
5793      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
5794      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
5795      various CFG manipulation function get to the right CFG.
5796
5797      FIXME, this is silly.  The CFG ought to become a parameter to
5798      these helpers.  */
5799   push_cfun (dest_cfun);
5800   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
5801   if (exit_bb)
5802     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
5803   pop_cfun ();
5804
5805   /* Back in the original function, the SESE region has disappeared,
5806      create a new basic block in its place.  */
5807   bb = create_empty_bb (entry_pred[0]);
5808   if (current_loops)
5809     add_bb_to_loop (bb, loop);
5810   for (i = 0; i < num_entry_edges; i++)
5811     {
5812       e = make_edge (entry_pred[i], bb, entry_flag[i]);
5813       e->probability = entry_prob[i];
5814     }
5815
5816   for (i = 0; i < num_exit_edges; i++)
5817     {
5818       e = make_edge (bb, exit_succ[i], exit_flag[i]);
5819       e->probability = exit_prob[i];
5820     }
5821
5822   set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
5823   for (i = 0; VEC_iterate (basic_block, dom_bbs, i, abb); i++)
5824     set_immediate_dominator (CDI_DOMINATORS, abb, bb);
5825   VEC_free (basic_block, heap, dom_bbs);
5826
5827   if (exit_bb)
5828     {
5829       free (exit_prob);
5830       free (exit_flag);
5831       free (exit_succ);
5832     }
5833   free (entry_prob);
5834   free (entry_flag);
5835   free (entry_pred);
5836   VEC_free (basic_block, heap, bbs);
5837
5838   return bb;
5839 }
5840
5841
5842 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree-pass.h)
5843    */
5844
5845 void
5846 dump_function_to_file (tree fn, FILE *file, int flags)
5847 {
5848   tree arg, vars, var;
5849   struct function *dsf;
5850   bool ignore_topmost_bind = false, any_var = false;
5851   basic_block bb;
5852   tree chain;
5853
5854   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
5855
5856   arg = DECL_ARGUMENTS (fn);
5857   while (arg)
5858     {
5859       print_generic_expr (file, TREE_TYPE (arg), dump_flags);
5860       fprintf (file, " ");
5861       print_generic_expr (file, arg, dump_flags);
5862       if (flags & TDF_VERBOSE)
5863         print_node (file, "", arg, 4);
5864       if (TREE_CHAIN (arg))
5865         fprintf (file, ", ");
5866       arg = TREE_CHAIN (arg);
5867     }
5868   fprintf (file, ")\n");
5869
5870   if (flags & TDF_VERBOSE)
5871     print_node (file, "", fn, 2);
5872
5873   dsf = DECL_STRUCT_FUNCTION (fn);
5874   if (dsf && (flags & TDF_DETAILS))
5875     dump_eh_tree (file, dsf);
5876
5877   if (flags & TDF_RAW && !gimple_body (fn))
5878     {
5879       dump_node (fn, TDF_SLIM | flags, file);
5880       return;
5881     }
5882
5883   /* Switch CFUN to point to FN.  */
5884   push_cfun (DECL_STRUCT_FUNCTION (fn));
5885
5886   /* When GIMPLE is lowered, the variables are no longer available in
5887      BIND_EXPRs, so display them separately.  */
5888   if (cfun && cfun->decl == fn && cfun->local_decls)
5889     {
5890       ignore_topmost_bind = true;
5891
5892       fprintf (file, "{\n");
5893       for (vars = cfun->local_decls; vars; vars = TREE_CHAIN (vars))
5894         {
5895           var = TREE_VALUE (vars);
5896
5897           print_generic_decl (file, var, flags);
5898           if (flags & TDF_VERBOSE)
5899             print_node (file, "", var, 4);
5900           fprintf (file, "\n");
5901
5902           any_var = true;
5903         }
5904     }
5905
5906   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
5907     {
5908       /* If the CFG has been built, emit a CFG-based dump.  */
5909       check_bb_profile (ENTRY_BLOCK_PTR, file);
5910       if (!ignore_topmost_bind)
5911         fprintf (file, "{\n");
5912
5913       if (any_var && n_basic_blocks)
5914         fprintf (file, "\n");
5915
5916       FOR_EACH_BB (bb)
5917         gimple_dump_bb (bb, file, 2, flags);
5918
5919       fprintf (file, "}\n");
5920       check_bb_profile (EXIT_BLOCK_PTR, file);
5921     }
5922   else if (DECL_SAVED_TREE (fn) == NULL)
5923     {
5924       /* The function is now in GIMPLE form but the CFG has not been
5925          built yet.  Emit the single sequence of GIMPLE statements
5926          that make up its body.  */
5927       gimple_seq body = gimple_body (fn);
5928
5929       if (gimple_seq_first_stmt (body)
5930           && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
5931           && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
5932         print_gimple_seq (file, body, 0, flags);
5933       else
5934         {
5935           if (!ignore_topmost_bind)
5936             fprintf (file, "{\n");
5937
5938           if (any_var)
5939             fprintf (file, "\n");
5940
5941           print_gimple_seq (file, body, 2, flags);
5942           fprintf (file, "}\n");
5943         }
5944     }
5945   else
5946     {
5947       int indent;
5948
5949       /* Make a tree based dump.  */
5950       chain = DECL_SAVED_TREE (fn);
5951
5952       if (chain && TREE_CODE (chain) == BIND_EXPR)
5953         {
5954           if (ignore_topmost_bind)
5955             {
5956               chain = BIND_EXPR_BODY (chain);
5957               indent = 2;
5958             }
5959           else
5960             indent = 0;
5961         }
5962       else
5963         {
5964           if (!ignore_topmost_bind)
5965             fprintf (file, "{\n");
5966           indent = 2;
5967         }
5968
5969       if (any_var)
5970         fprintf (file, "\n");
5971
5972       print_generic_stmt_indented (file, chain, flags, indent);
5973       if (ignore_topmost_bind)
5974         fprintf (file, "}\n");
5975     }
5976
5977   fprintf (file, "\n\n");
5978
5979   /* Restore CFUN.  */
5980   pop_cfun ();
5981 }
5982
5983
5984 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
5985
5986 void
5987 debug_function (tree fn, int flags)
5988 {
5989   dump_function_to_file (fn, stderr, flags);
5990 }
5991
5992
5993 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
5994
5995 static void
5996 print_pred_bbs (FILE *file, basic_block bb)
5997 {
5998   edge e;
5999   edge_iterator ei;
6000
6001   FOR_EACH_EDGE (e, ei, bb->preds)
6002     fprintf (file, "bb_%d ", e->src->index);
6003 }
6004
6005
6006 /* Print on FILE the indexes for the successors of basic_block BB.  */
6007
6008 static void
6009 print_succ_bbs (FILE *file, basic_block bb)
6010 {
6011   edge e;
6012   edge_iterator ei;
6013
6014   FOR_EACH_EDGE (e, ei, bb->succs)
6015     fprintf (file, "bb_%d ", e->dest->index);
6016 }
6017
6018 /* Print to FILE the basic block BB following the VERBOSITY level.  */
6019
6020 void
6021 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6022 {
6023   char *s_indent = (char *) alloca ((size_t) indent + 1);
6024   memset ((void *) s_indent, ' ', (size_t) indent);
6025   s_indent[indent] = '\0';
6026
6027   /* Print basic_block's header.  */
6028   if (verbosity >= 2)
6029     {
6030       fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
6031       print_pred_bbs (file, bb);
6032       fprintf (file, "}, succs = {");
6033       print_succ_bbs (file, bb);
6034       fprintf (file, "})\n");
6035     }
6036
6037   /* Print basic_block's body.  */
6038   if (verbosity >= 3)
6039     {
6040       fprintf (file, "%s  {\n", s_indent);
6041       gimple_dump_bb (bb, file, indent + 4, TDF_VOPS|TDF_MEMSYMS);
6042       fprintf (file, "%s  }\n", s_indent);
6043     }
6044 }
6045
6046 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6047
6048 /* Pretty print LOOP on FILE, indented INDENT spaces.  Following
6049    VERBOSITY level this outputs the contents of the loop, or just its
6050    structure.  */
6051
6052 static void
6053 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6054 {
6055   char *s_indent;
6056   basic_block bb;
6057
6058   if (loop == NULL)
6059     return;
6060
6061   s_indent = (char *) alloca ((size_t) indent + 1);
6062   memset ((void *) s_indent, ' ', (size_t) indent);
6063   s_indent[indent] = '\0';
6064
6065   /* Print loop's header.  */
6066   fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent,
6067            loop->num, loop->header->index, loop->latch->index);
6068   fprintf (file, ", niter = ");
6069   print_generic_expr (file, loop->nb_iterations, 0);
6070
6071   if (loop->any_upper_bound)
6072     {
6073       fprintf (file, ", upper_bound = ");
6074       dump_double_int (file, loop->nb_iterations_upper_bound, true);
6075     }
6076
6077   if (loop->any_estimate)
6078     {
6079       fprintf (file, ", estimate = ");
6080       dump_double_int (file, loop->nb_iterations_estimate, true);
6081     }
6082   fprintf (file, ")\n");
6083
6084   /* Print loop's body.  */
6085   if (verbosity >= 1)
6086     {
6087       fprintf (file, "%s{\n", s_indent);
6088       FOR_EACH_BB (bb)
6089         if (bb->loop_father == loop)
6090           print_loops_bb (file, bb, indent, verbosity);
6091
6092       print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
6093       fprintf (file, "%s}\n", s_indent);
6094     }
6095 }
6096
6097 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6098    spaces.  Following VERBOSITY level this outputs the contents of the
6099    loop, or just its structure.  */
6100
6101 static void
6102 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
6103 {
6104   if (loop == NULL)
6105     return;
6106
6107   print_loop (file, loop, indent, verbosity);
6108   print_loop_and_siblings (file, loop->next, indent, verbosity);
6109 }
6110
6111 /* Follow a CFG edge from the entry point of the program, and on entry
6112    of a loop, pretty print the loop structure on FILE.  */
6113
6114 void
6115 print_loops (FILE *file, int verbosity)
6116 {
6117   basic_block bb;
6118
6119   bb = BASIC_BLOCK (NUM_FIXED_BLOCKS);
6120   if (bb && bb->loop_father)
6121     print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
6122 }
6123
6124
6125 /* Debugging loops structure at tree level, at some VERBOSITY level.  */
6126
6127 void
6128 debug_loops (int verbosity)
6129 {
6130   print_loops (stderr, verbosity);
6131 }
6132
6133 /* Print on stderr the code of LOOP, at some VERBOSITY level.  */
6134
6135 void
6136 debug_loop (struct loop *loop, int verbosity)
6137 {
6138   print_loop (stderr, loop, 0, verbosity);
6139 }
6140
6141 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6142    level.  */
6143
6144 void
6145 debug_loop_num (unsigned num, int verbosity)
6146 {
6147   debug_loop (get_loop (num), verbosity);
6148 }
6149
6150 /* Return true if BB ends with a call, possibly followed by some
6151    instructions that must stay with the call.  Return false,
6152    otherwise.  */
6153
6154 static bool
6155 gimple_block_ends_with_call_p (basic_block bb)
6156 {
6157   gimple_stmt_iterator gsi = gsi_last_bb (bb);
6158   return is_gimple_call (gsi_stmt (gsi));
6159 }
6160
6161
6162 /* Return true if BB ends with a conditional branch.  Return false,
6163    otherwise.  */
6164
6165 static bool
6166 gimple_block_ends_with_condjump_p (const_basic_block bb)
6167 {
6168   gimple stmt = last_stmt (CONST_CAST_BB (bb));
6169   return (stmt && gimple_code (stmt) == GIMPLE_COND);
6170 }
6171
6172
6173 /* Return true if we need to add fake edge to exit at statement T.
6174    Helper function for gimple_flow_call_edges_add.  */
6175
6176 static bool
6177 need_fake_edge_p (gimple t)
6178 {
6179   tree fndecl = NULL_TREE;
6180   int call_flags = 0;
6181
6182   /* NORETURN and LONGJMP calls already have an edge to exit.
6183      CONST and PURE calls do not need one.
6184      We don't currently check for CONST and PURE here, although
6185      it would be a good idea, because those attributes are
6186      figured out from the RTL in mark_constant_function, and
6187      the counter incrementation code from -fprofile-arcs
6188      leads to different results from -fbranch-probabilities.  */
6189   if (is_gimple_call (t))
6190     {
6191       fndecl = gimple_call_fndecl (t);
6192       call_flags = gimple_call_flags (t);
6193     }
6194
6195   if (is_gimple_call (t)
6196       && fndecl
6197       && DECL_BUILT_IN (fndecl)
6198       && (call_flags & ECF_NOTHROW)
6199       && !(call_flags & ECF_NORETURN)
6200       && !(call_flags & ECF_RETURNS_TWICE))
6201    return false;
6202
6203   if (is_gimple_call (t)
6204       && !(call_flags & ECF_NORETURN))
6205     return true;
6206
6207   if (gimple_code (t) == ASM_EXPR
6208        && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
6209     return true;
6210
6211   return false;
6212 }
6213
6214
6215 /* Add fake edges to the function exit for any non constant and non
6216    noreturn calls, volatile inline assembly in the bitmap of blocks
6217    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
6218    the number of blocks that were split.
6219
6220    The goal is to expose cases in which entering a basic block does
6221    not imply that all subsequent instructions must be executed.  */
6222
6223 static int
6224 gimple_flow_call_edges_add (sbitmap blocks)
6225 {
6226   int i;
6227   int blocks_split = 0;
6228   int last_bb = last_basic_block;
6229   bool check_last_block = false;
6230
6231   if (n_basic_blocks == NUM_FIXED_BLOCKS)
6232     return 0;
6233
6234   if (! blocks)
6235     check_last_block = true;
6236   else
6237     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
6238
6239   /* In the last basic block, before epilogue generation, there will be
6240      a fallthru edge to EXIT.  Special care is required if the last insn
6241      of the last basic block is a call because make_edge folds duplicate
6242      edges, which would result in the fallthru edge also being marked
6243      fake, which would result in the fallthru edge being removed by
6244      remove_fake_edges, which would result in an invalid CFG.
6245
6246      Moreover, we can't elide the outgoing fake edge, since the block
6247      profiler needs to take this into account in order to solve the minimal
6248      spanning tree in the case that the call doesn't return.
6249
6250      Handle this by adding a dummy instruction in a new last basic block.  */
6251   if (check_last_block)
6252     {
6253       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
6254       gimple_stmt_iterator gsi = gsi_last_bb (bb);
6255       gimple t = NULL;
6256
6257       if (!gsi_end_p (gsi))
6258         t = gsi_stmt (gsi);
6259
6260       if (t && need_fake_edge_p (t))
6261         {
6262           edge e;
6263
6264           e = find_edge (bb, EXIT_BLOCK_PTR);
6265           if (e)
6266             {
6267               gsi_insert_on_edge (e, gimple_build_nop ());
6268               gsi_commit_edge_inserts ();
6269             }
6270         }
6271     }
6272
6273   /* Now add fake edges to the function exit for any non constant
6274      calls since there is no way that we can determine if they will
6275      return or not...  */
6276   for (i = 0; i < last_bb; i++)
6277     {
6278       basic_block bb = BASIC_BLOCK (i);
6279       gimple_stmt_iterator gsi;
6280       gimple stmt, last_stmt;
6281
6282       if (!bb)
6283         continue;
6284
6285       if (blocks && !TEST_BIT (blocks, i))
6286         continue;
6287
6288       gsi = gsi_last_bb (bb);
6289       if (!gsi_end_p (gsi))
6290         {
6291           last_stmt = gsi_stmt (gsi);
6292           do
6293             {
6294               stmt = gsi_stmt (gsi);
6295               if (need_fake_edge_p (stmt))
6296                 {
6297                   edge e;
6298
6299                   /* The handling above of the final block before the
6300                      epilogue should be enough to verify that there is
6301                      no edge to the exit block in CFG already.
6302                      Calling make_edge in such case would cause us to
6303                      mark that edge as fake and remove it later.  */
6304 #ifdef ENABLE_CHECKING
6305                   if (stmt == last_stmt)
6306                     {
6307                       e = find_edge (bb, EXIT_BLOCK_PTR);
6308                       gcc_assert (e == NULL);
6309                     }
6310 #endif
6311
6312                   /* Note that the following may create a new basic block
6313                      and renumber the existing basic blocks.  */
6314                   if (stmt != last_stmt)
6315                     {
6316                       e = split_block (bb, stmt);
6317                       if (e)
6318                         blocks_split++;
6319                     }
6320                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
6321                 }
6322               gsi_prev (&gsi);
6323             }
6324           while (!gsi_end_p (gsi));
6325         }
6326     }
6327
6328   if (blocks_split)
6329     verify_flow_info ();
6330
6331   return blocks_split;
6332 }
6333
6334 /* Purge dead abnormal call edges from basic block BB.  */
6335
6336 bool
6337 gimple_purge_dead_abnormal_call_edges (basic_block bb)
6338 {
6339   bool changed = gimple_purge_dead_eh_edges (bb);
6340
6341   if (cfun->has_nonlocal_label)
6342     {
6343       gimple stmt = last_stmt (bb);
6344       edge_iterator ei;
6345       edge e;
6346
6347       if (!(stmt && stmt_can_make_abnormal_goto (stmt)))
6348         for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6349           {
6350             if (e->flags & EDGE_ABNORMAL)
6351               {
6352                 remove_edge (e);
6353                 changed = true;
6354               }
6355             else
6356               ei_next (&ei);
6357           }
6358
6359       /* See gimple_purge_dead_eh_edges below.  */
6360       if (changed)
6361         free_dominance_info (CDI_DOMINATORS);
6362     }
6363
6364   return changed;
6365 }
6366
6367 /* Stores all basic blocks dominated by BB to DOM_BBS.  */
6368
6369 static void
6370 get_all_dominated_blocks (basic_block bb, VEC (basic_block, heap) **dom_bbs)
6371 {
6372   basic_block son;
6373
6374   VEC_safe_push (basic_block, heap, *dom_bbs, bb);
6375   for (son = first_dom_son (CDI_DOMINATORS, bb);
6376        son;
6377        son = next_dom_son (CDI_DOMINATORS, son))
6378     get_all_dominated_blocks (son, dom_bbs);
6379 }
6380
6381 /* Removes edge E and all the blocks dominated by it, and updates dominance
6382    information.  The IL in E->src needs to be updated separately.
6383    If dominance info is not available, only the edge E is removed.*/
6384
6385 void
6386 remove_edge_and_dominated_blocks (edge e)
6387 {
6388   VEC (basic_block, heap) *bbs_to_remove = NULL;
6389   VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
6390   bitmap df, df_idom;
6391   edge f;
6392   edge_iterator ei;
6393   bool none_removed = false;
6394   unsigned i;
6395   basic_block bb, dbb;
6396   bitmap_iterator bi;
6397
6398   if (!dom_info_available_p (CDI_DOMINATORS))
6399     {
6400       remove_edge (e);
6401       return;
6402     }
6403
6404   /* No updating is needed for edges to exit.  */
6405   if (e->dest == EXIT_BLOCK_PTR)
6406     {
6407       if (cfgcleanup_altered_bbs)
6408         bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6409       remove_edge (e);
6410       return;
6411     }
6412
6413   /* First, we find the basic blocks to remove.  If E->dest has a predecessor
6414      that is not dominated by E->dest, then this set is empty.  Otherwise,
6415      all the basic blocks dominated by E->dest are removed.
6416
6417      Also, to DF_IDOM we store the immediate dominators of the blocks in
6418      the dominance frontier of E (i.e., of the successors of the
6419      removed blocks, if there are any, and of E->dest otherwise).  */
6420   FOR_EACH_EDGE (f, ei, e->dest->preds)
6421     {
6422       if (f == e)
6423         continue;
6424
6425       if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
6426         {
6427           none_removed = true;
6428           break;
6429         }
6430     }
6431
6432   df = BITMAP_ALLOC (NULL);
6433   df_idom = BITMAP_ALLOC (NULL);
6434
6435   if (none_removed)
6436     bitmap_set_bit (df_idom,
6437                     get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
6438   else
6439     {
6440       get_all_dominated_blocks (e->dest, &bbs_to_remove);
6441       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6442         {
6443           FOR_EACH_EDGE (f, ei, bb->succs)
6444             {
6445               if (f->dest != EXIT_BLOCK_PTR)
6446                 bitmap_set_bit (df, f->dest->index);
6447             }
6448         }
6449       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6450         bitmap_clear_bit (df, bb->index);
6451
6452       EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
6453         {
6454           bb = BASIC_BLOCK (i);
6455           bitmap_set_bit (df_idom,
6456                           get_immediate_dominator (CDI_DOMINATORS, bb)->index);
6457         }
6458     }
6459
6460   if (cfgcleanup_altered_bbs)
6461     {
6462       /* Record the set of the altered basic blocks.  */
6463       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6464       bitmap_ior_into (cfgcleanup_altered_bbs, df);
6465     }
6466
6467   /* Remove E and the cancelled blocks.  */
6468   if (none_removed)
6469     remove_edge (e);
6470   else
6471     {
6472       for (i = 0; VEC_iterate (basic_block, bbs_to_remove, i, bb); i++)
6473         delete_basic_block (bb);
6474     }
6475
6476   /* Update the dominance information.  The immediate dominator may change only
6477      for blocks whose immediate dominator belongs to DF_IDOM:
6478
6479      Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
6480      removal.  Let Z the arbitrary block such that idom(Z) = Y and
6481      Z dominates X after the removal.  Before removal, there exists a path P
6482      from Y to X that avoids Z.  Let F be the last edge on P that is
6483      removed, and let W = F->dest.  Before removal, idom(W) = Y (since Y
6484      dominates W, and because of P, Z does not dominate W), and W belongs to
6485      the dominance frontier of E.  Therefore, Y belongs to DF_IDOM.  */
6486   EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
6487     {
6488       bb = BASIC_BLOCK (i);
6489       for (dbb = first_dom_son (CDI_DOMINATORS, bb);
6490            dbb;
6491            dbb = next_dom_son (CDI_DOMINATORS, dbb))
6492         VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
6493     }
6494
6495   iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
6496
6497   BITMAP_FREE (df);
6498   BITMAP_FREE (df_idom);
6499   VEC_free (basic_block, heap, bbs_to_remove);
6500   VEC_free (basic_block, heap, bbs_to_fix_dom);
6501 }
6502
6503 /* Purge dead EH edges from basic block BB.  */
6504
6505 bool
6506 gimple_purge_dead_eh_edges (basic_block bb)
6507 {
6508   bool changed = false;
6509   edge e;
6510   edge_iterator ei;
6511   gimple stmt = last_stmt (bb);
6512
6513   if (stmt && stmt_can_throw_internal (stmt))
6514     return false;
6515
6516   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
6517     {
6518       if (e->flags & EDGE_EH)
6519         {
6520           remove_edge_and_dominated_blocks (e);
6521           changed = true;
6522         }
6523       else
6524         ei_next (&ei);
6525     }
6526
6527   return changed;
6528 }
6529
6530 bool
6531 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
6532 {
6533   bool changed = false;
6534   unsigned i;
6535   bitmap_iterator bi;
6536
6537   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
6538     {
6539       changed |= gimple_purge_dead_eh_edges (BASIC_BLOCK (i));
6540     }
6541
6542   return changed;
6543 }
6544
6545 /* This function is called whenever a new edge is created or
6546    redirected.  */
6547
6548 static void
6549 gimple_execute_on_growing_pred (edge e)
6550 {
6551   basic_block bb = e->dest;
6552
6553   if (phi_nodes (bb))
6554     reserve_phi_args_for_new_edge (bb);
6555 }
6556
6557 /* This function is called immediately before edge E is removed from
6558    the edge vector E->dest->preds.  */
6559
6560 static void
6561 gimple_execute_on_shrinking_pred (edge e)
6562 {
6563   if (phi_nodes (e->dest))
6564     remove_phi_args (e);
6565 }
6566
6567 /*---------------------------------------------------------------------------
6568   Helper functions for Loop versioning
6569   ---------------------------------------------------------------------------*/
6570
6571 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
6572    of 'first'. Both of them are dominated by 'new_head' basic block. When
6573    'new_head' was created by 'second's incoming edge it received phi arguments
6574    on the edge by split_edge(). Later, additional edge 'e' was created to
6575    connect 'new_head' and 'first'. Now this routine adds phi args on this
6576    additional edge 'e' that new_head to second edge received as part of edge
6577    splitting.  */
6578
6579 static void
6580 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
6581                                   basic_block new_head, edge e)
6582 {
6583   gimple phi1, phi2;
6584   gimple_stmt_iterator psi1, psi2;
6585   tree def;
6586   edge e2 = find_edge (new_head, second);
6587
6588   /* Because NEW_HEAD has been created by splitting SECOND's incoming
6589      edge, we should always have an edge from NEW_HEAD to SECOND.  */
6590   gcc_assert (e2 != NULL);
6591
6592   /* Browse all 'second' basic block phi nodes and add phi args to
6593      edge 'e' for 'first' head. PHI args are always in correct order.  */
6594
6595   for (psi2 = gsi_start_phis (second),
6596        psi1 = gsi_start_phis (first);
6597        !gsi_end_p (psi2) && !gsi_end_p (psi1);
6598        gsi_next (&psi2),  gsi_next (&psi1))
6599     {
6600       phi1 = gsi_stmt (psi1);
6601       phi2 = gsi_stmt (psi2);
6602       def = PHI_ARG_DEF (phi2, e2->dest_idx);
6603       add_phi_arg (phi1, def, e);
6604     }
6605 }
6606
6607
6608 /* Adds a if else statement to COND_BB with condition COND_EXPR.
6609    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
6610    the destination of the ELSE part.  */
6611
6612 static void
6613 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
6614                                basic_block second_head ATTRIBUTE_UNUSED,
6615                                basic_block cond_bb, void *cond_e)
6616 {
6617   gimple_stmt_iterator gsi;
6618   gimple new_cond_expr;
6619   tree cond_expr = (tree) cond_e;
6620   edge e0;
6621
6622   /* Build new conditional expr */
6623   new_cond_expr = gimple_build_cond_from_tree (cond_expr,
6624                                                NULL_TREE, NULL_TREE);
6625
6626   /* Add new cond in cond_bb.  */
6627   gsi = gsi_last_bb (cond_bb);
6628   gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
6629
6630   /* Adjust edges appropriately to connect new head with first head
6631      as well as second head.  */
6632   e0 = single_succ_edge (cond_bb);
6633   e0->flags &= ~EDGE_FALLTHRU;
6634   e0->flags |= EDGE_FALSE_VALUE;
6635 }
6636
6637 struct cfg_hooks gimple_cfg_hooks = {
6638   "gimple",
6639   gimple_verify_flow_info,
6640   gimple_dump_bb,               /* dump_bb  */
6641   create_bb,                    /* create_basic_block  */
6642   gimple_redirect_edge_and_branch, /* redirect_edge_and_branch  */
6643   gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force  */
6644   gimple_can_remove_branch_p,   /* can_remove_branch_p  */
6645   remove_bb,                    /* delete_basic_block  */
6646   gimple_split_block,           /* split_block  */
6647   gimple_move_block_after,      /* move_block_after  */
6648   gimple_can_merge_blocks_p,    /* can_merge_blocks_p  */
6649   gimple_merge_blocks,          /* merge_blocks  */
6650   gimple_predict_edge,          /* predict_edge  */
6651   gimple_predicted_by_p,                /* predicted_by_p  */
6652   gimple_can_duplicate_bb_p,    /* can_duplicate_block_p  */
6653   gimple_duplicate_bb,          /* duplicate_block  */
6654   gimple_split_edge,            /* split_edge  */
6655   gimple_make_forwarder_block,  /* make_forward_block  */
6656   NULL,                         /* tidy_fallthru_edge  */
6657   gimple_block_ends_with_call_p,/* block_ends_with_call_p */
6658   gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
6659   gimple_flow_call_edges_add,     /* flow_call_edges_add */
6660   gimple_execute_on_growing_pred,       /* execute_on_growing_pred */
6661   gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
6662   gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
6663   gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
6664   gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
6665   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
6666   flush_pending_stmts           /* flush_pending_stmts */
6667 };
6668
6669
6670 /* Split all critical edges.  */
6671
6672 static unsigned int
6673 split_critical_edges (void)
6674 {
6675   basic_block bb;
6676   edge e;
6677   edge_iterator ei;
6678
6679   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
6680      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
6681      mappings around the calls to split_edge.  */
6682   start_recording_case_labels ();
6683   FOR_ALL_BB (bb)
6684     {
6685       FOR_EACH_EDGE (e, ei, bb->succs)
6686         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
6687           {
6688             split_edge (e);
6689           }
6690     }
6691   end_recording_case_labels ();
6692   return 0;
6693 }
6694
6695 struct gimple_opt_pass pass_split_crit_edges =
6696 {
6697  {
6698   GIMPLE_PASS,
6699   "crited",                          /* name */
6700   NULL,                          /* gate */
6701   split_critical_edges,          /* execute */
6702   NULL,                          /* sub */
6703   NULL,                          /* next */
6704   0,                             /* static_pass_number */
6705   TV_TREE_SPLIT_EDGES,           /* tv_id */
6706   PROP_cfg,                      /* properties required */
6707   PROP_no_crit_edges,            /* properties_provided */
6708   0,                             /* properties_destroyed */
6709   0,                             /* todo_flags_start */
6710   TODO_dump_func                 /* todo_flags_finish */
6711  }
6712 };
6713
6714
6715 /* Build a ternary operation and gimplify it.  Emit code before GSI.
6716    Return the gimple_val holding the result.  */
6717
6718 tree
6719 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
6720                  tree type, tree a, tree b, tree c)
6721 {
6722   tree ret;
6723
6724   ret = fold_build3 (code, type, a, b, c);
6725   STRIP_NOPS (ret);
6726
6727   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
6728                                    GSI_SAME_STMT);
6729 }
6730
6731 /* Build a binary operation and gimplify it.  Emit code before GSI.
6732    Return the gimple_val holding the result.  */
6733
6734 tree
6735 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
6736                  tree type, tree a, tree b)
6737 {
6738   tree ret;
6739
6740   ret = fold_build2 (code, type, a, b);
6741   STRIP_NOPS (ret);
6742
6743   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
6744                                    GSI_SAME_STMT);
6745 }
6746
6747 /* Build a unary operation and gimplify it.  Emit code before GSI.
6748    Return the gimple_val holding the result.  */
6749
6750 tree
6751 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
6752                  tree a)
6753 {
6754   tree ret;
6755
6756   ret = fold_build1 (code, type, a);
6757   STRIP_NOPS (ret);
6758
6759   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
6760                                    GSI_SAME_STMT);
6761 }
6762
6763
6764 \f
6765 /* Emit return warnings.  */
6766
6767 static unsigned int
6768 execute_warn_function_return (void)
6769 {
6770   source_location location;
6771   gimple last;
6772   edge e;
6773   edge_iterator ei;
6774
6775   /* If we have a path to EXIT, then we do return.  */
6776   if (TREE_THIS_VOLATILE (cfun->decl)
6777       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
6778     {
6779       location = UNKNOWN_LOCATION;
6780       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
6781         {
6782           last = last_stmt (e->src);
6783           if (gimple_code (last) == GIMPLE_RETURN
6784               && (location = gimple_location (last)) != UNKNOWN_LOCATION)
6785             break;
6786         }
6787       if (location == UNKNOWN_LOCATION)
6788         location = cfun->function_end_locus;
6789       warning (0, "%H%<noreturn%> function does return", &location);
6790     }
6791
6792   /* If we see "return;" in some basic block, then we do reach the end
6793      without returning a value.  */
6794   else if (warn_return_type
6795            && !TREE_NO_WARNING (cfun->decl)
6796            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
6797            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
6798     {
6799       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
6800         {
6801           gimple last = last_stmt (e->src);
6802           if (gimple_code (last) == GIMPLE_RETURN
6803               && gimple_return_retval (last) == NULL
6804               && !gimple_no_warning_p (last))
6805             {
6806               location = gimple_location (last);
6807               if (location == UNKNOWN_LOCATION)
6808                   location = cfun->function_end_locus;
6809               warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
6810               TREE_NO_WARNING (cfun->decl) = 1;
6811               break;
6812             }
6813         }
6814     }
6815   return 0;
6816 }
6817
6818
6819 /* Given a basic block B which ends with a conditional and has
6820    precisely two successors, determine which of the edges is taken if
6821    the conditional is true and which is taken if the conditional is
6822    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
6823
6824 void
6825 extract_true_false_edges_from_block (basic_block b,
6826                                      edge *true_edge,
6827                                      edge *false_edge)
6828 {
6829   edge e = EDGE_SUCC (b, 0);
6830
6831   if (e->flags & EDGE_TRUE_VALUE)
6832     {
6833       *true_edge = e;
6834       *false_edge = EDGE_SUCC (b, 1);
6835     }
6836   else
6837     {
6838       *false_edge = e;
6839       *true_edge = EDGE_SUCC (b, 1);
6840     }
6841 }
6842
6843 struct gimple_opt_pass pass_warn_function_return =
6844 {
6845  {
6846   GIMPLE_PASS,
6847   NULL,                                 /* name */
6848   NULL,                                 /* gate */
6849   execute_warn_function_return,         /* execute */
6850   NULL,                                 /* sub */
6851   NULL,                                 /* next */
6852   0,                                    /* static_pass_number */
6853   0,                                    /* tv_id */
6854   PROP_cfg,                             /* properties_required */
6855   0,                                    /* properties_provided */
6856   0,                                    /* properties_destroyed */
6857   0,                                    /* todo_flags_start */
6858   0                                     /* todo_flags_finish */
6859  }
6860 };
6861
6862 /* Emit noreturn warnings.  */
6863
6864 static unsigned int
6865 execute_warn_function_noreturn (void)
6866 {
6867   if (warn_missing_noreturn
6868       && !TREE_THIS_VOLATILE (cfun->decl)
6869       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
6870       && !lang_hooks.missing_noreturn_ok_p (cfun->decl))
6871     warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
6872              "for attribute %<noreturn%>",
6873              cfun->decl);
6874   return 0;
6875 }
6876
6877 struct gimple_opt_pass pass_warn_function_noreturn =
6878 {
6879  {
6880   GIMPLE_PASS,
6881   NULL,                                 /* name */
6882   NULL,                                 /* gate */
6883   execute_warn_function_noreturn,       /* execute */
6884   NULL,                                 /* sub */
6885   NULL,                                 /* next */
6886   0,                                    /* static_pass_number */
6887   0,                                    /* tv_id */
6888   PROP_cfg,                             /* properties_required */
6889   0,                                    /* properties_provided */
6890   0,                                    /* properties_destroyed */
6891   0,                                    /* todo_flags_start */
6892   0                                     /* todo_flags_finish */
6893  }
6894 };