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