gcc/tree-cfg.c

   1 /* Control flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
   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 2, 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 COPYING.  If not, write to
  20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  21 Boston, MA 02110-1301, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "tree.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "hard-reg-set.h"
  31 #include "basic-block.h"
  32 #include "output.h"
  33 #include "flags.h"
  34 #include "function.h"
  35 #include "expr.h"
  36 #include "ggc.h"
  37 #include "langhooks.h"
  38 #include "diagnostic.h"
  39 #include "tree-flow.h"
  40 #include "timevar.h"
  41 #include "tree-dump.h"
  42 #include "tree-pass.h"
  43 #include "toplev.h"
  44 #include "except.h"
  45 #include "cfgloop.h"
  46 #include "cfglayout.h"
  47 #include "hashtab.h"
  48 #include "tree-ssa-propagate.h"
  49
  50 /* This file contains functions for building the Control Flow Graph (CFG)
  51    for a function tree.  */
  52
  53 /* Local declarations.  */
  54
  55 /* Initial capacity for the basic block array.  */
  56 static const int initial_cfg_capacity = 20;
  57
  58 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
  59    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
  60    via their TREE_CHAIN field, which we clear after we're done with the
  61    hash table to prevent problems with duplication of SWITCH_EXPRs.
  62
  63    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
  64    update the case vector in response to edge redirections.
  65
  66    Right now this table is set up and torn down at key points in the
  67    compilation process.  It would be nice if we could make the table
  68    more persistent.  The key is getting notification of changes to
  69    the CFG (particularly edge removal, creation and redirection).  */
  70
  71 struct edge_to_cases_elt
  72 {
  73   /* The edge itself.  Necessary for hashing and equality tests.  */
  74   edge e;
  75
  76   /* The case labels associated with this edge.  We link these up via
  77      their TREE_CHAIN field, then we wipe out the TREE_CHAIN fields
  78      when we destroy the hash table.  This prevents problems when copying
  79      SWITCH_EXPRs.  */
  80   tree case_labels;
  81 };
  82
  83 static htab_t edge_to_cases;
  84
  85 /* CFG statistics.  */
  86 struct cfg_stats_d
  87 {
  88   long num_merged_labels;
  89 };
  90
  91 static struct cfg_stats_d cfg_stats;
  92
  93 /* Nonzero if we found a computed goto while building basic blocks.  */
  94 static bool found_computed_goto;
  95
  96 /* Basic blocks and flowgraphs.  */
  97 static basic_block create_bb (void *, void *, basic_block);
  98 static void make_blocks (tree);
  99 static void factor_computed_gotos (void);
 100
 101 /* Edges.  */
 102 static void make_edges (void);
 103 static void make_cond_expr_edges (basic_block);
 104 static void make_switch_expr_edges (basic_block);
 105 static void make_goto_expr_edges (basic_block);
 106 static edge tree_redirect_edge_and_branch (edge, basic_block);
 107 static edge tree_try_redirect_by_replacing_jump (edge, basic_block);
 108 static unsigned int split_critical_edges (void);
 109
 110 /* Various helpers.  */
 111 static inline bool stmt_starts_bb_p (tree, tree);
 112 static int tree_verify_flow_info (void);
 113 static void tree_make_forwarder_block (edge);
 114 static void tree_cfg2vcg (FILE *);
 115
 116 /* Flowgraph optimization and cleanup.  */
 117 static void tree_merge_blocks (basic_block, basic_block);
 118 static bool tree_can_merge_blocks_p (basic_block, basic_block);
 119 static void remove_bb (basic_block);
 120 static edge find_taken_edge_computed_goto (basic_block, tree);
 121 static edge find_taken_edge_cond_expr (basic_block, tree);
 122 static edge find_taken_edge_switch_expr (basic_block, tree);
 123 static tree find_case_label_for_value (tree, tree);
 124
 125 void
 126 init_empty_tree_cfg (void)
 127 {
 128   /* Initialize the basic block array.  */
 129   init_flow ();
 130   profile_status = PROFILE_ABSENT;
 131   n_basic_blocks = NUM_FIXED_BLOCKS;
 132   last_basic_block = NUM_FIXED_BLOCKS;
 133   basic_block_info = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 134   VEC_safe_grow (basic_block, gc, basic_block_info, initial_cfg_capacity);
 135   memset (VEC_address (basic_block, basic_block_info), 0,
 136           sizeof (basic_block) * initial_cfg_capacity);
 137
 138   /* Build a mapping of labels to their associated blocks.  */
 139   label_to_block_map = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 140   VEC_safe_grow (basic_block, gc, label_to_block_map, initial_cfg_capacity);
 141   memset (VEC_address (basic_block, label_to_block_map),
 142           0, sizeof (basic_block) * initial_cfg_capacity);
 143
 144   SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
 145   SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
 146   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 147   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 148 }
 149
 150 /*---------------------------------------------------------------------------
 151                               Create basic blocks
 152 ---------------------------------------------------------------------------*/
 153
 154 /* Entry point to the CFG builder for trees.  TP points to the list of
 155    statements to be added to the flowgraph.  */
 156
 157 static void
 158 build_tree_cfg (tree *tp)
 159 {
 160   /* Register specific tree functions.  */
 161   tree_register_cfg_hooks ();
 162
 163   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
 164
 165   init_empty_tree_cfg ();
 166
 167   found_computed_goto = 0;
 168   make_blocks (*tp);
 169
 170   /* Computed gotos are hell to deal with, especially if there are
 171      lots of them with a large number of destinations.  So we factor
 172      them to a common computed goto location before we build the
 173      edge list.  After we convert back to normal form, we will un-factor
 174      the computed gotos since factoring introduces an unwanted jump.  */
 175   if (found_computed_goto)
 176     factor_computed_gotos ();
 177
 178   /* Make sure there is always at least one block, even if it's empty.  */
 179   if (n_basic_blocks == NUM_FIXED_BLOCKS)
 180     create_empty_bb (ENTRY_BLOCK_PTR);
 181
 182   /* Adjust the size of the array.  */
 183   if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
 184     {
 185       size_t old_size = VEC_length (basic_block, basic_block_info);
 186       basic_block *p;
 187       VEC_safe_grow (basic_block, gc, basic_block_info, n_basic_blocks);
 188       p = VEC_address (basic_block, basic_block_info);
 189       memset (&p[old_size], 0,
 190               sizeof (basic_block) * (n_basic_blocks - old_size));
 191     }
 192
 193   /* To speed up statement iterator walks, we first purge dead labels.  */
 194   cleanup_dead_labels ();
 195
 196   /* Group case nodes to reduce the number of edges.
 197      We do this after cleaning up dead labels because otherwise we miss
 198      a lot of obvious case merging opportunities.  */
 199   group_case_labels ();
 200
 201   /* Create the edges of the flowgraph.  */
 202   make_edges ();
 203
 204   /* Debugging dumps.  */
 205
 206   /* Write the flowgraph to a VCG file.  */
 207   {
 208     int local_dump_flags;
 209     FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
 210     if (vcg_file)
 211       {
 212         tree_cfg2vcg (vcg_file);
 213         dump_end (TDI_vcg, vcg_file);
 214       }
 215   }
 216
 217 #ifdef ENABLE_CHECKING
 218   verify_stmts ();
 219 #endif
 220
 221   /* Dump a textual representation of the flowgraph.  */
 222   if (dump_file)
 223     dump_tree_cfg (dump_file, dump_flags);
 224 }
 225
 226 static unsigned int
 227 execute_build_cfg (void)
 228 {
 229   build_tree_cfg (&DECL_SAVED_TREE (current_function_decl));
 230   return 0;
 231 }
 232
 233 struct tree_opt_pass pass_build_cfg =
 234 {
 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_flags_finish */
 247   0                                     /* letter */
 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 = build2 (MODIFY_EXPR, ptr_type_node,
 317                                var, 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->stmt_list = h ? (tree) h : alloc_stmt_list ();
 391
 392   /* Add the new block to the linked list of blocks.  */
 393   link_block (bb, after);
 394
 395   /* Grow the basic block array if needed.  */
 396   if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
 397     {
 398       size_t old_size = VEC_length (basic_block, basic_block_info);
 399       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
 400       basic_block *p;
 401       VEC_safe_grow (basic_block, gc, basic_block_info, new_size);
 402       p = VEC_address (basic_block, basic_block_info);
 403       memset (&p[old_size], 0, sizeof (basic_block) * (new_size - old_size));
 404     }
 405
 406   /* Add the newly created block to the array.  */
 407   SET_BASIC_BLOCK (last_basic_block, bb);
 408
 409   n_basic_blocks++;
 410   last_basic_block++;
 411
 412   return bb;
 413 }
 414
 415
 416 /*---------------------------------------------------------------------------
 417                                  Edge creation
 418 ---------------------------------------------------------------------------*/
 419
 420 /* Fold COND_EXPR_COND of each COND_EXPR.  */
 421
 422 void
 423 fold_cond_expr_cond (void)
 424 {
 425   basic_block bb;
 426
 427   FOR_EACH_BB (bb)
 428     {
 429       tree stmt = last_stmt (bb);
 430
 431       if (stmt
 432           && TREE_CODE (stmt) == COND_EXPR)
 433         {
 434           tree cond = fold (COND_EXPR_COND (stmt));
 435           if (integer_zerop (cond))
 436             COND_EXPR_COND (stmt) = boolean_false_node;
 437           else if (integer_onep (cond))
 438             COND_EXPR_COND (stmt) = boolean_true_node;
 439         }
 440     }
 441 }
 442
 443 /* Join all the blocks in the flowgraph.  */
 444
 445 static void
 446 make_edges (void)
 447 {
 448   basic_block bb;
 449   struct omp_region *cur_region = NULL;
 450
 451   /* Create an edge from entry to the first block with executable
 452      statements in it.  */
 453   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
 454
 455   /* Traverse the basic block array placing edges.  */
 456   FOR_EACH_BB (bb)
 457     {
 458       tree last = last_stmt (bb);
 459       bool fallthru;
 460
 461       if (last)
 462         {
 463           enum tree_code code = TREE_CODE (last);
 464           switch (code)
 465             {
 466             case GOTO_EXPR:
 467               make_goto_expr_edges (bb);
 468               fallthru = false;
 469               break;
 470             case RETURN_EXPR:
 471               make_edge (bb, EXIT_BLOCK_PTR, 0);
 472               fallthru = false;
 473               break;
 474             case COND_EXPR:
 475               make_cond_expr_edges (bb);
 476               fallthru = false;
 477               break;
 478             case SWITCH_EXPR:
 479               make_switch_expr_edges (bb);
 480               fallthru = false;
 481               break;
 482             case RESX_EXPR:
 483               make_eh_edges (last);
 484               fallthru = false;
 485               break;
 486
 487             case CALL_EXPR:
 488               /* If this function receives a nonlocal goto, then we need to
 489                  make edges from this call site to all the nonlocal goto
 490                  handlers.  */
 491               if (TREE_SIDE_EFFECTS (last)
 492                   && current_function_has_nonlocal_label)
 493                 make_goto_expr_edges (bb);
 494
 495               /* If this statement has reachable exception handlers, then
 496                  create abnormal edges to them.  */
 497               make_eh_edges (last);
 498
 499               /* Some calls are known not to return.  */
 500               fallthru = !(call_expr_flags (last) & ECF_NORETURN);
 501               break;
 502
 503             case MODIFY_EXPR:
 504               if (is_ctrl_altering_stmt (last))
 505                 {
 506                   /* A MODIFY_EXPR may have a CALL_EXPR on its RHS and the
 507                      CALL_EXPR may have an abnormal edge.  Search the RHS for
 508                      this case and create any required edges.  */
 509                   tree op = get_call_expr_in (last);
 510                   if (op && TREE_SIDE_EFFECTS (op)
 511                       && current_function_has_nonlocal_label)
 512                     make_goto_expr_edges (bb);
 513
 514                   make_eh_edges (last);
 515                 }
 516               fallthru = true;
 517               break;
 518
 519             case OMP_PARALLEL:
 520             case OMP_FOR:
 521             case OMP_SINGLE:
 522             case OMP_MASTER:
 523             case OMP_ORDERED:
 524             case OMP_CRITICAL:
 525             case OMP_SECTION:
 526               cur_region = new_omp_region (bb, code, cur_region);
 527               fallthru = true;
 528               break;
 529
 530             case OMP_SECTIONS:
 531               cur_region = new_omp_region (bb, code, cur_region);
 532               fallthru = false;
 533               break;
 534
 535             case OMP_RETURN:
 536               /* In the case of an OMP_SECTION, the edge will go somewhere
 537                  other than the next block.  This will be created later.  */
 538               cur_region->exit = bb;
 539               fallthru = cur_region->type != OMP_SECTION;
 540               cur_region = cur_region->outer;
 541               break;
 542
 543             case OMP_CONTINUE:
 544               cur_region->cont = bb;
 545               switch (cur_region->type)
 546                 {
 547                 case OMP_FOR:
 548                   /* ??? Technically there should be a some sort of loopback
 549                      edge here, but it goes to a block that doesn't exist yet,
 550                      and without it, updating the ssa form would be a real
 551                      bear.  Fortunately, we don't yet do ssa before expanding
 552                      these nodes.  */
 553                   break;
 554
 555                 case OMP_SECTIONS:
 556                   /* Wire up the edges into and out of the nested sections.  */
 557                   /* ??? Similarly wrt loopback.  */
 558                   {
 559                     struct omp_region *i;
 560                     for (i = cur_region->inner; i ; i = i->next)
 561                       {
 562                         gcc_assert (i->type == OMP_SECTION);
 563                         make_edge (cur_region->entry, i->entry, 0);
 564                         make_edge (i->exit, bb, EDGE_FALLTHRU);
 565                       }
 566                   }
 567                   break;
 568
 569                 default:
 570                   gcc_unreachable ();
 571                 }
 572               fallthru = true;
 573               break;
 574
 575             default:
 576               gcc_assert (!stmt_ends_bb_p (last));
 577               fallthru = true;
 578             }
 579         }
 580       else
 581         fallthru = true;
 582
 583       if (fallthru)
 584         make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 585     }
 586
 587   if (root_omp_region)
 588     free_omp_regions ();
 589
 590   /* Fold COND_EXPR_COND of each COND_EXPR.  */
 591   fold_cond_expr_cond ();
 592
 593   /* Clean up the graph and warn for unreachable code.  */
 594   cleanup_tree_cfg ();
 595 }
 596
 597
 598 /* Create the edges for a COND_EXPR starting at block BB.
 599    At this point, both clauses must contain only simple gotos.  */
 600
 601 static void
 602 make_cond_expr_edges (basic_block bb)
 603 {
 604   tree entry = last_stmt (bb);
 605   basic_block then_bb, else_bb;
 606   tree then_label, else_label;
 607   edge e;
 608
 609   gcc_assert (entry);
 610   gcc_assert (TREE_CODE (entry) == COND_EXPR);
 611
 612   /* Entry basic blocks for each component.  */
 613   then_label = GOTO_DESTINATION (COND_EXPR_THEN (entry));
 614   else_label = GOTO_DESTINATION (COND_EXPR_ELSE (entry));
 615   then_bb = label_to_block (then_label);
 616   else_bb = label_to_block (else_label);
 617
 618   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
 619 #ifdef USE_MAPPED_LOCATION
 620   e->goto_locus = EXPR_LOCATION (COND_EXPR_THEN (entry));
 621 #else
 622   e->goto_locus = EXPR_LOCUS (COND_EXPR_THEN (entry));
 623 #endif
 624   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
 625   if (e)
 626     {
 627 #ifdef USE_MAPPED_LOCATION
 628       e->goto_locus = EXPR_LOCATION (COND_EXPR_ELSE (entry));
 629 #else
 630       e->goto_locus = EXPR_LOCUS (COND_EXPR_ELSE (entry));
 631 #endif
 632     }
 633 }
 634
 635 /* Hashing routine for EDGE_TO_CASES.  */
 636
 637 static hashval_t
 638 edge_to_cases_hash (const void *p)
 639 {
 640   edge e = ((struct edge_to_cases_elt *)p)->e;
 641
 642   /* Hash on the edge itself (which is a pointer).  */
 643   return htab_hash_pointer (e);
 644 }
 645
 646 /* Equality routine for EDGE_TO_CASES, edges are unique, so testing
 647    for equality is just a pointer comparison.  */
 648
 649 static int
 650 edge_to_cases_eq (const void *p1, const void *p2)
 651 {
 652   edge e1 = ((struct edge_to_cases_elt *)p1)->e;
 653   edge e2 = ((struct edge_to_cases_elt *)p2)->e;
 654
 655   return e1 == e2;
 656 }
 657
 658 /* Called for each element in the hash table (P) as we delete the
 659    edge to cases hash table.
 660
 661    Clear all the TREE_CHAINs to prevent problems with copying of
 662    SWITCH_EXPRs and structure sharing rules, then free the hash table
 663    element.  */
 664
 665 static void
 666 edge_to_cases_cleanup (void *p)
 667 {
 668   struct edge_to_cases_elt *elt = (struct edge_to_cases_elt *) p;
 669   tree t, next;
 670
 671   for (t = elt->case_labels; t; t = next)
 672     {
 673       next = TREE_CHAIN (t);
 674       TREE_CHAIN (t) = NULL;
 675     }
 676   free (p);
 677 }
 678
 679 /* Start recording information mapping edges to case labels.  */
 680
 681 void
 682 start_recording_case_labels (void)
 683 {
 684   gcc_assert (edge_to_cases == NULL);
 685
 686   edge_to_cases = htab_create (37,
 687                                edge_to_cases_hash,
 688                                edge_to_cases_eq,
 689                                edge_to_cases_cleanup);
 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   htab_delete (edge_to_cases);
 706   edge_to_cases = NULL;
 707 }
 708
 709 /* Record that CASE_LABEL (a CASE_LABEL_EXPR) references edge E.  */
 710
 711 static void
 712 record_switch_edge (edge e, tree case_label)
 713 {
 714   struct edge_to_cases_elt *elt;
 715   void **slot;
 716
 717   /* Build a hash table element so we can see if E is already
 718      in the table.  */
 719   elt = XNEW (struct edge_to_cases_elt);
 720   elt->e = e;
 721   elt->case_labels = case_label;
 722
 723   slot = htab_find_slot (edge_to_cases, elt, INSERT);
 724
 725   if (*slot == NULL)
 726     {
 727       /* E was not in the hash table.  Install E into the hash table.  */
 728       *slot = (void *)elt;
 729     }
 730   else
 731     {
 732       /* E was already in the hash table.  Free ELT as we do not need it
 733          anymore.  */
 734       free (elt);
 735
 736       /* Get the entry stored in the hash table.  */
 737       elt = (struct edge_to_cases_elt *) *slot;
 738
 739       /* Add it to the chain of CASE_LABEL_EXPRs referencing E.  */
 740       TREE_CHAIN (case_label) = elt->case_labels;
 741       elt->case_labels = case_label;
 742     }
 743 }
 744
 745 /* If we are inside a {start,end}_recording_cases block, then return
 746    a chain of CASE_LABEL_EXPRs from T which reference E.
 747
 748    Otherwise return NULL.  */
 749
 750 static tree
 751 get_cases_for_edge (edge e, tree t)
 752 {
 753   struct edge_to_cases_elt elt, *elt_p;
 754   void **slot;
 755   size_t i, n;
 756   tree vec;
 757
 758   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
 759      chains available.  Return NULL so the caller can detect this case.  */
 760   if (!recording_case_labels_p ())
 761     return NULL;
 762
 763 restart:
 764   elt.e = e;
 765   elt.case_labels = NULL;
 766   slot = htab_find_slot (edge_to_cases, &elt, NO_INSERT);
 767
 768   if (slot)
 769     {
 770       elt_p = (struct edge_to_cases_elt *)*slot;
 771       return elt_p->case_labels;
 772     }
 773
 774   /* If we did not find E in the hash table, then this must be the first
 775      time we have been queried for information about E & T.  Add all the
 776      elements from T to the hash table then perform the query again.  */
 777
 778   vec = SWITCH_LABELS (t);
 779   n = TREE_VEC_LENGTH (vec);
 780   for (i = 0; i < n; i++)
 781     {
 782       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
 783       basic_block label_bb = label_to_block (lab);
 784       record_switch_edge (find_edge (e->src, label_bb), TREE_VEC_ELT (vec, i));
 785     }
 786   goto restart;
 787 }
 788
 789 /* Create the edges for a SWITCH_EXPR starting at block BB.
 790    At this point, the switch body has been lowered and the
 791    SWITCH_LABELS filled in, so this is in effect a multi-way branch.  */
 792
 793 static void
 794 make_switch_expr_edges (basic_block bb)
 795 {
 796   tree entry = last_stmt (bb);
 797   size_t i, n;
 798   tree vec;
 799
 800   vec = SWITCH_LABELS (entry);
 801   n = TREE_VEC_LENGTH (vec);
 802
 803   for (i = 0; i < n; ++i)
 804     {
 805       tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
 806       basic_block label_bb = label_to_block (lab);
 807       make_edge (bb, label_bb, 0);
 808     }
 809 }
 810
 811
 812 /* Return the basic block holding label DEST.  */
 813
 814 basic_block
 815 label_to_block_fn (struct function *ifun, tree dest)
 816 {
 817   int uid = LABEL_DECL_UID (dest);
 818
 819   /* We would die hard when faced by an undefined label.  Emit a label to
 820      the very first basic block.  This will hopefully make even the dataflow
 821      and undefined variable warnings quite right.  */
 822   if ((errorcount || sorrycount) && uid < 0)
 823     {
 824       block_stmt_iterator bsi =
 825         bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 826       tree stmt;
 827
 828       stmt = build1 (LABEL_EXPR, void_type_node, dest);
 829       bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
 830       uid = LABEL_DECL_UID (dest);
 831     }
 832   if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
 833       <= (unsigned int) uid)
 834     return NULL;
 835   return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
 836 }
 837
 838 /* Create edges for a goto statement at block BB.  */
 839
 840 static void
 841 make_goto_expr_edges (basic_block bb)
 842 {
 843   tree goto_t;
 844   basic_block target_bb;
 845   bool for_call;
 846   block_stmt_iterator last = bsi_last (bb);
 847
 848   goto_t = bsi_stmt (last);
 849
 850   /* If the last statement is not a GOTO (i.e., it is a RETURN_EXPR,
 851      CALL_EXPR or MODIFY_EXPR), then the edge is an abnormal edge resulting
 852      from a nonlocal goto.  */
 853   if (TREE_CODE (goto_t) != GOTO_EXPR)
 854     for_call = true;
 855   else
 856     {
 857       tree dest = GOTO_DESTINATION (goto_t);
 858       for_call = false;
 859
 860       /* A GOTO to a local label creates normal edges.  */
 861       if (simple_goto_p (goto_t))
 862         {
 863           edge e = make_edge (bb, label_to_block (dest), EDGE_FALLTHRU);
 864 #ifdef USE_MAPPED_LOCATION
 865           e->goto_locus = EXPR_LOCATION (goto_t);
 866 #else
 867           e->goto_locus = EXPR_LOCUS (goto_t);
 868 #endif
 869           bsi_remove (&last, true);
 870           return;
 871         }
 872
 873       /* Nothing more to do for nonlocal gotos.  */
 874       if (TREE_CODE (dest) == LABEL_DECL)
 875         return;
 876
 877       /* Computed gotos remain.  */
 878     }
 879
 880   /* Look for the block starting with the destination label.  In the
 881      case of a computed goto, make an edge to any label block we find
 882      in the CFG.  */
 883   FOR_EACH_BB (target_bb)
 884     {
 885       block_stmt_iterator bsi;
 886
 887       for (bsi = bsi_start (target_bb); !bsi_end_p (bsi); bsi_next (&bsi))
 888         {
 889           tree target = bsi_stmt (bsi);
 890
 891           if (TREE_CODE (target) != LABEL_EXPR)
 892             break;
 893
 894           if (
 895               /* Computed GOTOs.  Make an edge to every label block that has
 896                  been marked as a potential target for a computed goto.  */
 897               (FORCED_LABEL (LABEL_EXPR_LABEL (target)) && !for_call)
 898               /* Nonlocal GOTO target.  Make an edge to every label block
 899                  that has been marked as a potential target for a nonlocal
 900                  goto.  */
 901               || (DECL_NONLOCAL (LABEL_EXPR_LABEL (target)) && for_call))
 902             {
 903               make_edge (bb, target_bb, EDGE_ABNORMAL);
 904               break;
 905             }
 906         }
 907     }
 908 }
 909
 910
 911 /*---------------------------------------------------------------------------
 912                                Flowgraph analysis
 913 ---------------------------------------------------------------------------*/
 914
 915 /* Cleanup useless labels in basic blocks.  This is something we wish
 916    to do early because it allows us to group case labels before creating
 917    the edges for the CFG, and it speeds up block statement iterators in
 918    all passes later on.
 919    We only run this pass once, running it more than once is probably not
 920    profitable.  */
 921
 922 /* A map from basic block index to the leading label of that block.  */
 923 static tree *label_for_bb;
 924
 925 /* Callback for for_each_eh_region.  Helper for cleanup_dead_labels.  */
 926 static void
 927 update_eh_label (struct eh_region *region)
 928 {
 929   tree old_label = get_eh_region_tree_label (region);
 930   if (old_label)
 931     {
 932       tree new_label;
 933       basic_block bb = label_to_block (old_label);
 934
 935       /* ??? After optimizing, there may be EH regions with labels
 936          that have already been removed from the function body, so
 937          there is no basic block for them.  */
 938       if (! bb)
 939         return;
 940
 941       new_label = label_for_bb[bb->index];
 942       set_eh_region_tree_label (region, new_label);
 943     }
 944 }
 945
 946 /* Given LABEL return the first label in the same basic block.  */
 947 static tree
 948 main_block_label (tree label)
 949 {
 950   basic_block bb = label_to_block (label);
 951
 952   /* label_to_block possibly inserted undefined label into the chain.  */
 953   if (!label_for_bb[bb->index])
 954     label_for_bb[bb->index] = label;
 955   return label_for_bb[bb->index];
 956 }
 957
 958 /* Cleanup redundant labels.  This is a three-step process:
 959      1) Find the leading label for each block.
 960      2) Redirect all references to labels to the leading labels.
 961      3) Cleanup all useless labels.  */
 962
 963 void
 964 cleanup_dead_labels (void)
 965 {
 966   basic_block bb;
 967   label_for_bb = XCNEWVEC (tree, last_basic_block);
 968
 969   /* Find a suitable label for each block.  We use the first user-defined
 970      label if there is one, or otherwise just the first label we see.  */
 971   FOR_EACH_BB (bb)
 972     {
 973       block_stmt_iterator i;
 974
 975       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 976         {
 977           tree label, stmt = bsi_stmt (i);
 978
 979           if (TREE_CODE (stmt) != LABEL_EXPR)
 980             break;
 981
 982           label = LABEL_EXPR_LABEL (stmt);
 983
 984           /* If we have not yet seen a label for the current block,
 985              remember this one and see if there are more labels.  */
 986           if (! label_for_bb[bb->index])
 987             {
 988               label_for_bb[bb->index] = label;
 989               continue;
 990             }
 991
 992           /* If we did see a label for the current block already, but it
 993              is an artificially created label, replace it if the current
 994              label is a user defined label.  */
 995           if (! DECL_ARTIFICIAL (label)
 996               && DECL_ARTIFICIAL (label_for_bb[bb->index]))
 997             {
 998               label_for_bb[bb->index] = label;
 999               break;
1000             }
1001         }
1002     }
1003
1004   /* Now redirect all jumps/branches to the selected label.
1005      First do so for each block ending in a control statement.  */
1006   FOR_EACH_BB (bb)
1007     {
1008       tree stmt = last_stmt (bb);
1009       if (!stmt)
1010         continue;
1011
1012       switch (TREE_CODE (stmt))
1013         {
1014         case COND_EXPR:
1015           {
1016             tree true_branch, false_branch;
1017
1018             true_branch = COND_EXPR_THEN (stmt);
1019             false_branch = COND_EXPR_ELSE (stmt);
1020
1021             GOTO_DESTINATION (true_branch)
1022               = main_block_label (GOTO_DESTINATION (true_branch));
1023             GOTO_DESTINATION (false_branch)
1024               = main_block_label (GOTO_DESTINATION (false_branch));
1025
1026             break;
1027           }
1028
1029         case SWITCH_EXPR:
1030           {
1031             size_t i;
1032             tree vec = SWITCH_LABELS (stmt);
1033             size_t n = TREE_VEC_LENGTH (vec);
1034
1035             /* Replace all destination labels.  */
1036             for (i = 0; i < n; ++i)
1037               {
1038                 tree elt = TREE_VEC_ELT (vec, i);
1039                 tree label = main_block_label (CASE_LABEL (elt));
1040                 CASE_LABEL (elt) = label;
1041               }
1042             break;
1043           }
1044
1045         /* We have to handle GOTO_EXPRs until they're removed, and we don't
1046            remove them until after we've created the CFG edges.  */
1047         case GOTO_EXPR:
1048           if (! computed_goto_p (stmt))
1049             {
1050               GOTO_DESTINATION (stmt)
1051                 = main_block_label (GOTO_DESTINATION (stmt));
1052               break;
1053             }
1054
1055         default:
1056           break;
1057       }
1058     }
1059
1060   for_each_eh_region (update_eh_label);
1061
1062   /* Finally, purge dead labels.  All user-defined labels and labels that
1063      can be the target of non-local gotos and labels which have their
1064      address taken are preserved.  */
1065   FOR_EACH_BB (bb)
1066     {
1067       block_stmt_iterator i;
1068       tree label_for_this_bb = label_for_bb[bb->index];
1069
1070       if (! label_for_this_bb)
1071         continue;
1072
1073       for (i = bsi_start (bb); !bsi_end_p (i); )
1074         {
1075           tree label, stmt = bsi_stmt (i);
1076
1077           if (TREE_CODE (stmt) != LABEL_EXPR)
1078             break;
1079
1080           label = LABEL_EXPR_LABEL (stmt);
1081
1082           if (label == label_for_this_bb
1083               || ! DECL_ARTIFICIAL (label)
1084               || DECL_NONLOCAL (label)
1085               || FORCED_LABEL (label))
1086             bsi_next (&i);
1087           else
1088             bsi_remove (&i, true);
1089         }
1090     }
1091
1092   free (label_for_bb);
1093 }
1094
1095 /* Look for blocks ending in a multiway branch (a SWITCH_EXPR in GIMPLE),
1096    and scan the sorted vector of cases.  Combine the ones jumping to the
1097    same label.
1098    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1099
1100 void
1101 group_case_labels (void)
1102 {
1103   basic_block bb;
1104
1105   FOR_EACH_BB (bb)
1106     {
1107       tree stmt = last_stmt (bb);
1108       if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
1109         {
1110           tree labels = SWITCH_LABELS (stmt);
1111           int old_size = TREE_VEC_LENGTH (labels);
1112           int i, j, new_size = old_size;
1113           tree default_case = TREE_VEC_ELT (labels, old_size - 1);
1114           tree default_label;
1115
1116           /* The default label is always the last case in a switch
1117              statement after gimplification.  */
1118           default_label = CASE_LABEL (default_case);
1119
1120           /* Look for possible opportunities to merge cases.
1121              Ignore the last element of the label vector because it
1122              must be the default case.  */
1123           i = 0;
1124           while (i < old_size - 1)
1125             {
1126               tree base_case, base_label, base_high;
1127               base_case = TREE_VEC_ELT (labels, i);
1128
1129               gcc_assert (base_case);
1130               base_label = CASE_LABEL (base_case);
1131
1132               /* Discard cases that have the same destination as the
1133                  default case.  */
1134               if (base_label == default_label)
1135                 {
1136                   TREE_VEC_ELT (labels, i) = NULL_TREE;
1137                   i++;
1138                   new_size--;
1139                   continue;
1140                 }
1141
1142               base_high = CASE_HIGH (base_case) ?
1143                 CASE_HIGH (base_case) : CASE_LOW (base_case);
1144               i++;
1145               /* Try to merge case labels.  Break out when we reach the end
1146                  of the label vector or when we cannot merge the next case
1147                  label with the current one.  */
1148               while (i < old_size - 1)
1149                 {
1150                   tree merge_case = TREE_VEC_ELT (labels, i);
1151                   tree merge_label = CASE_LABEL (merge_case);
1152                   tree t = int_const_binop (PLUS_EXPR, base_high,
1153                                             integer_one_node, 1);
1154
1155                   /* Merge the cases if they jump to the same place,
1156                      and their ranges are consecutive.  */
1157                   if (merge_label == base_label
1158                       && tree_int_cst_equal (CASE_LOW (merge_case), t))
1159                     {
1160                       base_high = CASE_HIGH (merge_case) ?
1161                         CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1162                       CASE_HIGH (base_case) = base_high;
1163                       TREE_VEC_ELT (labels, i) = NULL_TREE;
1164                       new_size--;
1165                       i++;
1166                     }
1167                   else
1168                     break;
1169                 }
1170             }
1171
1172           /* Compress the case labels in the label vector, and adjust the
1173              length of the vector.  */
1174           for (i = 0, j = 0; i < new_size; i++)
1175             {
1176               while (! TREE_VEC_ELT (labels, j))
1177                 j++;
1178               TREE_VEC_ELT (labels, i) = TREE_VEC_ELT (labels, j++);
1179             }
1180           TREE_VEC_LENGTH (labels) = new_size;
1181         }
1182     }
1183 }
1184
1185 /* Checks whether we can merge block B into block A.  */
1186
1187 static bool
1188 tree_can_merge_blocks_p (basic_block a, basic_block b)
1189 {
1190   tree stmt;
1191   block_stmt_iterator bsi;
1192   tree phi;
1193
1194   if (!single_succ_p (a))
1195     return false;
1196
1197   if (single_succ_edge (a)->flags & EDGE_ABNORMAL)
1198     return false;
1199
1200   if (single_succ (a) != b)
1201     return false;
1202
1203   if (!single_pred_p (b))
1204     return false;
1205
1206   if (b == EXIT_BLOCK_PTR)
1207     return false;
1208
1209   /* If A ends by a statement causing exceptions or something similar, we
1210      cannot merge the blocks.  */
1211   stmt = last_stmt (a);
1212   if (stmt && stmt_ends_bb_p (stmt))
1213     return false;
1214
1215   /* Do not allow a block with only a non-local label to be merged.  */
1216   if (stmt && TREE_CODE (stmt) == LABEL_EXPR
1217       && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
1218     return false;
1219
1220   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1221      is not up-to-date, we cannot eliminate any phis.  */
1222   phi = phi_nodes (b);
1223   if (phi)
1224     {
1225       if (need_ssa_update_p ())
1226         return false;
1227
1228       for (; phi; phi = PHI_CHAIN (phi))
1229         if (!is_gimple_reg (PHI_RESULT (phi))
1230             && !may_propagate_copy (PHI_RESULT (phi), PHI_ARG_DEF (phi, 0)))
1231           return false;
1232     }
1233
1234   /* Do not remove user labels.  */
1235   for (bsi = bsi_start (b); !bsi_end_p (bsi); bsi_next (&bsi))
1236     {
1237       stmt = bsi_stmt (bsi);
1238       if (TREE_CODE (stmt) != LABEL_EXPR)
1239         break;
1240       if (!DECL_ARTIFICIAL (LABEL_EXPR_LABEL (stmt)))
1241         return false;
1242     }
1243
1244   /* Protect the loop latches.  */
1245   if (current_loops
1246       && b->loop_father->latch == b)
1247     return false;
1248
1249   return true;
1250 }
1251
1252 /* Replaces all uses of NAME by VAL.  */
1253
1254 void
1255 replace_uses_by (tree name, tree val)
1256 {
1257   imm_use_iterator imm_iter;
1258   use_operand_p use;
1259   tree stmt;
1260   edge e;
1261   unsigned i;
1262   VEC(tree,heap) *stmts = VEC_alloc (tree, heap, 20);
1263
1264   FOR_EACH_IMM_USE_SAFE (use, imm_iter, name)
1265     {
1266       stmt = USE_STMT (use);
1267       replace_exp (use, val);
1268
1269       if (TREE_CODE (stmt) == PHI_NODE)
1270         {
1271           e = PHI_ARG_EDGE (stmt, PHI_ARG_INDEX_FROM_USE (use));
1272           if (e->flags & EDGE_ABNORMAL)
1273             {
1274               /* This can only occur for virtual operands, since
1275                  for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1276                  would prevent replacement.  */
1277               gcc_assert (!is_gimple_reg (name));
1278               SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1279             }
1280         }
1281       else
1282         VEC_safe_push (tree, heap, stmts, stmt);
1283     }
1284
1285   /* We do not update the statements in the loop above.  Consider
1286      x = w * w;
1287
1288      If we performed the update in the first loop, the statement
1289      would be rescanned after first occurrence of w is replaced,
1290      the new uses would be placed to the beginning of the list,
1291      and we would never process them.  */
1292   for (i = 0; VEC_iterate (tree, stmts, i, stmt); i++)
1293     {
1294       tree rhs;
1295
1296       fold_stmt_inplace (stmt);
1297
1298       rhs = get_rhs (stmt);
1299       if (TREE_CODE (rhs) == ADDR_EXPR)
1300         recompute_tree_invariant_for_addr_expr (rhs);
1301
1302       maybe_clean_or_replace_eh_stmt (stmt, stmt);
1303       mark_new_vars_to_rename (stmt);
1304     }
1305
1306   VEC_free (tree, heap, stmts);
1307
1308   /* Also update the trees stored in loop structures.  */
1309   if (current_loops)
1310     {
1311       struct loop *loop;
1312
1313       for (i = 0; i < current_loops->num; i++)
1314         {
1315           loop = current_loops->parray[i];
1316           if (loop)
1317             substitute_in_loop_info (loop, name, val);
1318         }
1319     }
1320 }
1321
1322 /* Merge block B into block A.  */
1323
1324 static void
1325 tree_merge_blocks (basic_block a, basic_block b)
1326 {
1327   block_stmt_iterator bsi;
1328   tree_stmt_iterator last;
1329   tree phi;
1330
1331   if (dump_file)
1332     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1333
1334   /* Remove all single-valued PHI nodes from block B of the form
1335      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1336   bsi = bsi_last (a);
1337   for (phi = phi_nodes (b); phi; phi = phi_nodes (b))
1338     {
1339       tree def = PHI_RESULT (phi), use = PHI_ARG_DEF (phi, 0);
1340       tree copy;
1341       bool may_replace_uses = may_propagate_copy (def, use);
1342
1343       /* In case we have loops to care about, do not propagate arguments of
1344          loop closed ssa phi nodes.  */
1345       if (current_loops
1346           && is_gimple_reg (def)
1347           && TREE_CODE (use) == SSA_NAME
1348           && a->loop_father != b->loop_father)
1349         may_replace_uses = false;
1350
1351       if (!may_replace_uses)
1352         {
1353           gcc_assert (is_gimple_reg (def));
1354
1355           /* Note that just emitting the copies is fine -- there is no problem
1356              with ordering of phi nodes.  This is because A is the single
1357              predecessor of B, therefore results of the phi nodes cannot
1358              appear as arguments of the phi nodes.  */
1359           copy = build2 (MODIFY_EXPR, void_type_node, def, use);
1360           bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
1361           SET_PHI_RESULT (phi, NULL_TREE);
1362           SSA_NAME_DEF_STMT (def) = copy;
1363         }
1364       else
1365         replace_uses_by (def, use);
1366
1367       remove_phi_node (phi, NULL);
1368     }
1369
1370   /* Ensure that B follows A.  */
1371   move_block_after (b, a);
1372
1373   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1374   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1375
1376   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1377   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1378     {
1379       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1380         {
1381           tree label = bsi_stmt (bsi);
1382
1383           bsi_remove (&bsi, false);
1384           /* Now that we can thread computed gotos, we might have
1385              a situation where we have a forced label in block B
1386              However, the label at the start of block B might still be
1387              used in other ways (think about the runtime checking for
1388              Fortran assigned gotos).  So we can not just delete the
1389              label.  Instead we move the label to the start of block A.  */
1390           if (FORCED_LABEL (LABEL_EXPR_LABEL (label)))
1391             {
1392               block_stmt_iterator dest_bsi = bsi_start (a);
1393               bsi_insert_before (&dest_bsi, label, BSI_NEW_STMT);
1394             }
1395         }
1396       else
1397         {
1398           set_bb_for_stmt (bsi_stmt (bsi), a);
1399           bsi_next (&bsi);
1400         }
1401     }
1402
1403   /* Merge the chains.  */
1404   last = tsi_last (a->stmt_list);
1405   tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
1406   b->stmt_list = NULL;
1407 }
1408
1409
1410 /* Return the one of two successors of BB that is not reachable by a
1411    reached by a complex edge, if there is one.  Else, return BB.  We use
1412    this in optimizations that use post-dominators for their heuristics,
1413    to catch the cases in C++ where function calls are involved.  */
1414
1415 basic_block
1416 single_noncomplex_succ (basic_block bb)
1417 {
1418   edge e0, e1;
1419   if (EDGE_COUNT (bb->succs) != 2)
1420     return bb;
1421
1422   e0 = EDGE_SUCC (bb, 0);
1423   e1 = EDGE_SUCC (bb, 1);
1424   if (e0->flags & EDGE_COMPLEX)
1425     return e1->dest;
1426   if (e1->flags & EDGE_COMPLEX)
1427     return e0->dest;
1428
1429   return bb;
1430 }
1431
1432
1433
1434 /* Walk the function tree removing unnecessary statements.
1435
1436      * Empty statement nodes are removed
1437
1438      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1439
1440      * Unnecessary COND_EXPRs are removed
1441
1442      * Some unnecessary BIND_EXPRs are removed
1443
1444    Clearly more work could be done.  The trick is doing the analysis
1445    and removal fast enough to be a net improvement in compile times.
1446
1447    Note that when we remove a control structure such as a COND_EXPR
1448    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1449    to ensure we eliminate all the useless code.  */
1450
1451 struct rus_data
1452 {
1453   tree *last_goto;
1454   bool repeat;
1455   bool may_throw;
1456   bool may_branch;
1457   bool has_label;
1458 };
1459
1460 static void remove_useless_stmts_1 (tree *, struct rus_data *);
1461
1462 static bool
1463 remove_useless_stmts_warn_notreached (tree stmt)
1464 {
1465   if (EXPR_HAS_LOCATION (stmt))
1466     {
1467       location_t loc = EXPR_LOCATION (stmt);
1468       if (LOCATION_LINE (loc) > 0)
1469         {
1470           warning (0, "%Hwill never be executed", &loc);
1471           return true;
1472         }
1473     }
1474
1475   switch (TREE_CODE (stmt))
1476     {
1477     case STATEMENT_LIST:
1478       {
1479         tree_stmt_iterator i;
1480         for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
1481           if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
1482             return true;
1483       }
1484       break;
1485
1486     case COND_EXPR:
1487       if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
1488         return true;
1489       if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
1490         return true;
1491       if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
1492         return true;
1493       break;
1494
1495     case TRY_FINALLY_EXPR:
1496     case TRY_CATCH_EXPR:
1497       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
1498         return true;
1499       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
1500         return true;
1501       break;
1502
1503     case CATCH_EXPR:
1504       return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
1505     case EH_FILTER_EXPR:
1506       return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
1507     case BIND_EXPR:
1508       return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
1509
1510     default:
1511       /* Not a live container.  */
1512       break;
1513     }
1514
1515   return false;
1516 }
1517
1518 static void
1519 remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
1520 {
1521   tree then_clause, else_clause, cond;
1522   bool save_has_label, then_has_label, else_has_label;
1523
1524   save_has_label = data->has_label;
1525   data->has_label = false;
1526   data->last_goto = NULL;
1527
1528   remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
1529
1530   then_has_label = data->has_label;
1531   data->has_label = false;
1532   data->last_goto = NULL;
1533
1534   remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
1535
1536   else_has_label = data->has_label;
1537   data->has_label = save_has_label | then_has_label | else_has_label;
1538
1539   then_clause = COND_EXPR_THEN (*stmt_p);
1540   else_clause = COND_EXPR_ELSE (*stmt_p);
1541   cond = fold (COND_EXPR_COND (*stmt_p));
1542
1543   /* If neither arm does anything at all, we can remove the whole IF.  */
1544   if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
1545     {
1546       *stmt_p = build_empty_stmt ();
1547       data->repeat = true;
1548     }
1549
1550   /* If there are no reachable statements in an arm, then we can
1551      zap the entire conditional.  */
1552   else if (integer_nonzerop (cond) && !else_has_label)
1553     {
1554       if (warn_notreached)
1555         remove_useless_stmts_warn_notreached (else_clause);
1556       *stmt_p = then_clause;
1557       data->repeat = true;
1558     }
1559   else if (integer_zerop (cond) && !then_has_label)
1560     {
1561       if (warn_notreached)
1562         remove_useless_stmts_warn_notreached (then_clause);
1563       *stmt_p = else_clause;
1564       data->repeat = true;
1565     }
1566
1567   /* Check a couple of simple things on then/else with single stmts.  */
1568   else
1569     {
1570       tree then_stmt = expr_only (then_clause);
1571       tree else_stmt = expr_only (else_clause);
1572
1573       /* Notice branches to a common destination.  */
1574       if (then_stmt && else_stmt
1575           && TREE_CODE (then_stmt) == GOTO_EXPR
1576           && TREE_CODE (else_stmt) == GOTO_EXPR
1577           && (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
1578         {
1579           *stmt_p = then_stmt;
1580           data->repeat = true;
1581         }
1582
1583       /* If the THEN/ELSE clause merely assigns a value to a variable or
1584          parameter which is already known to contain that value, then
1585          remove the useless THEN/ELSE clause.  */
1586       else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1587         {
1588           if (else_stmt
1589               && TREE_CODE (else_stmt) == MODIFY_EXPR
1590               && TREE_OPERAND (else_stmt, 0) == cond
1591               && integer_zerop (TREE_OPERAND (else_stmt, 1)))
1592             COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
1593         }
1594       else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1595                && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1596                    || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1597                && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
1598         {
1599           tree stmt = (TREE_CODE (cond) == EQ_EXPR
1600                        ? then_stmt : else_stmt);
1601           tree *location = (TREE_CODE (cond) == EQ_EXPR
1602                             ? &COND_EXPR_THEN (*stmt_p)
1603                             : &COND_EXPR_ELSE (*stmt_p));
1604
1605           if (stmt
1606               && TREE_CODE (stmt) == MODIFY_EXPR
1607               && TREE_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
1608               && TREE_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
1609             *location = alloc_stmt_list ();
1610         }
1611     }
1612
1613   /* Protect GOTOs in the arm of COND_EXPRs from being removed.  They
1614      would be re-introduced during lowering.  */
1615   data->last_goto = NULL;
1616 }
1617
1618
1619 static void
1620 remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
1621 {
1622   bool save_may_branch, save_may_throw;
1623   bool this_may_branch, this_may_throw;
1624
1625   /* Collect may_branch and may_throw information for the body only.  */
1626   save_may_branch = data->may_branch;
1627   save_may_throw = data->may_throw;
1628   data->may_branch = false;
1629   data->may_throw = false;
1630   data->last_goto = NULL;
1631
1632   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1633
1634   this_may_branch = data->may_branch;
1635   this_may_throw = data->may_throw;
1636   data->may_branch |= save_may_branch;
1637   data->may_throw |= save_may_throw;
1638   data->last_goto = NULL;
1639
1640   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1641
1642   /* If the body is empty, then we can emit the FINALLY block without
1643      the enclosing TRY_FINALLY_EXPR.  */
1644   if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
1645     {
1646       *stmt_p = TREE_OPERAND (*stmt_p, 1);
1647       data->repeat = true;
1648     }
1649
1650   /* If the handler is empty, then we can emit the TRY block without
1651      the enclosing TRY_FINALLY_EXPR.  */
1652   else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1653     {
1654       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1655       data->repeat = true;
1656     }
1657
1658   /* If the body neither throws, nor branches, then we can safely
1659      string the TRY and FINALLY blocks together.  */
1660   else if (!this_may_branch && !this_may_throw)
1661     {
1662       tree stmt = *stmt_p;
1663       *stmt_p = TREE_OPERAND (stmt, 0);
1664       append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
1665       data->repeat = true;
1666     }
1667 }
1668
1669
1670 static void
1671 remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
1672 {
1673   bool save_may_throw, this_may_throw;
1674   tree_stmt_iterator i;
1675   tree stmt;
1676
1677   /* Collect may_throw information for the body only.  */
1678   save_may_throw = data->may_throw;
1679   data->may_throw = false;
1680   data->last_goto = NULL;
1681
1682   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1683
1684   this_may_throw = data->may_throw;
1685   data->may_throw = save_may_throw;
1686
1687   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1688   if (!this_may_throw)
1689     {
1690       if (warn_notreached)
1691         remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
1692       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1693       data->repeat = true;
1694       return;
1695     }
1696
1697   /* Process the catch clause specially.  We may be able to tell that
1698      no exceptions propagate past this point.  */
1699
1700   this_may_throw = true;
1701   i = tsi_start (TREE_OPERAND (*stmt_p, 1));
1702   stmt = tsi_stmt (i);
1703   data->last_goto = NULL;
1704
1705   switch (TREE_CODE (stmt))
1706     {
1707     case CATCH_EXPR:
1708       for (; !tsi_end_p (i); tsi_next (&i))
1709         {
1710           stmt = tsi_stmt (i);
1711           /* If we catch all exceptions, then the body does not
1712              propagate exceptions past this point.  */
1713           if (CATCH_TYPES (stmt) == NULL)
1714             this_may_throw = false;
1715           data->last_goto = NULL;
1716           remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
1717         }
1718       break;
1719
1720     case EH_FILTER_EXPR:
1721       if (EH_FILTER_MUST_NOT_THROW (stmt))
1722         this_may_throw = false;
1723       else if (EH_FILTER_TYPES (stmt) == NULL)
1724         this_may_throw = false;
1725       remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
1726       break;
1727
1728     default:
1729       /* Otherwise this is a cleanup.  */
1730       remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1731
1732       /* If the cleanup is empty, then we can emit the TRY block without
1733          the enclosing TRY_CATCH_EXPR.  */
1734       if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1735         {
1736           *stmt_p = TREE_OPERAND (*stmt_p, 0);
1737           data->repeat = true;
1738         }
1739       break;
1740     }
1741   data->may_throw |= this_may_throw;
1742 }
1743
1744
1745 static void
1746 remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
1747 {
1748   tree block;
1749
1750   /* First remove anything underneath the BIND_EXPR.  */
1751   remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
1752
1753   /* If the BIND_EXPR has no variables, then we can pull everything
1754      up one level and remove the BIND_EXPR, unless this is the toplevel
1755      BIND_EXPR for the current function or an inlined function.
1756
1757      When this situation occurs we will want to apply this
1758      optimization again.  */
1759   block = BIND_EXPR_BLOCK (*stmt_p);
1760   if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
1761       && *stmt_p != DECL_SAVED_TREE (current_function_decl)
1762       && (! block
1763           || ! BLOCK_ABSTRACT_ORIGIN (block)
1764           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1765               != FUNCTION_DECL)))
1766     {
1767       *stmt_p = BIND_EXPR_BODY (*stmt_p);
1768       data->repeat = true;
1769     }
1770 }
1771
1772
1773 static void
1774 remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
1775 {
1776   tree dest = GOTO_DESTINATION (*stmt_p);
1777
1778   data->may_branch = true;
1779   data->last_goto = NULL;
1780
1781   /* Record the last goto expr, so that we can delete it if unnecessary.  */
1782   if (TREE_CODE (dest) == LABEL_DECL)
1783     data->last_goto = stmt_p;
1784 }
1785
1786
1787 static void
1788 remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
1789 {
1790   tree label = LABEL_EXPR_LABEL (*stmt_p);
1791
1792   data->has_label = true;
1793
1794   /* We do want to jump across non-local label receiver code.  */
1795   if (DECL_NONLOCAL (label))
1796     data->last_goto = NULL;
1797
1798   else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
1799     {
1800       *data->last_goto = build_empty_stmt ();
1801       data->repeat = true;
1802     }
1803
1804   /* ??? Add something here to delete unused labels.  */
1805 }
1806
1807
1808 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1809    decl.  This allows us to eliminate redundant or useless
1810    calls to "const" functions.
1811
1812    Gimplifier already does the same operation, but we may notice functions
1813    being const and pure once their calls has been gimplified, so we need
1814    to update the flag.  */
1815
1816 static void
1817 update_call_expr_flags (tree call)
1818 {
1819   tree decl = get_callee_fndecl (call);
1820   if (!decl)
1821     return;
1822   if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1823     TREE_SIDE_EFFECTS (call) = 0;
1824   if (TREE_NOTHROW (decl))
1825     TREE_NOTHROW (call) = 1;
1826 }
1827
1828
1829 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1830
1831 void
1832 notice_special_calls (tree t)
1833 {
1834   int flags = call_expr_flags (t);
1835
1836   if (flags & ECF_MAY_BE_ALLOCA)
1837     current_function_calls_alloca = true;
1838   if (flags & ECF_RETURNS_TWICE)
1839     current_function_calls_setjmp = true;
1840 }
1841
1842
1843 /* Clear flags set by notice_special_calls.  Used by dead code removal
1844    to update the flags.  */
1845
1846 void
1847 clear_special_calls (void)
1848 {
1849   current_function_calls_alloca = false;
1850   current_function_calls_setjmp = false;
1851 }
1852
1853
1854 static void
1855 remove_useless_stmts_1 (tree *tp, struct rus_data *data)
1856 {
1857   tree t = *tp, op;
1858
1859   switch (TREE_CODE (t))
1860     {
1861     case COND_EXPR:
1862       remove_useless_stmts_cond (tp, data);
1863       break;
1864
1865     case TRY_FINALLY_EXPR:
1866       remove_useless_stmts_tf (tp, data);
1867       break;
1868
1869     case TRY_CATCH_EXPR:
1870       remove_useless_stmts_tc (tp, data);
1871       break;
1872
1873     case BIND_EXPR:
1874       remove_useless_stmts_bind (tp, data);
1875       break;
1876
1877     case GOTO_EXPR:
1878       remove_useless_stmts_goto (tp, data);
1879       break;
1880
1881     case LABEL_EXPR:
1882       remove_useless_stmts_label (tp, data);
1883       break;
1884
1885     case RETURN_EXPR:
1886       fold_stmt (tp);
1887       data->last_goto = NULL;
1888       data->may_branch = true;
1889       break;
1890
1891     case CALL_EXPR:
1892       fold_stmt (tp);
1893       data->last_goto = NULL;
1894       notice_special_calls (t);
1895       update_call_expr_flags (t);
1896       if (tree_could_throw_p (t))
1897         data->may_throw = true;
1898       break;
1899
1900     case MODIFY_EXPR:
1901       data->last_goto = NULL;
1902       fold_stmt (tp);
1903       op = get_call_expr_in (t);
1904       if (op)
1905         {
1906           update_call_expr_flags (op);
1907           notice_special_calls (op);
1908         }
1909       if (tree_could_throw_p (t))
1910         data->may_throw = true;
1911       break;
1912
1913     case STATEMENT_LIST:
1914       {
1915         tree_stmt_iterator i = tsi_start (t);
1916         while (!tsi_end_p (i))
1917           {
1918             t = tsi_stmt (i);
1919             if (IS_EMPTY_STMT (t))
1920               {
1921                 tsi_delink (&i);
1922                 continue;
1923               }
1924
1925             remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
1926
1927             t = tsi_stmt (i);
1928             if (TREE_CODE (t) == STATEMENT_LIST)
1929               {
1930                 tsi_link_before (&i, t, TSI_SAME_STMT);
1931                 tsi_delink (&i);
1932               }
1933             else
1934               tsi_next (&i);
1935           }
1936       }
1937       break;
1938     case ASM_EXPR:
1939       fold_stmt (tp);
1940       data->last_goto = NULL;
1941       break;
1942
1943     default:
1944       data->last_goto = NULL;
1945       break;
1946     }
1947 }
1948
1949 static unsigned int
1950 remove_useless_stmts (void)
1951 {
1952   struct rus_data data;
1953
1954   clear_special_calls ();
1955
1956   do
1957     {
1958       memset (&data, 0, sizeof (data));
1959       remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1960     }
1961   while (data.repeat);
1962   return 0;
1963 }
1964
1965
1966 struct tree_opt_pass pass_remove_useless_stmts =
1967 {
1968   "useless",                            /* name */
1969   NULL,                                 /* gate */
1970   remove_useless_stmts,                 /* execute */
1971   NULL,                                 /* sub */
1972   NULL,                                 /* next */
1973   0,                                    /* static_pass_number */
1974   0,                                    /* tv_id */
1975   PROP_gimple_any,                      /* properties_required */
1976   0,                                    /* properties_provided */
1977   0,                                    /* properties_destroyed */
1978   0,                                    /* todo_flags_start */
1979   TODO_dump_func,                       /* todo_flags_finish */
1980   0                                     /* letter */
1981 };
1982
1983 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1984
1985 static void
1986 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1987 {
1988   tree phi;
1989
1990   /* Since this block is no longer reachable, we can just delete all
1991      of its PHI nodes.  */
1992   phi = phi_nodes (bb);
1993   while (phi)
1994     {
1995       tree next = PHI_CHAIN (phi);
1996       remove_phi_node (phi, NULL_TREE);
1997       phi = next;
1998     }
1999
2000   /* Remove edges to BB's successors.  */
2001   while (EDGE_COUNT (bb->succs) > 0)
2002     remove_edge (EDGE_SUCC (bb, 0));
2003 }
2004
2005
2006 /* Remove statements of basic block BB.  */
2007
2008 static void
2009 remove_bb (basic_block bb)
2010 {
2011   block_stmt_iterator i;
2012 #ifdef USE_MAPPED_LOCATION
2013   source_location loc = UNKNOWN_LOCATION;
2014 #else
2015   source_locus loc = 0;
2016 #endif
2017
2018   if (dump_file)
2019     {
2020       fprintf (dump_file, "Removing basic block %d\n", bb->index);
2021       if (dump_flags & TDF_DETAILS)
2022         {
2023           dump_bb (bb, dump_file, 0);
2024           fprintf (dump_file, "\n");
2025         }
2026     }
2027
2028   /* If we remove the header or the latch of a loop, mark the loop for
2029      removal by setting its header and latch to NULL.  */
2030   if (current_loops)
2031     {
2032       struct loop *loop = bb->loop_father;
2033
2034       if (loop->latch == bb
2035           || loop->header == bb)
2036         {
2037           loop->latch = NULL;
2038           loop->header = NULL;
2039
2040           /* Also clean up the information associated with the loop.  Updating
2041              it would waste time. More importantly, it may refer to ssa
2042              names that were defined in other removed basic block -- these
2043              ssa names are now removed and invalid.  */
2044           free_numbers_of_iterations_estimates_loop (loop);
2045         }
2046     }
2047
2048   /* Remove all the instructions in the block.  */
2049   for (i = bsi_start (bb); !bsi_end_p (i);)
2050     {
2051       tree stmt = bsi_stmt (i);
2052       if (TREE_CODE (stmt) == LABEL_EXPR
2053           && (FORCED_LABEL (LABEL_EXPR_LABEL (stmt))
2054               || DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))))
2055         {
2056           basic_block new_bb;
2057           block_stmt_iterator new_bsi;
2058
2059           /* A non-reachable non-local label may still be referenced.
2060              But it no longer needs to carry the extra semantics of
2061              non-locality.  */
2062           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
2063             {
2064               DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)) = 0;
2065               FORCED_LABEL (LABEL_EXPR_LABEL (stmt)) = 1;
2066             }
2067
2068           new_bb = bb->prev_bb;
2069           new_bsi = bsi_start (new_bb);
2070           bsi_remove (&i, false);
2071           bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
2072         }
2073       else
2074         {
2075           /* Release SSA definitions if we are in SSA.  Note that we
2076              may be called when not in SSA.  For example,
2077              final_cleanup calls this function via
2078              cleanup_tree_cfg.  */
2079           if (in_ssa_p)
2080             release_defs (stmt);
2081
2082           bsi_remove (&i, true);
2083         }
2084
2085       /* Don't warn for removed gotos.  Gotos are often removed due to
2086          jump threading, thus resulting in bogus warnings.  Not great,
2087          since this way we lose warnings for gotos in the original
2088          program that are indeed unreachable.  */
2089       if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
2090         {
2091 #ifdef USE_MAPPED_LOCATION
2092           if (EXPR_HAS_LOCATION (stmt))
2093             loc = EXPR_LOCATION (stmt);
2094 #else
2095           source_locus t;
2096           t = EXPR_LOCUS (stmt);
2097           if (t && LOCATION_LINE (*t) > 0)
2098             loc = t;
2099 #endif
2100         }
2101     }
2102
2103   /* If requested, give a warning that the first statement in the
2104      block is unreachable.  We walk statements backwards in the
2105      loop above, so the last statement we process is the first statement
2106      in the block.  */
2107 #ifdef USE_MAPPED_LOCATION
2108   if (loc > BUILTINS_LOCATION)
2109     warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
2110 #else
2111   if (loc)
2112     warning (OPT_Wunreachable_code, "%Hwill never be executed", loc);
2113 #endif
2114
2115   remove_phi_nodes_and_edges_for_unreachable_block (bb);
2116 }
2117
2118
2119 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2120    predicate VAL, return the edge that will be taken out of the block.
2121    If VAL does not match a unique edge, NULL is returned.  */
2122
2123 edge
2124 find_taken_edge (basic_block bb, tree val)
2125 {
2126   tree stmt;
2127
2128   stmt = last_stmt (bb);
2129
2130   gcc_assert (stmt);
2131   gcc_assert (is_ctrl_stmt (stmt));
2132   gcc_assert (val);
2133
2134   if (! is_gimple_min_invariant (val))
2135     return NULL;
2136
2137   if (TREE_CODE (stmt) == COND_EXPR)
2138     return find_taken_edge_cond_expr (bb, val);
2139
2140   if (TREE_CODE (stmt) == SWITCH_EXPR)
2141     return find_taken_edge_switch_expr (bb, val);
2142
2143   if (computed_goto_p (stmt))
2144     return find_taken_edge_computed_goto (bb, TREE_OPERAND( val, 0));
2145
2146   gcc_unreachable ();
2147 }
2148
2149 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2150    statement, determine which of the outgoing edges will be taken out of the
2151    block.  Return NULL if either edge may be taken.  */
2152
2153 static edge
2154 find_taken_edge_computed_goto (basic_block bb, tree val)
2155 {
2156   basic_block dest;
2157   edge e = NULL;
2158
2159   dest = label_to_block (val);
2160   if (dest)
2161     {
2162       e = find_edge (bb, dest);
2163       gcc_assert (e != NULL);
2164     }
2165
2166   return e;
2167 }
2168
2169 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2170    statement, determine which of the two edges will be taken out of the
2171    block.  Return NULL if either edge may be taken.  */
2172
2173 static edge
2174 find_taken_edge_cond_expr (basic_block bb, tree val)
2175 {
2176   edge true_edge, false_edge;
2177
2178   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2179
2180   gcc_assert (TREE_CODE (val) == INTEGER_CST);
2181   return (zero_p (val) ? false_edge : true_edge);
2182 }
2183
2184 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2185    statement, determine which edge will be taken out of the block.  Return
2186    NULL if any edge may be taken.  */
2187
2188 static edge
2189 find_taken_edge_switch_expr (basic_block bb, tree val)
2190 {
2191   tree switch_expr, taken_case;
2192   basic_block dest_bb;
2193   edge e;
2194
2195   switch_expr = last_stmt (bb);
2196   taken_case = find_case_label_for_value (switch_expr, val);
2197   dest_bb = label_to_block (CASE_LABEL (taken_case));
2198
2199   e = find_edge (bb, dest_bb);
2200   gcc_assert (e);
2201   return e;
2202 }
2203
2204
2205 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2206    We can make optimal use here of the fact that the case labels are
2207    sorted: We can do a binary search for a case matching VAL.  */
2208
2209 static tree
2210 find_case_label_for_value (tree switch_expr, tree val)
2211 {
2212   tree vec = SWITCH_LABELS (switch_expr);
2213   size_t low, high, n = TREE_VEC_LENGTH (vec);
2214   tree default_case = TREE_VEC_ELT (vec, n - 1);
2215
2216   for (low = -1, high = n - 1; high - low > 1; )
2217     {
2218       size_t i = (high + low) / 2;
2219       tree t = TREE_VEC_ELT (vec, i);
2220       int cmp;
2221
2222       /* Cache the result of comparing CASE_LOW and val.  */
2223       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2224
2225       if (cmp > 0)
2226         high = i;
2227       else
2228         low = i;
2229
2230       if (CASE_HIGH (t) == NULL)
2231         {
2232           /* A singe-valued case label.  */
2233           if (cmp == 0)
2234             return t;
2235         }
2236       else
2237         {
2238           /* A case range.  We can only handle integer ranges.  */
2239           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2240             return t;
2241         }
2242     }
2243
2244   return default_case;
2245 }
2246
2247
2248
2249
2250 /*---------------------------------------------------------------------------
2251                               Debugging functions
2252 ---------------------------------------------------------------------------*/
2253
2254 /* Dump tree-specific information of block BB to file OUTF.  */
2255
2256 void
2257 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2258 {
2259   dump_generic_bb (outf, bb, indent, TDF_VOPS);
2260 }
2261
2262
2263 /* Dump a basic block on stderr.  */
2264
2265 void
2266 debug_tree_bb (basic_block bb)
2267 {
2268   dump_bb (bb, stderr, 0);
2269 }
2270
2271
2272 /* Dump basic block with index N on stderr.  */
2273
2274 basic_block
2275 debug_tree_bb_n (int n)
2276 {
2277   debug_tree_bb (BASIC_BLOCK (n));
2278   return BASIC_BLOCK (n);
2279 }
2280
2281
2282 /* Dump the CFG on stderr.
2283
2284    FLAGS are the same used by the tree dumping functions
2285    (see TDF_* in tree.h).  */
2286
2287 void
2288 debug_tree_cfg (int flags)
2289 {
2290   dump_tree_cfg (stderr, flags);
2291 }
2292
2293
2294 /* Dump the program showing basic block boundaries on the given FILE.
2295
2296    FLAGS are the same used by the tree dumping functions (see TDF_* in
2297    tree.h).  */
2298
2299 void
2300 dump_tree_cfg (FILE *file, int flags)
2301 {
2302   if (flags & TDF_DETAILS)
2303     {
2304       const char *funcname
2305         = lang_hooks.decl_printable_name (current_function_decl, 2);
2306
2307       fputc ('\n', file);
2308       fprintf (file, ";; Function %s\n\n", funcname);
2309       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2310                n_basic_blocks, n_edges, last_basic_block);
2311
2312       brief_dump_cfg (file);
2313       fprintf (file, "\n");
2314     }
2315
2316   if (flags & TDF_STATS)
2317     dump_cfg_stats (file);
2318
2319   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2320 }
2321
2322
2323 /* Dump CFG statistics on FILE.  */
2324
2325 void
2326 dump_cfg_stats (FILE *file)
2327 {
2328   static long max_num_merged_labels = 0;
2329   unsigned long size, total = 0;
2330   long num_edges;
2331   basic_block bb;
2332   const char * const fmt_str   = "%-30s%-13s%12s\n";
2333   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2334   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2335   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2336   const char *funcname
2337     = lang_hooks.decl_printable_name (current_function_decl, 2);
2338
2339
2340   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2341
2342   fprintf (file, "---------------------------------------------------------\n");
2343   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2344   fprintf (file, fmt_str, "", "  instances  ", "used ");
2345   fprintf (file, "---------------------------------------------------------\n");
2346
2347   size = n_basic_blocks * sizeof (struct basic_block_def);
2348   total += size;
2349   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2350            SCALE (size), LABEL (size));
2351
2352   num_edges = 0;
2353   FOR_EACH_BB (bb)
2354     num_edges += EDGE_COUNT (bb->succs);
2355   size = num_edges * sizeof (struct edge_def);
2356   total += size;
2357   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2358
2359   fprintf (file, "---------------------------------------------------------\n");
2360   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2361            LABEL (total));
2362   fprintf (file, "---------------------------------------------------------\n");
2363   fprintf (file, "\n");
2364
2365   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2366     max_num_merged_labels = cfg_stats.num_merged_labels;
2367
2368   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2369            cfg_stats.num_merged_labels, max_num_merged_labels);
2370
2371   fprintf (file, "\n");
2372 }
2373
2374
2375 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2376    linked in the final executable.  */
2377
2378 void
2379 debug_cfg_stats (void)
2380 {
2381   dump_cfg_stats (stderr);
2382 }
2383
2384
2385 /* Dump the flowgraph to a .vcg FILE.  */
2386
2387 static void
2388 tree_cfg2vcg (FILE *file)
2389 {
2390   edge e;
2391   edge_iterator ei;
2392   basic_block bb;
2393   const char *funcname
2394     = lang_hooks.decl_printable_name (current_function_decl, 2);
2395
2396   /* Write the file header.  */
2397   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2398   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2399   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2400
2401   /* Write blocks and edges.  */
2402   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2403     {
2404       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2405                e->dest->index);
2406
2407       if (e->flags & EDGE_FAKE)
2408         fprintf (file, " linestyle: dotted priority: 10");
2409       else
2410         fprintf (file, " linestyle: solid priority: 100");
2411
2412       fprintf (file, " }\n");
2413     }
2414   fputc ('\n', file);
2415
2416   FOR_EACH_BB (bb)
2417     {
2418       enum tree_code head_code, end_code;
2419       const char *head_name, *end_name;
2420       int head_line = 0;
2421       int end_line = 0;
2422       tree first = first_stmt (bb);
2423       tree last = last_stmt (bb);
2424
2425       if (first)
2426         {
2427           head_code = TREE_CODE (first);
2428           head_name = tree_code_name[head_code];
2429           head_line = get_lineno (first);
2430         }
2431       else
2432         head_name = "no-statement";
2433
2434       if (last)
2435         {
2436           end_code = TREE_CODE (last);
2437           end_name = tree_code_name[end_code];
2438           end_line = get_lineno (last);
2439         }
2440       else
2441         end_name = "no-statement";
2442
2443       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2444                bb->index, bb->index, head_name, head_line, end_name,
2445                end_line);
2446
2447       FOR_EACH_EDGE (e, ei, bb->succs)
2448         {
2449           if (e->dest == EXIT_BLOCK_PTR)
2450             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2451           else
2452             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2453
2454           if (e->flags & EDGE_FAKE)
2455             fprintf (file, " priority: 10 linestyle: dotted");
2456           else
2457             fprintf (file, " priority: 100 linestyle: solid");
2458
2459           fprintf (file, " }\n");
2460         }
2461
2462       if (bb->next_bb != EXIT_BLOCK_PTR)
2463         fputc ('\n', file);
2464     }
2465
2466   fputs ("}\n\n", file);
2467 }
2468
2469
2470
2471 /*---------------------------------------------------------------------------
2472                              Miscellaneous helpers
2473 ---------------------------------------------------------------------------*/
2474
2475 /* Return true if T represents a stmt that always transfers control.  */
2476
2477 bool
2478 is_ctrl_stmt (tree t)
2479 {
2480   return (TREE_CODE (t) == COND_EXPR
2481           || TREE_CODE (t) == SWITCH_EXPR
2482           || TREE_CODE (t) == GOTO_EXPR
2483           || TREE_CODE (t) == RETURN_EXPR
2484           || TREE_CODE (t) == RESX_EXPR);
2485 }
2486
2487
2488 /* Return true if T is a statement that may alter the flow of control
2489    (e.g., a call to a non-returning function).  */
2490
2491 bool
2492 is_ctrl_altering_stmt (tree t)
2493 {
2494   tree call;
2495
2496   gcc_assert (t);
2497   call = get_call_expr_in (t);
2498   if (call)
2499     {
2500       /* A non-pure/const CALL_EXPR alters flow control if the current
2501          function has nonlocal labels.  */
2502       if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
2503         return true;
2504
2505       /* A CALL_EXPR also alters control flow if it does not return.  */
2506       if (call_expr_flags (call) & ECF_NORETURN)
2507         return true;
2508     }
2509
2510   /* OpenMP directives alter control flow.  */
2511   if (OMP_DIRECTIVE_P (t))
2512     return true;
2513
2514   /* If a statement can throw, it alters control flow.  */
2515   return tree_can_throw_internal (t);
2516 }
2517
2518
2519 /* Return true if T is a computed goto.  */
2520
2521 bool
2522 computed_goto_p (tree t)
2523 {
2524   return (TREE_CODE (t) == GOTO_EXPR
2525           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2526 }
2527
2528
2529 /* Checks whether EXPR is a simple local goto.  */
2530
2531 bool
2532 simple_goto_p (tree expr)
2533 {
2534   return (TREE_CODE (expr) == GOTO_EXPR
2535           && TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL);
2536 }
2537
2538
2539 /* Return true if T should start a new basic block.  PREV_T is the
2540    statement preceding T.  It is used when T is a label or a case label.
2541    Labels should only start a new basic block if their previous statement
2542    wasn't a label.  Otherwise, sequence of labels would generate
2543    unnecessary basic blocks that only contain a single label.  */
2544
2545 static inline bool
2546 stmt_starts_bb_p (tree t, tree prev_t)
2547 {
2548   if (t == NULL_TREE)
2549     return false;
2550
2551   /* LABEL_EXPRs start a new basic block only if the preceding
2552      statement wasn't a label of the same type.  This prevents the
2553      creation of consecutive blocks that have nothing but a single
2554      label.  */
2555   if (TREE_CODE (t) == LABEL_EXPR)
2556     {
2557       /* Nonlocal and computed GOTO targets always start a new block.  */
2558       if (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2559           || FORCED_LABEL (LABEL_EXPR_LABEL (t)))
2560         return true;
2561
2562       if (prev_t && TREE_CODE (prev_t) == LABEL_EXPR)
2563         {
2564           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2565             return true;
2566
2567           cfg_stats.num_merged_labels++;
2568           return false;
2569         }
2570       else
2571         return true;
2572     }
2573
2574   return false;
2575 }
2576
2577
2578 /* Return true if T should end a basic block.  */
2579
2580 bool
2581 stmt_ends_bb_p (tree t)
2582 {
2583   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2584 }
2585
2586
2587 /* Add gotos that used to be represented implicitly in the CFG.  */
2588
2589 void
2590 disband_implicit_edges (void)
2591 {
2592   basic_block bb;
2593   block_stmt_iterator last;
2594   edge e;
2595   edge_iterator ei;
2596   tree stmt, label;
2597
2598   FOR_EACH_BB (bb)
2599     {
2600       last = bsi_last (bb);
2601       stmt = last_stmt (bb);
2602
2603       if (stmt && TREE_CODE (stmt) == COND_EXPR)
2604         {
2605           /* Remove superfluous gotos from COND_EXPR branches.  Moved
2606              from cfg_remove_useless_stmts here since it violates the
2607              invariants for tree--cfg correspondence and thus fits better
2608              here where we do it anyway.  */
2609           e = find_edge (bb, bb->next_bb);
2610           if (e)
2611             {
2612               if (e->flags & EDGE_TRUE_VALUE)
2613                 COND_EXPR_THEN (stmt) = build_empty_stmt ();
2614               else if (e->flags & EDGE_FALSE_VALUE)
2615                 COND_EXPR_ELSE (stmt) = build_empty_stmt ();
2616               else
2617                 gcc_unreachable ();
2618               e->flags |= EDGE_FALLTHRU;
2619             }
2620
2621           continue;
2622         }
2623
2624       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
2625         {
2626           /* Remove the RETURN_EXPR if we may fall though to the exit
2627              instead.  */
2628           gcc_assert (single_succ_p (bb));
2629           gcc_assert (single_succ (bb) == EXIT_BLOCK_PTR);
2630
2631           if (bb->next_bb == EXIT_BLOCK_PTR
2632               && !TREE_OPERAND (stmt, 0))
2633             {
2634               bsi_remove (&last, true);
2635               single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
2636             }
2637           continue;
2638         }
2639
2640       /* There can be no fallthru edge if the last statement is a control
2641          one.  */
2642       if (stmt && is_ctrl_stmt (stmt))
2643         continue;
2644
2645       /* Find a fallthru edge and emit the goto if necessary.  */
2646       FOR_EACH_EDGE (e, ei, bb->succs)
2647         if (e->flags & EDGE_FALLTHRU)
2648           break;
2649
2650       if (!e || e->dest == bb->next_bb)
2651         continue;
2652
2653       gcc_assert (e->dest != EXIT_BLOCK_PTR);
2654       label = tree_block_label (e->dest);
2655
2656       stmt = build1 (GOTO_EXPR, void_type_node, label);
2657 #ifdef USE_MAPPED_LOCATION
2658       SET_EXPR_LOCATION (stmt, e->goto_locus);
2659 #else
2660       SET_EXPR_LOCUS (stmt, e->goto_locus);
2661 #endif
2662       bsi_insert_after (&last, stmt, BSI_NEW_STMT);
2663       e->flags &= ~EDGE_FALLTHRU;
2664     }
2665 }
2666
2667 /* Remove block annotations and other datastructures.  */
2668
2669 void
2670 delete_tree_cfg_annotations (void)
2671 {
2672   label_to_block_map = NULL;
2673 }
2674
2675
2676 /* Return the first statement in basic block BB.  */
2677
2678 tree
2679 first_stmt (basic_block bb)
2680 {
2681   block_stmt_iterator i = bsi_start (bb);
2682   return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2683 }
2684
2685
2686 /* Return the last statement in basic block BB.  */
2687
2688 tree
2689 last_stmt (basic_block bb)
2690 {
2691   block_stmt_iterator b = bsi_last (bb);
2692   return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2693 }
2694
2695
2696 /* Return a pointer to the last statement in block BB.  */
2697
2698 tree *
2699 last_stmt_ptr (basic_block bb)
2700 {
2701   block_stmt_iterator last = bsi_last (bb);
2702   return !bsi_end_p (last) ? bsi_stmt_ptr (last) : NULL;
2703 }
2704
2705
2706 /* Return the last statement of an otherwise empty block.  Return NULL
2707    if the block is totally empty, or if it contains more than one
2708    statement.  */
2709
2710 tree
2711 last_and_only_stmt (basic_block bb)
2712 {
2713   block_stmt_iterator i = bsi_last (bb);
2714   tree last, prev;
2715
2716   if (bsi_end_p (i))
2717     return NULL_TREE;
2718
2719   last = bsi_stmt (i);
2720   bsi_prev (&i);
2721   if (bsi_end_p (i))
2722     return last;
2723
2724   /* Empty statements should no longer appear in the instruction stream.
2725      Everything that might have appeared before should be deleted by
2726      remove_useless_stmts, and the optimizers should just bsi_remove
2727      instead of smashing with build_empty_stmt.
2728
2729      Thus the only thing that should appear here in a block containing
2730      one executable statement is a label.  */
2731   prev = bsi_stmt (i);
2732   if (TREE_CODE (prev) == LABEL_EXPR)
2733     return last;
2734   else
2735     return NULL_TREE;
2736 }
2737
2738
2739 /* Mark BB as the basic block holding statement T.  */
2740
2741 void
2742 set_bb_for_stmt (tree t, basic_block bb)
2743 {
2744   if (TREE_CODE (t) == PHI_NODE)
2745     PHI_BB (t) = bb;
2746   else if (TREE_CODE (t) == STATEMENT_LIST)
2747     {
2748       tree_stmt_iterator i;
2749       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2750         set_bb_for_stmt (tsi_stmt (i), bb);
2751     }
2752   else
2753     {
2754       stmt_ann_t ann = get_stmt_ann (t);
2755       ann->bb = bb;
2756
2757       /* If the statement is a label, add the label to block-to-labels map
2758         so that we can speed up edge creation for GOTO_EXPRs.  */
2759       if (TREE_CODE (t) == LABEL_EXPR)
2760         {
2761           int uid;
2762
2763           t = LABEL_EXPR_LABEL (t);
2764           uid = LABEL_DECL_UID (t);
2765           if (uid == -1)
2766             {
2767               unsigned old_len = VEC_length (basic_block, label_to_block_map);
2768               LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
2769               if (old_len <= (unsigned) uid)
2770                 {
2771                   basic_block *addr;
2772                   unsigned new_len = 3 * uid / 2;
2773
2774                   VEC_safe_grow (basic_block, gc, label_to_block_map,
2775                                  new_len);
2776                   addr = VEC_address (basic_block, label_to_block_map);
2777                   memset (&addr[old_len],
2778                           0, sizeof (basic_block) * (new_len - old_len));
2779                 }
2780             }
2781           else
2782             /* We're moving an existing label.  Make sure that we've
2783                 removed it from the old block.  */
2784             gcc_assert (!bb
2785                         || !VEC_index (basic_block, label_to_block_map, uid));
2786           VEC_replace (basic_block, label_to_block_map, uid, bb);
2787         }
2788     }
2789 }
2790
2791 /* Finds iterator for STMT.  */
2792
2793 extern block_stmt_iterator
2794 bsi_for_stmt (tree stmt)
2795 {
2796   block_stmt_iterator bsi;
2797
2798   for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2799     if (bsi_stmt (bsi) == stmt)
2800       return bsi;
2801
2802   gcc_unreachable ();
2803 }
2804
2805 /* Mark statement T as modified, and update it.  */
2806 static inline void
2807 update_modified_stmts (tree t)
2808 {
2809   if (TREE_CODE (t) == STATEMENT_LIST)
2810     {
2811       tree_stmt_iterator i;
2812       tree stmt;
2813       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2814         {
2815           stmt = tsi_stmt (i);
2816           update_stmt_if_modified (stmt);
2817         }
2818     }
2819   else
2820     update_stmt_if_modified (t);
2821 }
2822
2823 /* Insert statement (or statement list) T before the statement
2824    pointed-to by iterator I.  M specifies how to update iterator I
2825    after insertion (see enum bsi_iterator_update).  */
2826
2827 void
2828 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2829 {
2830   set_bb_for_stmt (t, i->bb);
2831   update_modified_stmts (t);
2832   tsi_link_before (&i->tsi, t, m);
2833 }
2834
2835
2836 /* Insert statement (or statement list) T after the statement
2837    pointed-to by iterator I.  M specifies how to update iterator I
2838    after insertion (see enum bsi_iterator_update).  */
2839
2840 void
2841 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2842 {
2843   set_bb_for_stmt (t, i->bb);
2844   update_modified_stmts (t);
2845   tsi_link_after (&i->tsi, t, m);
2846 }
2847
2848
2849 /* Remove the statement pointed to by iterator I.  The iterator is updated
2850    to the next statement.
2851
2852    When REMOVE_EH_INFO is true we remove the statement pointed to by
2853    iterator I from the EH tables.  Otherwise we do not modify the EH
2854    tables.
2855
2856    Generally, REMOVE_EH_INFO should be true when the statement is going to
2857    be removed from the IL and not reinserted elsewhere.  */
2858
2859 void
2860 bsi_remove (block_stmt_iterator *i, bool remove_eh_info)
2861 {
2862   tree t = bsi_stmt (*i);
2863   set_bb_for_stmt (t, NULL);
2864   delink_stmt_imm_use (t);
2865   tsi_delink (&i->tsi);
2866   mark_stmt_modified (t);
2867   if (remove_eh_info)
2868     remove_stmt_from_eh_region (t);
2869 }
2870
2871
2872 /* Move the statement at FROM so it comes right after the statement at TO.  */
2873
2874 void
2875 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2876 {
2877   tree stmt = bsi_stmt (*from);
2878   bsi_remove (from, false);
2879   bsi_insert_after (to, stmt, BSI_SAME_STMT);
2880 }
2881
2882
2883 /* Move the statement at FROM so it comes right before the statement at TO.  */
2884
2885 void
2886 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2887 {
2888   tree stmt = bsi_stmt (*from);
2889   bsi_remove (from, false);
2890   bsi_insert_before (to, stmt, BSI_SAME_STMT);
2891 }
2892
2893
2894 /* Move the statement at FROM to the end of basic block BB.  */
2895
2896 void
2897 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2898 {
2899   block_stmt_iterator last = bsi_last (bb);
2900
2901   /* Have to check bsi_end_p because it could be an empty block.  */
2902   if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2903     bsi_move_before (from, &last);
2904   else
2905     bsi_move_after (from, &last);
2906 }
2907
2908
2909 /* Replace the contents of the statement pointed to by iterator BSI
2910    with STMT.  If UPDATE_EH_INFO is true, the exception handling
2911    information of the original statement is moved to the new statement.  */
2912
2913
2914 void
2915 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool update_eh_info)
2916 {
2917   int eh_region;
2918   tree orig_stmt = bsi_stmt (*bsi);
2919
2920   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2921   set_bb_for_stmt (stmt, bsi->bb);
2922
2923   /* Preserve EH region information from the original statement, if
2924      requested by the caller.  */
2925   if (update_eh_info)
2926     {
2927       eh_region = lookup_stmt_eh_region (orig_stmt);
2928       if (eh_region >= 0)
2929         {
2930           remove_stmt_from_eh_region (orig_stmt);
2931           add_stmt_to_eh_region (stmt, eh_region);
2932         }
2933     }
2934
2935   delink_stmt_imm_use (orig_stmt);
2936   *bsi_stmt_ptr (*bsi) = stmt;
2937   mark_stmt_modified (stmt);
2938   update_modified_stmts (stmt);
2939 }
2940
2941
2942 /* Insert the statement pointed-to by BSI into edge E.  Every attempt
2943    is made to place the statement in an existing basic block, but
2944    sometimes that isn't possible.  When it isn't possible, the edge is
2945    split and the statement is added to the new block.
2946
2947    In all cases, the returned *BSI points to the correct location.  The
2948    return value is true if insertion should be done after the location,
2949    or false if it should be done before the location.  If new basic block
2950    has to be created, it is stored in *NEW_BB.  */
2951
2952 static bool
2953 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2954                            basic_block *new_bb)
2955 {
2956   basic_block dest, src;
2957   tree tmp;
2958
2959   dest = e->dest;
2960  restart:
2961
2962   /* If the destination has one predecessor which has no PHI nodes,
2963      insert there.  Except for the exit block.
2964
2965      The requirement for no PHI nodes could be relaxed.  Basically we
2966      would have to examine the PHIs to prove that none of them used
2967      the value set by the statement we want to insert on E.  That
2968      hardly seems worth the effort.  */
2969   if (single_pred_p (dest)
2970       && ! phi_nodes (dest)
2971       && dest != EXIT_BLOCK_PTR)
2972     {
2973       *bsi = bsi_start (dest);
2974       if (bsi_end_p (*bsi))
2975         return true;
2976
2977       /* Make sure we insert after any leading labels.  */
2978       tmp = bsi_stmt (*bsi);
2979       while (TREE_CODE (tmp) == LABEL_EXPR)
2980         {
2981           bsi_next (bsi);
2982           if (bsi_end_p (*bsi))
2983             break;
2984           tmp = bsi_stmt (*bsi);
2985         }
2986
2987       if (bsi_end_p (*bsi))
2988         {
2989           *bsi = bsi_last (dest);
2990           return true;
2991         }
2992       else
2993         return false;
2994     }
2995
2996   /* If the source has one successor, the edge is not abnormal and
2997      the last statement does not end a basic block, insert there.
2998      Except for the entry block.  */
2999   src = e->src;
3000   if ((e->flags & EDGE_ABNORMAL) == 0
3001       && single_succ_p (src)
3002       && src != ENTRY_BLOCK_PTR)
3003     {
3004       *bsi = bsi_last (src);
3005       if (bsi_end_p (*bsi))
3006         return true;
3007
3008       tmp = bsi_stmt (*bsi);
3009       if (!stmt_ends_bb_p (tmp))
3010         return true;
3011
3012       /* Insert code just before returning the value.  We may need to decompose
3013          the return in the case it contains non-trivial operand.  */
3014       if (TREE_CODE (tmp) == RETURN_EXPR)
3015         {
3016           tree op = TREE_OPERAND (tmp, 0);
3017           if (op && !is_gimple_val (op))
3018             {
3019               gcc_assert (TREE_CODE (op) == MODIFY_EXPR);
3020               bsi_insert_before (bsi, op, BSI_NEW_STMT);
3021               TREE_OPERAND (tmp, 0) = TREE_OPERAND (op, 0);
3022             }
3023           bsi_prev (bsi);
3024           return true;
3025         }
3026     }
3027
3028   /* Otherwise, create a new basic block, and split this edge.  */
3029   dest = split_edge (e);
3030   if (new_bb)
3031     *new_bb = dest;
3032   e = single_pred_edge (dest);
3033   goto restart;
3034 }
3035
3036
3037 /* This routine will commit all pending edge insertions, creating any new
3038    basic blocks which are necessary.  */
3039
3040 void
3041 bsi_commit_edge_inserts (void)
3042 {
3043   basic_block bb;
3044   edge e;
3045   edge_iterator ei;
3046
3047   bsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
3048
3049   FOR_EACH_BB (bb)
3050     FOR_EACH_EDGE (e, ei, bb->succs)
3051       bsi_commit_one_edge_insert (e, NULL);
3052 }
3053
3054
3055 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
3056    to this block, otherwise set it to NULL.  */
3057
3058 void
3059 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
3060 {
3061   if (new_bb)
3062     *new_bb = NULL;
3063   if (PENDING_STMT (e))
3064     {
3065       block_stmt_iterator bsi;
3066       tree stmt = PENDING_STMT (e);
3067
3068       PENDING_STMT (e) = NULL_TREE;
3069
3070       if (tree_find_edge_insert_loc (e, &bsi, new_bb))
3071         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3072       else
3073         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3074     }
3075 }
3076
3077
3078 /* Add STMT to the pending list of edge E.  No actual insertion is
3079    made until a call to bsi_commit_edge_inserts () is made.  */
3080
3081 void
3082 bsi_insert_on_edge (edge e, tree stmt)
3083 {
3084   append_to_statement_list (stmt, &PENDING_STMT (e));
3085 }
3086
3087 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If a new
3088    block has to be created, it is returned.  */
3089
3090 basic_block
3091 bsi_insert_on_edge_immediate (edge e, tree stmt)
3092 {
3093   block_stmt_iterator bsi;
3094   basic_block new_bb = NULL;
3095
3096   gcc_assert (!PENDING_STMT (e));
3097
3098   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3099     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3100   else
3101     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3102
3103   return new_bb;
3104 }
3105
3106 /*---------------------------------------------------------------------------
3107              Tree specific functions for CFG manipulation
3108 ---------------------------------------------------------------------------*/
3109
3110 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
3111
3112 static void
3113 reinstall_phi_args (edge new_edge, edge old_edge)
3114 {
3115   tree var, phi;
3116
3117   if (!PENDING_STMT (old_edge))
3118     return;
3119
3120   for (var = PENDING_STMT (old_edge), phi = phi_nodes (new_edge->dest);
3121        var && phi;
3122        var = TREE_CHAIN (var), phi = PHI_CHAIN (phi))
3123     {
3124       tree result = TREE_PURPOSE (var);
3125       tree arg = TREE_VALUE (var);
3126
3127       gcc_assert (result == PHI_RESULT (phi));
3128
3129       add_phi_arg (phi, arg, new_edge);
3130     }
3131
3132   PENDING_STMT (old_edge) = NULL;
3133 }
3134
3135 /* Returns the basic block after that the new basic block created
3136    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
3137    near its "logical" location.  This is of most help to humans looking
3138    at debugging dumps.  */
3139
3140 static basic_block
3141 split_edge_bb_loc (edge edge_in)
3142 {
3143   basic_block dest = edge_in->dest;
3144
3145   if (dest->prev_bb && find_edge (dest->prev_bb, dest))
3146     return edge_in->src;
3147   else
3148     return dest->prev_bb;
3149 }
3150
3151 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3152    Abort on abnormal edges.  */
3153
3154 static basic_block
3155 tree_split_edge (edge edge_in)
3156 {
3157   basic_block new_bb, after_bb, dest, src;
3158   edge new_edge, e;
3159
3160   /* Abnormal edges cannot be split.  */
3161   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3162
3163   src = edge_in->src;
3164   dest = edge_in->dest;
3165
3166   after_bb = split_edge_bb_loc (edge_in);
3167
3168   new_bb = create_empty_bb (after_bb);
3169   new_bb->frequency = EDGE_FREQUENCY (edge_in);
3170   new_bb->count = edge_in->count;
3171   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3172   new_edge->probability = REG_BR_PROB_BASE;
3173   new_edge->count = edge_in->count;
3174
3175   e = redirect_edge_and_branch (edge_in, new_bb);
3176   gcc_assert (e);
3177   reinstall_phi_args (new_edge, e);
3178
3179   return new_bb;
3180 }
3181
3182
3183 /* Return true when BB has label LABEL in it.  */
3184
3185 static bool
3186 has_label_p (basic_block bb, tree label)
3187 {
3188   block_stmt_iterator bsi;
3189
3190   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3191     {
3192       tree stmt = bsi_stmt (bsi);
3193
3194       if (TREE_CODE (stmt) != LABEL_EXPR)
3195         return false;
3196       if (LABEL_EXPR_LABEL (stmt) == label)
3197         return true;
3198     }
3199   return false;
3200 }
3201
3202
3203 /* Callback for walk_tree, check that all elements with address taken are
3204    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
3205    inside a PHI node.  */
3206
3207 static tree
3208 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3209 {
3210   tree t = *tp, x;
3211   bool in_phi = (data != NULL);
3212
3213   if (TYPE_P (t))
3214     *walk_subtrees = 0;
3215
3216   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
3217 #define CHECK_OP(N, MSG) \
3218   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
3219        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3220
3221   switch (TREE_CODE (t))
3222     {
3223     case SSA_NAME:
3224       if (SSA_NAME_IN_FREE_LIST (t))
3225         {
3226           error ("SSA name in freelist but still referenced");
3227           return *tp;
3228         }
3229       break;
3230
3231     case ASSERT_EXPR:
3232       x = fold (ASSERT_EXPR_COND (t));
3233       if (x == boolean_false_node)
3234         {
3235           error ("ASSERT_EXPR with an always-false condition");
3236           return *tp;
3237         }
3238       break;
3239
3240     case MODIFY_EXPR:
3241       x = TREE_OPERAND (t, 0);
3242       if (TREE_CODE (x) == BIT_FIELD_REF
3243           && is_gimple_reg (TREE_OPERAND (x, 0)))
3244         {
3245           error ("GIMPLE register modified with BIT_FIELD_REF");
3246           return t;
3247         }
3248       break;
3249
3250     case ADDR_EXPR:
3251       {
3252         bool old_invariant;
3253         bool old_constant;
3254         bool old_side_effects;
3255         bool new_invariant;
3256         bool new_constant;
3257         bool new_side_effects;
3258
3259         /* ??? tree-ssa-alias.c may have overlooked dead PHI nodes, missing
3260            dead PHIs that take the address of something.  But if the PHI
3261            result is dead, the fact that it takes the address of anything
3262            is irrelevant.  Because we can not tell from here if a PHI result
3263            is dead, we just skip this check for PHIs altogether.  This means
3264            we may be missing "valid" checks, but what can you do?
3265            This was PR19217.  */
3266         if (in_phi)
3267           break;
3268
3269         old_invariant = TREE_INVARIANT (t);
3270         old_constant = TREE_CONSTANT (t);
3271         old_side_effects = TREE_SIDE_EFFECTS (t);
3272
3273         recompute_tree_invariant_for_addr_expr (t);
3274         new_invariant = TREE_INVARIANT (t);
3275         new_side_effects = TREE_SIDE_EFFECTS (t);
3276         new_constant = TREE_CONSTANT (t);
3277
3278         if (old_invariant != new_invariant)
3279           {
3280             error ("invariant not recomputed when ADDR_EXPR changed");
3281             return t;
3282           }
3283
3284         if (old_constant != new_constant)
3285           {
3286             error ("constant not recomputed when ADDR_EXPR changed");
3287             return t;
3288           }
3289         if (old_side_effects != new_side_effects)
3290           {
3291             error ("side effects not recomputed when ADDR_EXPR changed");
3292             return t;
3293           }
3294
3295         /* Skip any references (they will be checked when we recurse down the
3296            tree) and ensure that any variable used as a prefix is marked
3297            addressable.  */
3298         for (x = TREE_OPERAND (t, 0);
3299              handled_component_p (x);
3300              x = TREE_OPERAND (x, 0))
3301           ;
3302
3303         if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3304           return NULL;
3305         if (!TREE_ADDRESSABLE (x))
3306           {
3307             error ("address taken, but ADDRESSABLE bit not set");
3308             return x;
3309           }
3310         break;
3311       }
3312
3313     case COND_EXPR:
3314       x = COND_EXPR_COND (t);
3315       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3316         {
3317           error ("non-boolean used in condition");
3318           return x;
3319         }
3320       if (!is_gimple_condexpr (x))
3321         {
3322           error ("invalid conditional operand");
3323           return x;
3324         }
3325       break;
3326
3327     case NOP_EXPR:
3328     case CONVERT_EXPR:
3329     case FIX_TRUNC_EXPR:
3330     case FIX_CEIL_EXPR:
3331     case FIX_FLOOR_EXPR:
3332     case FIX_ROUND_EXPR:
3333     case FLOAT_EXPR:
3334     case NEGATE_EXPR:
3335     case ABS_EXPR:
3336     case BIT_NOT_EXPR:
3337     case NON_LVALUE_EXPR:
3338     case TRUTH_NOT_EXPR:
3339       CHECK_OP (0, "invalid operand to unary operator");
3340       break;
3341
3342     case REALPART_EXPR:
3343     case IMAGPART_EXPR:
3344     case COMPONENT_REF:
3345     case ARRAY_REF:
3346     case ARRAY_RANGE_REF:
3347     case BIT_FIELD_REF:
3348     case VIEW_CONVERT_EXPR:
3349       /* We have a nest of references.  Verify that each of the operands
3350          that determine where to reference is either a constant or a variable,
3351          verify that the base is valid, and then show we've already checked
3352          the subtrees.  */
3353       while (handled_component_p (t))
3354         {
3355           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3356             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
3357           else if (TREE_CODE (t) == ARRAY_REF
3358                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3359             {
3360               CHECK_OP (1, "invalid array index");
3361               if (TREE_OPERAND (t, 2))
3362                 CHECK_OP (2, "invalid array lower bound");
3363               if (TREE_OPERAND (t, 3))
3364                 CHECK_OP (3, "invalid array stride");
3365             }
3366           else if (TREE_CODE (t) == BIT_FIELD_REF)
3367             {
3368               CHECK_OP (1, "invalid operand to BIT_FIELD_REF");
3369               CHECK_OP (2, "invalid operand to BIT_FIELD_REF");
3370             }
3371
3372           t = TREE_OPERAND (t, 0);
3373         }
3374
3375       if (!CONSTANT_CLASS_P (t) && !is_gimple_lvalue (t))
3376         {
3377           error ("invalid reference prefix");
3378           return t;
3379         }
3380       *walk_subtrees = 0;
3381       break;
3382
3383     case LT_EXPR:
3384     case LE_EXPR:
3385     case GT_EXPR:
3386     case GE_EXPR:
3387     case EQ_EXPR:
3388     case NE_EXPR:
3389     case UNORDERED_EXPR:
3390     case ORDERED_EXPR:
3391     case UNLT_EXPR:
3392     case UNLE_EXPR:
3393     case UNGT_EXPR:
3394     case UNGE_EXPR:
3395     case UNEQ_EXPR:
3396     case LTGT_EXPR:
3397     case PLUS_EXPR:
3398     case MINUS_EXPR:
3399     case MULT_EXPR:
3400     case TRUNC_DIV_EXPR:
3401     case CEIL_DIV_EXPR:
3402     case FLOOR_DIV_EXPR:
3403     case ROUND_DIV_EXPR:
3404     case TRUNC_MOD_EXPR:
3405     case CEIL_MOD_EXPR:
3406     case FLOOR_MOD_EXPR:
3407     case ROUND_MOD_EXPR:
3408     case RDIV_EXPR:
3409     case EXACT_DIV_EXPR:
3410     case MIN_EXPR:
3411     case MAX_EXPR:
3412     case LSHIFT_EXPR:
3413     case RSHIFT_EXPR:
3414     case LROTATE_EXPR:
3415     case RROTATE_EXPR:
3416     case BIT_IOR_EXPR:
3417     case BIT_XOR_EXPR:
3418     case BIT_AND_EXPR:
3419       CHECK_OP (0, "invalid operand to binary operator");
3420       CHECK_OP (1, "invalid operand to binary operator");
3421       break;
3422
3423     default:
3424       break;
3425     }
3426   return NULL;
3427
3428 #undef CHECK_OP
3429 }
3430
3431
3432 /* Verify STMT, return true if STMT is not in GIMPLE form.
3433    TODO: Implement type checking.  */
3434
3435 static bool
3436 verify_stmt (tree stmt, bool last_in_block)
3437 {
3438   tree addr;
3439
3440   if (OMP_DIRECTIVE_P (stmt))
3441     {
3442       /* OpenMP directives are validated by the FE and never operated
3443          on by the optimizers.  Furthermore, OMP_FOR may contain
3444          non-gimple expressions when the main index variable has had
3445          its address taken.  This does not affect the loop itself
3446          because the header of an OMP_FOR is merely used to determine
3447          how to setup the parallel iteration.  */
3448       return false;
3449     }
3450
3451   if (!is_gimple_stmt (stmt))
3452     {
3453       error ("is not a valid GIMPLE statement");
3454       goto fail;
3455     }
3456
3457   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3458   if (addr)
3459     {
3460       debug_generic_stmt (addr);
3461       return true;
3462     }
3463
3464   /* If the statement is marked as part of an EH region, then it is
3465      expected that the statement could throw.  Verify that when we
3466      have optimizations that simplify statements such that we prove
3467      that they cannot throw, that we update other data structures
3468      to match.  */
3469   if (lookup_stmt_eh_region (stmt) >= 0)
3470     {
3471       if (!tree_could_throw_p (stmt))
3472         {
3473           error ("statement marked for throw, but doesn%'t");
3474           goto fail;
3475         }
3476       if (!last_in_block && tree_can_throw_internal (stmt))
3477         {
3478           error ("statement marked for throw in middle of block");
3479           goto fail;
3480         }
3481     }
3482
3483   return false;
3484
3485  fail:
3486   debug_generic_stmt (stmt);
3487   return true;
3488 }
3489
3490
3491 /* Return true when the T can be shared.  */
3492
3493 static bool
3494 tree_node_can_be_shared (tree t)
3495 {
3496   if (IS_TYPE_OR_DECL_P (t)
3497       || is_gimple_min_invariant (t)
3498       || TREE_CODE (t) == SSA_NAME
3499       || t == error_mark_node
3500       || TREE_CODE (t) == IDENTIFIER_NODE)
3501     return true;
3502
3503   if (TREE_CODE (t) == CASE_LABEL_EXPR)
3504     return true;
3505
3506   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3507            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
3508          || TREE_CODE (t) == COMPONENT_REF
3509          || TREE_CODE (t) == REALPART_EXPR
3510          || TREE_CODE (t) == IMAGPART_EXPR)
3511     t = TREE_OPERAND (t, 0);
3512
3513   if (DECL_P (t))
3514     return true;
3515
3516   return false;
3517 }
3518
3519
3520 /* Called via walk_trees.  Verify tree sharing.  */
3521
3522 static tree
3523 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3524 {
3525   htab_t htab = (htab_t) data;
3526   void **slot;
3527
3528   if (tree_node_can_be_shared (*tp))
3529     {
3530       *walk_subtrees = false;
3531       return NULL;
3532     }
3533
3534   slot = htab_find_slot (htab, *tp, INSERT);
3535   if (*slot)
3536     return (tree) *slot;
3537   *slot = *tp;
3538
3539   return NULL;
3540 }
3541
3542
3543 /* Verify the GIMPLE statement chain.  */
3544
3545 void
3546 verify_stmts (void)
3547 {
3548   basic_block bb;
3549   block_stmt_iterator bsi;
3550   bool err = false;
3551   htab_t htab;
3552   tree addr;
3553
3554   timevar_push (TV_TREE_STMT_VERIFY);
3555   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3556
3557   FOR_EACH_BB (bb)
3558     {
3559       tree phi;
3560       int i;
3561
3562       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3563         {
3564           int phi_num_args = PHI_NUM_ARGS (phi);
3565
3566           if (bb_for_stmt (phi) != bb)
3567             {
3568               error ("bb_for_stmt (phi) is set to a wrong basic block");
3569               err |= true;
3570             }
3571
3572           for (i = 0; i < phi_num_args; i++)
3573             {
3574               tree t = PHI_ARG_DEF (phi, i);
3575               tree addr;
3576
3577               /* Addressable variables do have SSA_NAMEs but they
3578                  are not considered gimple values.  */
3579               if (TREE_CODE (t) != SSA_NAME
3580                   && TREE_CODE (t) != FUNCTION_DECL
3581                   && !is_gimple_val (t))
3582                 {
3583                   error ("PHI def is not a GIMPLE value");
3584                   debug_generic_stmt (phi);
3585                   debug_generic_stmt (t);
3586                   err |= true;
3587                 }
3588
3589               addr = walk_tree (&t, verify_expr, (void *) 1, NULL);
3590               if (addr)
3591                 {
3592                   debug_generic_stmt (addr);
3593                   err |= true;
3594                 }
3595
3596               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3597               if (addr)
3598                 {
3599                   error ("incorrect sharing of tree nodes");
3600                   debug_generic_stmt (phi);
3601                   debug_generic_stmt (addr);
3602                   err |= true;
3603                 }
3604             }
3605         }
3606
3607       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3608         {
3609           tree stmt = bsi_stmt (bsi);
3610
3611           if (bb_for_stmt (stmt) != bb)
3612             {
3613               error ("bb_for_stmt (stmt) is set to a wrong basic block");
3614               err |= true;
3615             }
3616
3617           bsi_next (&bsi);
3618           err |= verify_stmt (stmt, bsi_end_p (bsi));
3619           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3620           if (addr)
3621             {
3622               error ("incorrect sharing of tree nodes");
3623               debug_generic_stmt (stmt);
3624               debug_generic_stmt (addr);
3625               err |= true;
3626             }
3627         }
3628     }
3629
3630   if (err)
3631     internal_error ("verify_stmts failed");
3632
3633   htab_delete (htab);
3634   timevar_pop (TV_TREE_STMT_VERIFY);
3635 }
3636
3637
3638 /* Verifies that the flow information is OK.  */
3639
3640 static int
3641 tree_verify_flow_info (void)
3642 {
3643   int err = 0;
3644   basic_block bb;
3645   block_stmt_iterator bsi;
3646   tree stmt;
3647   edge e;
3648   edge_iterator ei;
3649
3650   if (ENTRY_BLOCK_PTR->stmt_list)
3651     {
3652       error ("ENTRY_BLOCK has a statement list associated with it");
3653       err = 1;
3654     }
3655
3656   if (EXIT_BLOCK_PTR->stmt_list)
3657     {
3658       error ("EXIT_BLOCK has a statement list associated with it");
3659       err = 1;
3660     }
3661
3662   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
3663     if (e->flags & EDGE_FALLTHRU)
3664       {
3665         error ("fallthru to exit from bb %d", e->src->index);
3666         err = 1;
3667       }
3668
3669   FOR_EACH_BB (bb)
3670     {
3671       bool found_ctrl_stmt = false;
3672
3673       stmt = NULL_TREE;
3674
3675       /* Skip labels on the start of basic block.  */
3676       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3677         {
3678           tree prev_stmt = stmt;
3679
3680           stmt = bsi_stmt (bsi);
3681
3682           if (TREE_CODE (stmt) != LABEL_EXPR)
3683             break;
3684
3685           if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3686             {
3687               error ("nonlocal label ");
3688               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3689               fprintf (stderr, " is not first in a sequence of labels in bb %d",
3690                        bb->index);
3691               err = 1;
3692             }
3693
3694           if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
3695             {
3696               error ("label ");
3697               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3698               fprintf (stderr, " to block does not match in bb %d",
3699                        bb->index);
3700               err = 1;
3701             }
3702
3703           if (decl_function_context (LABEL_EXPR_LABEL (stmt))
3704               != current_function_decl)
3705             {
3706               error ("label ");
3707               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3708               fprintf (stderr, " has incorrect context in bb %d",
3709                        bb->index);
3710               err = 1;
3711             }
3712         }
3713
3714       /* Verify that body of basic block BB is free of control flow.  */
3715       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3716         {
3717           tree stmt = bsi_stmt (bsi);
3718
3719           if (found_ctrl_stmt)
3720             {
3721               error ("control flow in the middle of basic block %d",
3722                      bb->index);
3723               err = 1;
3724             }
3725
3726           if (stmt_ends_bb_p (stmt))
3727             found_ctrl_stmt = true;
3728
3729           if (TREE_CODE (stmt) == LABEL_EXPR)
3730             {
3731               error ("label ");
3732               print_generic_expr (stderr, LABEL_EXPR_LABEL (stmt), 0);
3733               fprintf (stderr, " in the middle of basic block %d", bb->index);
3734               err = 1;
3735             }
3736         }
3737
3738       bsi = bsi_last (bb);
3739       if (bsi_end_p (bsi))
3740         continue;
3741
3742       stmt = bsi_stmt (bsi);
3743
3744       err |= verify_eh_edges (stmt);
3745
3746       if (is_ctrl_stmt (stmt))
3747         {
3748           FOR_EACH_EDGE (e, ei, bb->succs)
3749             if (e->flags & EDGE_FALLTHRU)
3750               {
3751                 error ("fallthru edge after a control statement in bb %d",
3752                        bb->index);
3753                 err = 1;
3754               }
3755         }
3756
3757       switch (TREE_CODE (stmt))
3758         {
3759         case COND_EXPR:
3760           {
3761             edge true_edge;
3762             edge false_edge;
3763             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3764                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3765               {
3766                 error ("structured COND_EXPR at the end of bb %d", bb->index);
3767                 err = 1;
3768               }
3769
3770             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3771
3772             if (!true_edge || !false_edge
3773                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3774                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3775                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3776                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3777                 || EDGE_COUNT (bb->succs) >= 3)
3778               {
3779                 error ("wrong outgoing edge flags at end of bb %d",
3780                        bb->index);
3781                 err = 1;
3782               }
3783
3784             if (!has_label_p (true_edge->dest,
3785                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3786               {
3787                 error ("%<then%> label does not match edge at end of bb %d",
3788                        bb->index);
3789                 err = 1;
3790               }
3791
3792             if (!has_label_p (false_edge->dest,
3793                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3794               {
3795                 error ("%<else%> label does not match edge at end of bb %d",
3796                        bb->index);
3797                 err = 1;
3798               }
3799           }
3800           break;
3801
3802         case GOTO_EXPR:
3803           if (simple_goto_p (stmt))
3804             {
3805               error ("explicit goto at end of bb %d", bb->index);
3806               err = 1;
3807             }
3808           else
3809             {
3810               /* FIXME.  We should double check that the labels in the
3811                  destination blocks have their address taken.  */
3812               FOR_EACH_EDGE (e, ei, bb->succs)
3813                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3814                                  | EDGE_FALSE_VALUE))
3815                     || !(e->flags & EDGE_ABNORMAL))
3816                   {
3817                     error ("wrong outgoing edge flags at end of bb %d",
3818                            bb->index);
3819                     err = 1;
3820                   }
3821             }
3822           break;
3823
3824         case RETURN_EXPR:
3825           if (!single_succ_p (bb)
3826               || (single_succ_edge (bb)->flags
3827                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
3828                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3829             {
3830               error ("wrong outgoing edge flags at end of bb %d", bb->index);
3831               err = 1;
3832             }
3833           if (single_succ (bb) != EXIT_BLOCK_PTR)
3834             {
3835               error ("return edge does not point to exit in bb %d",
3836                      bb->index);
3837               err = 1;
3838             }
3839           break;
3840
3841         case SWITCH_EXPR:
3842           {
3843             tree prev;
3844             edge e;
3845             size_t i, n;
3846             tree vec;
3847
3848             vec = SWITCH_LABELS (stmt);
3849             n = TREE_VEC_LENGTH (vec);
3850
3851             /* Mark all the destination basic blocks.  */
3852             for (i = 0; i < n; ++i)
3853               {
3854                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3855                 basic_block label_bb = label_to_block (lab);
3856
3857                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
3858                 label_bb->aux = (void *)1;
3859               }
3860
3861             /* Verify that the case labels are sorted.  */
3862             prev = TREE_VEC_ELT (vec, 0);
3863             for (i = 1; i < n - 1; ++i)
3864               {
3865                 tree c = TREE_VEC_ELT (vec, i);
3866                 if (! CASE_LOW (c))
3867                   {
3868                     error ("found default case not at end of case vector");
3869                     err = 1;
3870                     continue;
3871                   }
3872                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
3873                   {
3874                     error ("case labels not sorted: ");
3875                     print_generic_expr (stderr, prev, 0);
3876                     fprintf (stderr," is greater than ");
3877                     print_generic_expr (stderr, c, 0);
3878                     fprintf (stderr," but comes before it.\n");
3879                     err = 1;
3880                   }
3881                 prev = c;
3882               }
3883             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
3884               {
3885                 error ("no default case found at end of case vector");
3886                 err = 1;
3887               }
3888
3889             FOR_EACH_EDGE (e, ei, bb->succs)
3890               {
3891                 if (!e->dest->aux)
3892                   {
3893                     error ("extra outgoing edge %d->%d",
3894                            bb->index, e->dest->index);
3895                     err = 1;
3896                   }
3897                 e->dest->aux = (void *)2;
3898                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3899                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3900                   {
3901                     error ("wrong outgoing edge flags at end of bb %d",
3902                            bb->index);
3903                     err = 1;
3904                   }
3905               }
3906
3907             /* Check that we have all of them.  */
3908             for (i = 0; i < n; ++i)
3909               {
3910                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3911                 basic_block label_bb = label_to_block (lab);
3912
3913                 if (label_bb->aux != (void *)2)
3914                   {
3915                     error ("missing edge %i->%i",
3916                            bb->index, label_bb->index);
3917                     err = 1;
3918                   }
3919               }
3920
3921             FOR_EACH_EDGE (e, ei, bb->succs)
3922               e->dest->aux = (void *)0;
3923           }
3924
3925         default: ;
3926         }
3927     }
3928
3929   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
3930     verify_dominators (CDI_DOMINATORS);
3931
3932   return err;
3933 }
3934
3935
3936 /* Updates phi nodes after creating a forwarder block joined
3937    by edge FALLTHRU.  */
3938
3939 static void
3940 tree_make_forwarder_block (edge fallthru)
3941 {
3942   edge e;
3943   edge_iterator ei;
3944   basic_block dummy, bb;
3945   tree phi, new_phi, var;
3946
3947   dummy = fallthru->src;
3948   bb = fallthru->dest;
3949
3950   if (single_pred_p (bb))
3951     return;
3952
3953   /* If we redirected a branch we must create new phi nodes at the
3954      start of BB.  */
3955   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
3956     {
3957       var = PHI_RESULT (phi);
3958       new_phi = create_phi_node (var, bb);
3959       SSA_NAME_DEF_STMT (var) = new_phi;
3960       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
3961       add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
3962     }
3963
3964   /* Ensure that the PHI node chain is in the same order.  */
3965   set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
3966
3967   /* Add the arguments we have stored on edges.  */
3968   FOR_EACH_EDGE (e, ei, bb->preds)
3969     {
3970       if (e == fallthru)
3971         continue;
3972
3973       flush_pending_stmts (e);
3974     }
3975 }
3976
3977
3978 /* Return a non-special label in the head of basic block BLOCK.
3979    Create one if it doesn't exist.  */
3980
3981 tree
3982 tree_block_label (basic_block bb)
3983 {
3984   block_stmt_iterator i, s = bsi_start (bb);
3985   bool first = true;
3986   tree label, stmt;
3987
3988   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
3989     {
3990       stmt = bsi_stmt (i);
3991       if (TREE_CODE (stmt) != LABEL_EXPR)
3992         break;
3993       label = LABEL_EXPR_LABEL (stmt);
3994       if (!DECL_NONLOCAL (label))
3995         {
3996           if (!first)
3997             bsi_move_before (&i, &s);
3998           return label;
3999         }
4000     }
4001
4002   label = create_artificial_label ();
4003   stmt = build1 (LABEL_EXPR, void_type_node, label);
4004   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
4005   return label;
4006 }
4007
4008
4009 /* Attempt to perform edge redirection by replacing a possibly complex
4010    jump instruction by a goto or by removing the jump completely.
4011    This can apply only if all edges now point to the same block.  The
4012    parameters and return values are equivalent to
4013    redirect_edge_and_branch.  */
4014
4015 static edge
4016 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4017 {
4018   basic_block src = e->src;
4019   block_stmt_iterator b;
4020   tree stmt;
4021
4022   /* We can replace or remove a complex jump only when we have exactly
4023      two edges.  */
4024   if (EDGE_COUNT (src->succs) != 2
4025       /* Verify that all targets will be TARGET.  Specifically, the
4026          edge that is not E must also go to TARGET.  */
4027       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4028     return NULL;
4029
4030   b = bsi_last (src);
4031   if (bsi_end_p (b))
4032     return NULL;
4033   stmt = bsi_stmt (b);
4034
4035   if (TREE_CODE (stmt) == COND_EXPR
4036       || TREE_CODE (stmt) == SWITCH_EXPR)
4037     {
4038       bsi_remove (&b, true);
4039       e = ssa_redirect_edge (e, target);
4040       e->flags = EDGE_FALLTHRU;
4041       return e;
4042     }
4043
4044   return NULL;
4045 }
4046
4047
4048 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4049    edge representing the redirected branch.  */
4050
4051 static edge
4052 tree_redirect_edge_and_branch (edge e, basic_block dest)
4053 {
4054   basic_block bb = e->src;
4055   block_stmt_iterator bsi;
4056   edge ret;
4057   tree label, stmt;
4058
4059   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4060     return NULL;
4061
4062   if (e->src != ENTRY_BLOCK_PTR
4063       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4064     return ret;
4065
4066   if (e->dest == dest)
4067     return NULL;
4068
4069   label = tree_block_label (dest);
4070
4071   bsi = bsi_last (bb);
4072   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4073
4074   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4075     {
4076     case COND_EXPR:
4077       stmt = (e->flags & EDGE_TRUE_VALUE
4078               ? COND_EXPR_THEN (stmt)
4079               : COND_EXPR_ELSE (stmt));
4080       GOTO_DESTINATION (stmt) = label;
4081       break;
4082
4083     case GOTO_EXPR:
4084       /* No non-abnormal edges should lead from a non-simple goto, and
4085          simple ones should be represented implicitly.  */
4086       gcc_unreachable ();
4087
4088     case SWITCH_EXPR:
4089       {
4090         tree cases = get_cases_for_edge (e, stmt);
4091
4092         /* If we have a list of cases associated with E, then use it
4093            as it's a lot faster than walking the entire case vector.  */
4094         if (cases)
4095           {
4096             edge e2 = find_edge (e->src, dest);
4097             tree last, first;
4098
4099             first = cases;
4100             while (cases)
4101               {
4102                 last = cases;
4103                 CASE_LABEL (cases) = label;
4104                 cases = TREE_CHAIN (cases);
4105               }
4106
4107             /* If there was already an edge in the CFG, then we need
4108                to move all the cases associated with E to E2.  */
4109             if (e2)
4110               {
4111                 tree cases2 = get_cases_for_edge (e2, stmt);
4112
4113                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
4114                 TREE_CHAIN (cases2) = first;
4115               }
4116           }
4117         else
4118           {
4119             tree vec = SWITCH_LABELS (stmt);
4120             size_t i, n = TREE_VEC_LENGTH (vec);
4121
4122             for (i = 0; i < n; i++)
4123               {
4124                 tree elt = TREE_VEC_ELT (vec, i);
4125
4126                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4127                   CASE_LABEL (elt) = label;
4128               }
4129           }
4130
4131         break;
4132       }
4133
4134     case RETURN_EXPR:
4135       bsi_remove (&bsi, true);
4136       e->flags |= EDGE_FALLTHRU;
4137       break;
4138
4139     default:
4140       /* Otherwise it must be a fallthru edge, and we don't need to
4141          do anything besides redirecting it.  */
4142       gcc_assert (e->flags & EDGE_FALLTHRU);
4143       break;
4144     }
4145
4146   /* Update/insert PHI nodes as necessary.  */
4147
4148   /* Now update the edges in the CFG.  */
4149   e = ssa_redirect_edge (e, dest);
4150
4151   return e;
4152 }
4153
4154
4155 /* Simple wrapper, as we can always redirect fallthru edges.  */
4156
4157 static basic_block
4158 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4159 {
4160   e = tree_redirect_edge_and_branch (e, dest);
4161   gcc_assert (e);
4162
4163   return NULL;
4164 }
4165
4166
4167 /* Splits basic block BB after statement STMT (but at least after the
4168    labels).  If STMT is NULL, BB is split just after the labels.  */
4169
4170 static basic_block
4171 tree_split_block (basic_block bb, void *stmt)
4172 {
4173   block_stmt_iterator bsi, bsi_tgt;
4174   tree act;
4175   basic_block new_bb;
4176   edge e;
4177   edge_iterator ei;
4178
4179   new_bb = create_empty_bb (bb);
4180
4181   /* Redirect the outgoing edges.  */
4182   new_bb->succs = bb->succs;
4183   bb->succs = NULL;
4184   FOR_EACH_EDGE (e, ei, new_bb->succs)
4185     e->src = new_bb;
4186
4187   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4188     stmt = NULL;
4189
4190   /* Move everything from BSI to the new basic block.  */
4191   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4192     {
4193       act = bsi_stmt (bsi);
4194       if (TREE_CODE (act) == LABEL_EXPR)
4195         continue;
4196
4197       if (!stmt)
4198         break;
4199
4200       if (stmt == act)
4201         {
4202           bsi_next (&bsi);
4203           break;
4204         }
4205     }
4206
4207   bsi_tgt = bsi_start (new_bb);
4208   while (!bsi_end_p (bsi))
4209     {
4210       act = bsi_stmt (bsi);
4211       bsi_remove (&bsi, false);
4212       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
4213     }
4214
4215   return new_bb;
4216 }
4217
4218
4219 /* Moves basic block BB after block AFTER.  */
4220
4221 static bool
4222 tree_move_block_after (basic_block bb, basic_block after)
4223 {
4224   if (bb->prev_bb == after)
4225     return true;
4226
4227   unlink_block (bb);
4228   link_block (bb, after);
4229
4230   return true;
4231 }
4232
4233
4234 /* Return true if basic_block can be duplicated.  */
4235
4236 static bool
4237 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4238 {
4239   return true;
4240 }
4241
4242
4243 /* Create a duplicate of the basic block BB.  NOTE: This does not
4244    preserve SSA form.  */
4245
4246 static basic_block
4247 tree_duplicate_bb (basic_block bb)
4248 {
4249   basic_block new_bb;
4250   block_stmt_iterator bsi, bsi_tgt;
4251   tree phi;
4252
4253   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4254
4255   /* Copy the PHI nodes.  We ignore PHI node arguments here because
4256      the incoming edges have not been setup yet.  */
4257   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4258     {
4259       tree copy = create_phi_node (PHI_RESULT (phi), new_bb);
4260       create_new_def_for (PHI_RESULT (copy), copy, PHI_RESULT_PTR (copy));
4261     }
4262
4263   /* Keep the chain of PHI nodes in the same order so that they can be
4264      updated by ssa_redirect_edge.  */
4265   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
4266
4267   bsi_tgt = bsi_start (new_bb);
4268   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4269     {
4270       def_operand_p def_p;
4271       ssa_op_iter op_iter;
4272       tree stmt, copy;
4273       int region;
4274
4275       stmt = bsi_stmt (bsi);
4276       if (TREE_CODE (stmt) == LABEL_EXPR)
4277         continue;
4278
4279       /* Create a new copy of STMT and duplicate STMT's virtual
4280          operands.  */
4281       copy = unshare_expr (stmt);
4282       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4283       copy_virtual_operands (copy, stmt);
4284       region = lookup_stmt_eh_region (stmt);
4285       if (region >= 0)
4286         add_stmt_to_eh_region (copy, region);
4287
4288       /* Create new names for all the definitions created by COPY and
4289          add replacement mappings for each new name.  */
4290       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
4291         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
4292     }
4293
4294   return new_bb;
4295 }
4296
4297
4298 /* Basic block BB_COPY was created by code duplication.  Add phi node
4299    arguments for edges going out of BB_COPY.  The blocks that were
4300    duplicated have BB_DUPLICATED set.  */
4301
4302 void
4303 add_phi_args_after_copy_bb (basic_block bb_copy)
4304 {
4305   basic_block bb, dest;
4306   edge e, e_copy;
4307   edge_iterator ei;
4308   tree phi, phi_copy, phi_next, def;
4309
4310   bb = get_bb_original (bb_copy);
4311
4312   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
4313     {
4314       if (!phi_nodes (e_copy->dest))
4315         continue;
4316
4317       if (e_copy->dest->flags & BB_DUPLICATED)
4318         dest = get_bb_original (e_copy->dest);
4319       else
4320         dest = e_copy->dest;
4321
4322       e = find_edge (bb, dest);
4323       if (!e)
4324         {
4325           /* During loop unrolling the target of the latch edge is copied.
4326              In this case we are not looking for edge to dest, but to
4327              duplicated block whose original was dest.  */
4328           FOR_EACH_EDGE (e, ei, bb->succs)
4329             if ((e->dest->flags & BB_DUPLICATED)
4330                 && get_bb_original (e->dest) == dest)
4331               break;
4332
4333           gcc_assert (e != NULL);
4334         }
4335
4336       for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
4337            phi;
4338            phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
4339         {
4340           phi_next = PHI_CHAIN (phi);
4341           def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4342           add_phi_arg (phi_copy, def, e_copy);
4343         }
4344     }
4345 }
4346
4347 /* Blocks in REGION_COPY array of length N_REGION were created by
4348    duplication of basic blocks.  Add phi node arguments for edges
4349    going from these blocks.  */
4350
4351 void
4352 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
4353 {
4354   unsigned i;
4355
4356   for (i = 0; i < n_region; i++)
4357     region_copy[i]->flags |= BB_DUPLICATED;
4358
4359   for (i = 0; i < n_region; i++)
4360     add_phi_args_after_copy_bb (region_copy[i]);
4361
4362   for (i = 0; i < n_region; i++)
4363     region_copy[i]->flags &= ~BB_DUPLICATED;
4364 }
4365
4366 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
4367    important exit edge EXIT.  By important we mean that no SSA name defined
4368    inside region is live over the other exit edges of the region.  All entry
4369    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
4370    to the duplicate of the region.  SSA form, dominance and loop information
4371    is updated.  The new basic blocks are stored to REGION_COPY in the same
4372    order as they had in REGION, provided that REGION_COPY is not NULL.
4373    The function returns false if it is unable to copy the region,
4374    true otherwise.  */
4375
4376 bool
4377 tree_duplicate_sese_region (edge entry, edge exit,
4378                             basic_block *region, unsigned n_region,
4379                             basic_block *region_copy)
4380 {
4381   unsigned i, n_doms;
4382   bool free_region_copy = false, copying_header = false;
4383   struct loop *loop = entry->dest->loop_father;
4384   edge exit_copy;
4385   basic_block *doms;
4386   edge redirected;
4387   int total_freq = 0, entry_freq = 0;
4388   gcov_type total_count = 0, entry_count = 0;
4389
4390   if (!can_copy_bbs_p (region, n_region))
4391     return false;
4392
4393   /* Some sanity checking.  Note that we do not check for all possible
4394      missuses of the functions.  I.e. if you ask to copy something weird,
4395      it will work, but the state of structures probably will not be
4396      correct.  */
4397   for (i = 0; i < n_region; i++)
4398     {
4399       /* We do not handle subloops, i.e. all the blocks must belong to the
4400          same loop.  */
4401       if (region[i]->loop_father != loop)
4402         return false;
4403
4404       if (region[i] != entry->dest
4405           && region[i] == loop->header)
4406         return false;
4407     }
4408
4409   loop->copy = loop;
4410
4411   /* In case the function is used for loop header copying (which is the primary
4412      use), ensure that EXIT and its copy will be new latch and entry edges.  */
4413   if (loop->header == entry->dest)
4414     {
4415       copying_header = true;
4416       loop->copy = loop->outer;
4417
4418       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
4419         return false;
4420
4421       for (i = 0; i < n_region; i++)
4422         if (region[i] != exit->src
4423             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
4424           return false;
4425     }
4426
4427   if (!region_copy)
4428     {
4429       region_copy = XNEWVEC (basic_block, n_region);
4430       free_region_copy = true;
4431     }
4432
4433   gcc_assert (!need_ssa_update_p ());
4434
4435   /* Record blocks outside the region that are dominated by something
4436      inside.  */
4437   doms = XNEWVEC (basic_block, n_basic_blocks);
4438   initialize_original_copy_tables ();
4439
4440   n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
4441
4442   if (entry->dest->count)
4443     {
4444       total_count = entry->dest->count;
4445       entry_count = entry->count;
4446       /* Fix up corner cases, to avoid division by zero or creation of negative
4447          frequencies.  */
4448       if (entry_count > total_count)
4449         entry_count = total_count;
4450     }
4451   else
4452     {
4453       total_freq = entry->dest->frequency;
4454       entry_freq = EDGE_FREQUENCY (entry);
4455       /* Fix up corner cases, to avoid division by zero or creation of negative
4456          frequencies.  */
4457       if (total_freq == 0)
4458         total_freq = 1;
4459       else if (entry_freq > total_freq)
4460         entry_freq = total_freq;
4461     }
4462
4463   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
4464             split_edge_bb_loc (entry));
4465   if (total_count)
4466     {
4467       scale_bbs_frequencies_gcov_type (region, n_region,
4468                                        total_count - entry_count,
4469                                        total_count);
4470       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
4471                                        total_count);
4472     }
4473   else
4474     {
4475       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
4476                                  total_freq);
4477       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
4478     }
4479
4480   if (copying_header)
4481     {
4482       loop->header = exit->dest;
4483       loop->latch = exit->src;
4484     }
4485
4486   /* Redirect the entry and add the phi node arguments.  */
4487   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
4488   gcc_assert (redirected != NULL);
4489   flush_pending_stmts (entry);
4490
4491   /* Concerning updating of dominators:  We must recount dominators
4492      for entry block and its copy.  Anything that is outside of the
4493      region, but was dominated by something inside needs recounting as
4494      well.  */
4495   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
4496   doms[n_doms++] = get_bb_original (entry->dest);
4497   iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
4498   free (doms);
4499
4500   /* Add the other PHI node arguments.  */
4501   add_phi_args_after_copy (region_copy, n_region);
4502
4503   /* Update the SSA web.  */
4504   update_ssa (TODO_update_ssa);
4505
4506   if (free_region_copy)
4507     free (region_copy);
4508
4509   free_original_copy_tables ();
4510   return true;
4511 }
4512
4513 /*
4514 DEF_VEC_P(basic_block);
4515 DEF_VEC_ALLOC_P(basic_block,heap);
4516 */
4517
4518 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
4519    adding blocks when the dominator traversal reaches EXIT.  This
4520    function silently assumes that ENTRY strictly dominates EXIT.  */
4521
4522 static void
4523 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
4524                               VEC(basic_block,heap) **bbs_p)
4525 {
4526   basic_block son;
4527
4528   for (son = first_dom_son (CDI_DOMINATORS, entry);
4529        son;
4530        son = next_dom_son (CDI_DOMINATORS, son))
4531     {
4532       VEC_safe_push (basic_block, heap, *bbs_p, son);
4533       if (son != exit)
4534         gather_blocks_in_sese_region (son, exit, bbs_p);
4535     }
4536 }
4537
4538
4539 struct move_stmt_d
4540 {
4541   tree block;
4542   tree from_context;
4543   tree to_context;
4544   bitmap vars_to_remove;
4545   htab_t new_label_map;
4546   bool remap_decls_p;
4547 };
4548
4549 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
4550    contained in *TP and change the DECL_CONTEXT of every local
4551    variable referenced in *TP.  */
4552
4553 static tree
4554 move_stmt_r (tree *tp, int *walk_subtrees, void *data)
4555 {
4556   struct move_stmt_d *p = (struct move_stmt_d *) data;
4557   tree t = *tp;
4558
4559   if (p->block && IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (TREE_CODE (t))))
4560     TREE_BLOCK (t) = p->block;
4561
4562   if (OMP_DIRECTIVE_P (t)
4563       && TREE_CODE (t) != OMP_RETURN
4564       && TREE_CODE (t) != OMP_CONTINUE)
4565     {
4566       /* Do not remap variables inside OMP directives.  Variables
4567          referenced in clauses and directive header belong to the
4568          parent function and should not be moved into the child
4569          function.  */
4570       bool save_remap_decls_p = p->remap_decls_p;
4571       p->remap_decls_p = false;
4572       *walk_subtrees = 0;
4573
4574       walk_tree (&OMP_BODY (t), move_stmt_r, p, NULL);
4575
4576       p->remap_decls_p = save_remap_decls_p;
4577     }
4578   else if (DECL_P (t) && DECL_CONTEXT (t) == p->from_context)
4579     {
4580       if (TREE_CODE (t) == LABEL_DECL)
4581         {
4582           if (p->new_label_map)
4583             {
4584               struct tree_map in, *out;
4585               in.from = t;
4586               out = htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
4587               if (out)
4588                 *tp = t = out->to;
4589             }
4590
4591           DECL_CONTEXT (t) = p->to_context;
4592         }
4593       else if (p->remap_decls_p)
4594         {
4595           DECL_CONTEXT (t) = p->to_context;
4596
4597           if (TREE_CODE (t) == VAR_DECL)
4598             {
4599               struct function *f = DECL_STRUCT_FUNCTION (p->to_context);
4600               f->unexpanded_var_list
4601                 = tree_cons (0, t, f->unexpanded_var_list);
4602
4603               /* Mark T to be removed from the original function,
4604                  otherwise it will be given a DECL_RTL when the
4605                  original function is expanded.  */
4606               bitmap_set_bit (p->vars_to_remove, DECL_UID (t));
4607             }
4608         }
4609     }
4610   else if (TYPE_P (t))
4611     *walk_subtrees = 0;
4612
4613   return NULL_TREE;
4614 }
4615
4616
4617 /* Move basic block BB from function CFUN to function DEST_FN.  The
4618    block is moved out of the original linked list and placed after
4619    block AFTER in the new list.  Also, the block is removed from the
4620    original array of blocks and placed in DEST_FN's array of blocks.
4621    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
4622    updated to reflect the moved edges.
4623
4624    On exit, local variables that need to be removed from
4625    CFUN->UNEXPANDED_VAR_LIST will have been added to VARS_TO_REMOVE.  */
4626
4627 static void
4628 move_block_to_fn (struct function *dest_cfun, basic_block bb,
4629                   basic_block after, bool update_edge_count_p,
4630                   bitmap vars_to_remove, htab_t new_label_map, int eh_offset)
4631 {
4632   struct control_flow_graph *cfg;
4633   edge_iterator ei;
4634   edge e;
4635   block_stmt_iterator si;
4636   struct move_stmt_d d;
4637   unsigned old_len, new_len;
4638   basic_block *addr;
4639
4640   /* Link BB to the new linked list.  */
4641   move_block_after (bb, after);
4642
4643   /* Update the edge count in the corresponding flowgraphs.  */
4644   if (update_edge_count_p)
4645     FOR_EACH_EDGE (e, ei, bb->succs)
4646       {
4647         cfun->cfg->x_n_edges--;
4648         dest_cfun->cfg->x_n_edges++;
4649       }
4650
4651   /* Remove BB from the original basic block array.  */
4652   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
4653   cfun->cfg->x_n_basic_blocks--;
4654
4655   /* Grow DEST_CFUN's basic block array if needed.  */
4656   cfg = dest_cfun->cfg;
4657   cfg->x_n_basic_blocks++;
4658   if (bb->index > cfg->x_last_basic_block)
4659     cfg->x_last_basic_block = bb->index;
4660
4661   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
4662   if ((unsigned) cfg->x_last_basic_block >= old_len)
4663     {
4664       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
4665       VEC_safe_grow (basic_block, gc, cfg->x_basic_block_info, new_len);
4666       addr = VEC_address (basic_block, cfg->x_basic_block_info);
4667       memset (&addr[old_len], 0, sizeof (basic_block) * (new_len - old_len));
4668     }
4669
4670   VEC_replace (basic_block, cfg->x_basic_block_info,
4671                cfg->x_last_basic_block, bb);
4672
4673   /* The statements in BB need to be associated with a new TREE_BLOCK.
4674      Labels need to be associated with a new label-to-block map.  */
4675   memset (&d, 0, sizeof (d));
4676   d.vars_to_remove = vars_to_remove;
4677
4678   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4679     {
4680       tree stmt = bsi_stmt (si);
4681       int region;
4682
4683       d.from_context = cfun->decl;
4684       d.to_context = dest_cfun->decl;
4685       d.remap_decls_p = true;
4686       d.new_label_map = new_label_map;
4687       if (TREE_BLOCK (stmt))
4688         d.block = DECL_INITIAL (dest_cfun->decl);
4689
4690       walk_tree (&stmt, move_stmt_r, &d, NULL);
4691
4692       if (TREE_CODE (stmt) == LABEL_EXPR)
4693         {
4694           tree label = LABEL_EXPR_LABEL (stmt);
4695           int uid = LABEL_DECL_UID (label);
4696
4697           gcc_assert (uid > -1);
4698
4699           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
4700           if (old_len <= (unsigned) uid)
4701             {
4702               new_len = 3 * uid / 2;
4703               VEC_safe_grow (basic_block, gc, cfg->x_label_to_block_map,
4704                              new_len);
4705               addr = VEC_address (basic_block, cfg->x_label_to_block_map);
4706               memset (&addr[old_len], 0,
4707                       sizeof (basic_block) * (new_len - old_len));
4708             }
4709
4710           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
4711           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
4712
4713           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
4714
4715           if (uid >= dest_cfun->last_label_uid)
4716             dest_cfun->last_label_uid = uid + 1;
4717         }
4718       else if (TREE_CODE (stmt) == RESX_EXPR && eh_offset != 0)
4719         TREE_OPERAND (stmt, 0) =
4720           build_int_cst (NULL_TREE,
4721                          TREE_INT_CST_LOW (TREE_OPERAND (stmt, 0))
4722                          + eh_offset);
4723
4724       region = lookup_stmt_eh_region (stmt);
4725       if (region >= 0)
4726         {
4727           add_stmt_to_eh_region_fn (dest_cfun, stmt, region + eh_offset);
4728           remove_stmt_from_eh_region (stmt);
4729         }
4730     }
4731 }
4732
4733 /* Examine the statements in BB (which is in SRC_CFUN); find and return
4734    the outermost EH region.  Use REGION as the incoming base EH region.  */
4735
4736 static int
4737 find_outermost_region_in_block (struct function *src_cfun,
4738                                 basic_block bb, int region)
4739 {
4740   block_stmt_iterator si;
4741
4742   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
4743     {
4744       tree stmt = bsi_stmt (si);
4745       int stmt_region;
4746
4747       stmt_region = lookup_stmt_eh_region_fn (src_cfun, stmt);
4748       if (stmt_region > 0)
4749         {
4750           if (region < 0)
4751             region = stmt_region;
4752           else if (stmt_region != region)
4753             {
4754               region = eh_region_outermost (src_cfun, stmt_region, region);
4755               gcc_assert (region != -1);
4756             }
4757         }
4758     }
4759
4760   return region;
4761 }
4762
4763 static tree
4764 new_label_mapper (tree decl, void *data)
4765 {
4766   htab_t hash = (htab_t) data;
4767   struct tree_map *m;
4768   void **slot;
4769
4770   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
4771
4772   m = xmalloc (sizeof (struct tree_map));
4773   m->hash = DECL_UID (decl);
4774   m->from = decl;
4775   m->to = create_artificial_label ();
4776   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
4777
4778   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
4779   gcc_assert (*slot == NULL);
4780
4781   *slot = m;
4782
4783   return m->to;
4784 }
4785
4786 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
4787    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
4788    single basic block in the original CFG and the new basic block is
4789    returned.  DEST_CFUN must not have a CFG yet.
4790
4791    Note that the region need not be a pure SESE region.  Blocks inside
4792    the region may contain calls to abort/exit.  The only restriction
4793    is that ENTRY_BB should be the only entry point and it must
4794    dominate EXIT_BB.
4795
4796    All local variables referenced in the region are assumed to be in
4797    the corresponding BLOCK_VARS and unexpanded variable lists
4798    associated with DEST_CFUN.  */
4799
4800 basic_block
4801 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
4802                         basic_block exit_bb)
4803 {
4804   VEC(basic_block,heap) *bbs;
4805   basic_block after, bb, *entry_pred, *exit_succ;
4806   struct function *saved_cfun;
4807   int *entry_flag, *exit_flag, eh_offset;
4808   unsigned i, num_entry_edges, num_exit_edges;
4809   edge e;
4810   edge_iterator ei;
4811   bitmap vars_to_remove;
4812   htab_t new_label_map;
4813
4814   saved_cfun = cfun;
4815
4816   /* Collect all the blocks in the region.  Manually add ENTRY_BB
4817      because it won't be added by dfs_enumerate_from.  */
4818   calculate_dominance_info (CDI_DOMINATORS);
4819
4820   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
4821      region.  */
4822   gcc_assert (entry_bb != exit_bb
4823               && dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
4824
4825   bbs = NULL;
4826   VEC_safe_push (basic_block, heap, bbs, entry_bb);
4827   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
4828
4829   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
4830      the predecessor edges to ENTRY_BB and the successor edges to
4831      EXIT_BB so that we can re-attach them to the new basic block that
4832      will replace the region.  */
4833   num_entry_edges = EDGE_COUNT (entry_bb->preds);
4834   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
4835   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
4836   i = 0;
4837   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
4838     {
4839       entry_flag[i] = e->flags;
4840       entry_pred[i++] = e->src;
4841       remove_edge (e);
4842     }
4843
4844   num_exit_edges = EDGE_COUNT (exit_bb->succs);
4845   exit_succ = (basic_block *) xcalloc (num_exit_edges, sizeof (basic_block));
4846   exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
4847   i = 0;
4848   for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
4849     {
4850       exit_flag[i] = e->flags;
4851       exit_succ[i++] = e->dest;
4852       remove_edge (e);
4853     }
4854
4855   /* Switch context to the child function to initialize DEST_FN's CFG.  */
4856   gcc_assert (dest_cfun->cfg == NULL);
4857   cfun = dest_cfun;
4858
4859   init_empty_tree_cfg ();
4860
4861   /* Initialize EH information for the new function.  */
4862   eh_offset = 0;
4863   new_label_map = NULL;
4864   if (saved_cfun->eh)
4865     {
4866       int region = -1;
4867
4868       for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4869         region = find_outermost_region_in_block (saved_cfun, bb, region);
4870
4871       init_eh_for_function ();
4872       if (region != -1)
4873         {
4874           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
4875           eh_offset = duplicate_eh_regions (saved_cfun, new_label_mapper,
4876                                             new_label_map, region, 0);
4877         }
4878     }
4879
4880   cfun = saved_cfun;
4881
4882   /* Move blocks from BBS into DEST_CFUN.  */
4883   gcc_assert (VEC_length (basic_block, bbs) >= 2);
4884   after = dest_cfun->cfg->x_entry_block_ptr;
4885   vars_to_remove = BITMAP_ALLOC (NULL);
4886   for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
4887     {
4888       /* No need to update edge counts on the last block.  It has
4889          already been updated earlier when we detached the region from
4890          the original CFG.  */
4891       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, vars_to_remove,
4892                         new_label_map, eh_offset);
4893       after = bb;
4894     }
4895
4896   if (new_label_map)
4897     htab_delete (new_label_map);
4898
4899   /* Remove the variables marked in VARS_TO_REMOVE from
4900      CFUN->UNEXPANDED_VAR_LIST.  Otherwise, they will be given a
4901      DECL_RTL in the context of CFUN.  */
4902   if (!bitmap_empty_p (vars_to_remove))
4903     {
4904       tree *p;
4905
4906       for (p = &cfun->unexpanded_var_list; *p; )
4907         {
4908           tree var = TREE_VALUE (*p);
4909           if (bitmap_bit_p (vars_to_remove, DECL_UID (var)))
4910             {
4911               *p = TREE_CHAIN (*p);
4912               continue;
4913             }
4914
4915           p = &TREE_CHAIN (*p);
4916         }
4917     }
4918
4919   BITMAP_FREE (vars_to_remove);
4920
4921   /* Rewire the entry and exit blocks.  The successor to the entry
4922      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
4923      the child function.  Similarly, the predecessor of DEST_FN's
4924      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
4925      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
4926      various CFG manipulation function get to the right CFG.
4927
4928      FIXME, this is silly.  The CFG ought to become a parameter to
4929      these helpers.  */
4930   cfun = dest_cfun;
4931   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
4932   make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
4933   cfun = saved_cfun;
4934
4935   /* Back in the original function, the SESE region has disappeared,
4936      create a new basic block in its place.  */
4937   bb = create_empty_bb (entry_pred[0]);
4938   for (i = 0; i < num_entry_edges; i++)
4939     make_edge (entry_pred[i], bb, entry_flag[i]);
4940
4941   for (i = 0; i < num_exit_edges; i++)
4942     make_edge (bb, exit_succ[i], exit_flag[i]);
4943
4944   free (exit_flag);
4945   free (entry_flag);
4946   free (entry_pred);
4947   free (exit_succ);
4948   free_dominance_info (CDI_DOMINATORS);
4949   free_dominance_info (CDI_POST_DOMINATORS);
4950   VEC_free (basic_block, heap, bbs);
4951
4952   return bb;
4953 }
4954
4955
4956 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4957
4958 void
4959 dump_function_to_file (tree fn, FILE *file, int flags)
4960 {
4961   tree arg, vars, var;
4962   bool ignore_topmost_bind = false, any_var = false;
4963   basic_block bb;
4964   tree chain;
4965   struct function *saved_cfun;
4966
4967   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4968
4969   arg = DECL_ARGUMENTS (fn);
4970   while (arg)
4971     {
4972       print_generic_expr (file, arg, dump_flags);
4973       if (TREE_CHAIN (arg))
4974         fprintf (file, ", ");
4975       arg = TREE_CHAIN (arg);
4976     }
4977   fprintf (file, ")\n");
4978
4979   if (flags & TDF_DETAILS)
4980     dump_eh_tree (file, DECL_STRUCT_FUNCTION (fn));
4981   if (flags & TDF_RAW)
4982     {
4983       dump_node (fn, TDF_SLIM | flags, file);
4984       return;
4985     }
4986
4987   /* Switch CFUN to point to FN.  */
4988   saved_cfun = cfun;
4989   cfun = DECL_STRUCT_FUNCTION (fn);
4990
4991   /* When GIMPLE is lowered, the variables are no longer available in
4992      BIND_EXPRs, so display them separately.  */
4993   if (cfun && cfun->decl == fn && cfun->unexpanded_var_list)
4994     {
4995       ignore_topmost_bind = true;
4996
4997       fprintf (file, "{\n");
4998       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
4999         {
5000           var = TREE_VALUE (vars);
5001
5002           print_generic_decl (file, var, flags);
5003           fprintf (file, "\n");
5004
5005           any_var = true;
5006         }
5007     }
5008
5009   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
5010     {
5011       /* Make a CFG based dump.  */
5012       check_bb_profile (ENTRY_BLOCK_PTR, file);
5013       if (!ignore_topmost_bind)
5014         fprintf (file, "{\n");
5015
5016       if (any_var && n_basic_blocks)
5017         fprintf (file, "\n");
5018
5019       FOR_EACH_BB (bb)
5020         dump_generic_bb (file, bb, 2, flags);
5021
5022       fprintf (file, "}\n");
5023       check_bb_profile (EXIT_BLOCK_PTR, file);
5024     }
5025   else
5026     {
5027       int indent;
5028
5029       /* Make a tree based dump.  */
5030       chain = DECL_SAVED_TREE (fn);
5031
5032       if (chain && TREE_CODE (chain) == BIND_EXPR)
5033         {
5034           if (ignore_topmost_bind)
5035             {
5036               chain = BIND_EXPR_BODY (chain);
5037               indent = 2;
5038             }
5039           else
5040             indent = 0;
5041         }
5042       else
5043         {
5044           if (!ignore_topmost_bind)
5045             fprintf (file, "{\n");
5046           indent = 2;
5047         }
5048
5049       if (any_var)
5050         fprintf (file, "\n");
5051
5052       print_generic_stmt_indented (file, chain, flags, indent);
5053       if (ignore_topmost_bind)
5054         fprintf (file, "}\n");
5055     }
5056
5057   fprintf (file, "\n\n");
5058
5059   /* Restore CFUN.  */
5060   cfun = saved_cfun;
5061 }
5062
5063
5064 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
5065
5066 void
5067 debug_function (tree fn, int flags)
5068 {
5069   dump_function_to_file (fn, stderr, flags);
5070 }
5071
5072
5073 /* Pretty print of the loops intermediate representation.  */
5074 static void print_loop (FILE *, struct loop *, int);
5075 static void print_pred_bbs (FILE *, basic_block bb);
5076 static void print_succ_bbs (FILE *, basic_block bb);
5077
5078
5079 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
5080
5081 static void
5082 print_pred_bbs (FILE *file, basic_block bb)
5083 {
5084   edge e;
5085   edge_iterator ei;
5086
5087   FOR_EACH_EDGE (e, ei, bb->preds)
5088     fprintf (file, "bb_%d ", e->src->index);
5089 }
5090
5091
5092 /* Print on FILE the indexes for the successors of basic_block BB.  */
5093
5094 static void
5095 print_succ_bbs (FILE *file, basic_block bb)
5096 {
5097   edge e;
5098   edge_iterator ei;
5099
5100   FOR_EACH_EDGE (e, ei, bb->succs)
5101     fprintf (file, "bb_%d ", e->dest->index);
5102 }
5103
5104
5105 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
5106
5107 static void
5108 print_loop (FILE *file, struct loop *loop, int indent)
5109 {
5110   char *s_indent;
5111   basic_block bb;
5112
5113   if (loop == NULL)
5114     return;
5115
5116   s_indent = (char *) alloca ((size_t) indent + 1);
5117   memset ((void *) s_indent, ' ', (size_t) indent);
5118   s_indent[indent] = '\0';
5119
5120   /* Print the loop's header.  */
5121   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
5122
5123   /* Print the loop's body.  */
5124   fprintf (file, "%s{\n", s_indent);
5125   FOR_EACH_BB (bb)
5126     if (bb->loop_father == loop)
5127       {
5128         /* Print the basic_block's header.  */
5129         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
5130         print_pred_bbs (file, bb);
5131         fprintf (file, "}, succs = {");
5132         print_succ_bbs (file, bb);
5133         fprintf (file, "})\n");
5134
5135         /* Print the basic_block's body.  */
5136         fprintf (file, "%s  {\n", s_indent);
5137         tree_dump_bb (bb, file, indent + 4);
5138         fprintf (file, "%s  }\n", s_indent);
5139       }
5140
5141   print_loop (file, loop->inner, indent + 2);
5142   fprintf (file, "%s}\n", s_indent);
5143   print_loop (file, loop->next, indent);
5144 }
5145
5146
5147 /* Follow a CFG edge from the entry point of the program, and on entry
5148    of a loop, pretty print the loop structure on FILE.  */
5149
5150 void
5151 print_loop_ir (FILE *file)
5152 {
5153   basic_block bb;
5154
5155   bb = BASIC_BLOCK (NUM_FIXED_BLOCKS);
5156   if (bb && bb->loop_father)
5157     print_loop (file, bb->loop_father, 0);
5158 }
5159
5160
5161 /* Debugging loops structure at tree level.  */
5162
5163 void
5164 debug_loop_ir (void)
5165 {
5166   print_loop_ir (stderr);
5167 }
5168
5169
5170 /* Return true if BB ends with a call, possibly followed by some
5171    instructions that must stay with the call.  Return false,
5172    otherwise.  */
5173
5174 static bool
5175 tree_block_ends_with_call_p (basic_block bb)
5176 {
5177   block_stmt_iterator bsi = bsi_last (bb);
5178   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
5179 }
5180
5181
5182 /* Return true if BB ends with a conditional branch.  Return false,
5183    otherwise.  */
5184
5185 static bool
5186 tree_block_ends_with_condjump_p (basic_block bb)
5187 {
5188   tree stmt = last_stmt (bb);
5189   return (stmt && TREE_CODE (stmt) == COND_EXPR);
5190 }
5191
5192
5193 /* Return true if we need to add fake edge to exit at statement T.
5194    Helper function for tree_flow_call_edges_add.  */
5195
5196 static bool
5197 need_fake_edge_p (tree t)
5198 {
5199   tree call;
5200
5201   /* NORETURN and LONGJMP calls already have an edge to exit.
5202      CONST and PURE calls do not need one.
5203      We don't currently check for CONST and PURE here, although
5204      it would be a good idea, because those attributes are
5205      figured out from the RTL in mark_constant_function, and
5206      the counter incrementation code from -fprofile-arcs
5207      leads to different results from -fbranch-probabilities.  */
5208   call = get_call_expr_in (t);
5209   if (call
5210       && !(call_expr_flags (call) & ECF_NORETURN))
5211     return true;
5212
5213   if (TREE_CODE (t) == ASM_EXPR
5214        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
5215     return true;
5216
5217   return false;
5218 }
5219
5220
5221 /* Add fake edges to the function exit for any non constant and non
5222    noreturn calls, volatile inline assembly in the bitmap of blocks
5223    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
5224    the number of blocks that were split.
5225
5226    The goal is to expose cases in which entering a basic block does
5227    not imply that all subsequent instructions must be executed.  */
5228
5229 static int
5230 tree_flow_call_edges_add (sbitmap blocks)
5231 {
5232   int i;
5233   int blocks_split = 0;
5234   int last_bb = last_basic_block;
5235   bool check_last_block = false;
5236
5237   if (n_basic_blocks == NUM_FIXED_BLOCKS)
5238     return 0;
5239
5240   if (! blocks)
5241     check_last_block = true;
5242   else
5243     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
5244
5245   /* In the last basic block, before epilogue generation, there will be
5246      a fallthru edge to EXIT.  Special care is required if the last insn
5247      of the last basic block is a call because make_edge folds duplicate
5248      edges, which would result in the fallthru edge also being marked
5249      fake, which would result in the fallthru edge being removed by
5250      remove_fake_edges, which would result in an invalid CFG.
5251
5252      Moreover, we can't elide the outgoing fake edge, since the block
5253      profiler needs to take this into account in order to solve the minimal
5254      spanning tree in the case that the call doesn't return.
5255
5256      Handle this by adding a dummy instruction in a new last basic block.  */
5257   if (check_last_block)
5258     {
5259       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
5260       block_stmt_iterator bsi = bsi_last (bb);
5261       tree t = NULL_TREE;
5262       if (!bsi_end_p (bsi))
5263         t = bsi_stmt (bsi);
5264
5265       if (t && need_fake_edge_p (t))
5266         {
5267           edge e;
5268
5269           e = find_edge (bb, EXIT_BLOCK_PTR);
5270           if (e)
5271             {
5272               bsi_insert_on_edge (e, build_empty_stmt ());
5273               bsi_commit_edge_inserts ();
5274             }
5275         }
5276     }
5277
5278   /* Now add fake edges to the function exit for any non constant
5279      calls since there is no way that we can determine if they will
5280      return or not...  */
5281   for (i = 0; i < last_bb; i++)
5282     {
5283       basic_block bb = BASIC_BLOCK (i);
5284       block_stmt_iterator bsi;
5285       tree stmt, last_stmt;
5286
5287       if (!bb)
5288         continue;
5289
5290       if (blocks && !TEST_BIT (blocks, i))
5291         continue;
5292
5293       bsi = bsi_last (bb);
5294       if (!bsi_end_p (bsi))
5295         {
5296           last_stmt = bsi_stmt (bsi);
5297           do
5298             {
5299               stmt = bsi_stmt (bsi);
5300               if (need_fake_edge_p (stmt))
5301                 {
5302                   edge e;
5303                   /* The handling above of the final block before the
5304                      epilogue should be enough to verify that there is
5305                      no edge to the exit block in CFG already.
5306                      Calling make_edge in such case would cause us to
5307                      mark that edge as fake and remove it later.  */
5308 #ifdef ENABLE_CHECKING
5309                   if (stmt == last_stmt)
5310                     {
5311                       e = find_edge (bb, EXIT_BLOCK_PTR);
5312                       gcc_assert (e == NULL);
5313                     }
5314 #endif
5315
5316                   /* Note that the following may create a new basic block
5317                      and renumber the existing basic blocks.  */
5318                   if (stmt != last_stmt)
5319                     {
5320                       e = split_block (bb, stmt);
5321                       if (e)
5322                         blocks_split++;
5323                     }
5324                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
5325                 }
5326               bsi_prev (&bsi);
5327             }
5328           while (!bsi_end_p (bsi));
5329         }
5330     }
5331
5332   if (blocks_split)
5333     verify_flow_info ();
5334
5335   return blocks_split;
5336 }
5337
5338 bool
5339 tree_purge_dead_eh_edges (basic_block bb)
5340 {
5341   bool changed = false;
5342   edge e;
5343   edge_iterator ei;
5344   tree stmt = last_stmt (bb);
5345
5346   if (stmt && tree_can_throw_internal (stmt))
5347     return false;
5348
5349   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
5350     {
5351       if (e->flags & EDGE_EH)
5352         {
5353           remove_edge (e);
5354           changed = true;
5355         }
5356       else
5357         ei_next (&ei);
5358     }
5359
5360   /* Removal of dead EH edges might change dominators of not
5361      just immediate successors.  E.g. when bb1 is changed so that
5362      it no longer can throw and bb1->bb3 and bb1->bb4 are dead
5363      eh edges purged by this function in:
5364            0
5365           / \
5366          v   v
5367          1-->2
5368         / \  |
5369        v   v |
5370        3-->4 |
5371         \    v
5372          --->5
5373              |
5374              -
5375      idom(bb5) must be recomputed.  For now just free the dominance
5376      info.  */
5377   if (changed)
5378     free_dominance_info (CDI_DOMINATORS);
5379
5380   return changed;
5381 }
5382
5383 bool
5384 tree_purge_all_dead_eh_edges (bitmap blocks)
5385 {
5386   bool changed = false;
5387   unsigned i;
5388   bitmap_iterator bi;
5389
5390   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
5391     {
5392       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
5393     }
5394
5395   return changed;
5396 }
5397
5398 /* This function is called whenever a new edge is created or
5399    redirected.  */
5400
5401 static void
5402 tree_execute_on_growing_pred (edge e)
5403 {
5404   basic_block bb = e->dest;
5405
5406   if (phi_nodes (bb))
5407     reserve_phi_args_for_new_edge (bb);
5408 }
5409
5410 /* This function is called immediately before edge E is removed from
5411    the edge vector E->dest->preds.  */
5412
5413 static void
5414 tree_execute_on_shrinking_pred (edge e)
5415 {
5416   if (phi_nodes (e->dest))
5417     remove_phi_args (e);
5418 }
5419
5420 /*---------------------------------------------------------------------------
5421   Helper functions for Loop versioning
5422   ---------------------------------------------------------------------------*/
5423
5424 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
5425    of 'first'. Both of them are dominated by 'new_head' basic block. When
5426    'new_head' was created by 'second's incoming edge it received phi arguments
5427    on the edge by split_edge(). Later, additional edge 'e' was created to
5428    connect 'new_head' and 'first'. Now this routine adds phi args on this
5429    additional edge 'e' that new_head to second edge received as part of edge
5430    splitting.
5431 */
5432
5433 static void
5434 tree_lv_adjust_loop_header_phi (basic_block first, basic_block second,
5435                                 basic_block new_head, edge e)
5436 {
5437   tree phi1, phi2;
5438   edge e2 = find_edge (new_head, second);
5439
5440   /* Because NEW_HEAD has been created by splitting SECOND's incoming
5441      edge, we should always have an edge from NEW_HEAD to SECOND.  */
5442   gcc_assert (e2 != NULL);
5443
5444   /* Browse all 'second' basic block phi nodes and add phi args to
5445      edge 'e' for 'first' head. PHI args are always in correct order.  */
5446
5447   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
5448        phi2 && phi1;
5449        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
5450     {
5451       tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
5452       add_phi_arg (phi1, def, e);
5453     }
5454 }
5455
5456 /* Adds a if else statement to COND_BB with condition COND_EXPR.
5457    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
5458    the destination of the ELSE part.  */
5459 static void
5460 tree_lv_add_condition_to_bb (basic_block first_head, basic_block second_head,
5461                             basic_block cond_bb, void *cond_e)
5462 {
5463   block_stmt_iterator bsi;
5464   tree goto1 = NULL_TREE;
5465   tree goto2 = NULL_TREE;
5466   tree new_cond_expr = NULL_TREE;
5467   tree cond_expr = (tree) cond_e;
5468   edge e0;
5469
5470   /* Build new conditional expr */
5471   goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
5472   goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
5473   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
5474
5475   /* Add new cond in cond_bb.  */
5476   bsi = bsi_start (cond_bb);
5477   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
5478   /* Adjust edges appropriately to connect new head with first head
5479      as well as second head.  */
5480   e0 = single_succ_edge (cond_bb);
5481   e0->flags &= ~EDGE_FALLTHRU;
5482   e0->flags |= EDGE_FALSE_VALUE;
5483 }
5484
5485 struct cfg_hooks tree_cfg_hooks = {
5486   "tree",
5487   tree_verify_flow_info,
5488   tree_dump_bb,                 /* dump_bb  */
5489   create_bb,                    /* create_basic_block  */
5490   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
5491   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
5492   remove_bb,                    /* delete_basic_block  */
5493   tree_split_block,             /* split_block  */
5494   tree_move_block_after,        /* move_block_after  */
5495   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
5496   tree_merge_blocks,            /* merge_blocks  */
5497   tree_predict_edge,            /* predict_edge  */
5498   tree_predicted_by_p,          /* predicted_by_p  */
5499   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
5500   tree_duplicate_bb,            /* duplicate_block  */
5501   tree_split_edge,              /* split_edge  */
5502   tree_make_forwarder_block,    /* make_forward_block  */
5503   NULL,                         /* tidy_fallthru_edge  */
5504   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
5505   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
5506   tree_flow_call_edges_add,     /* flow_call_edges_add */
5507   tree_execute_on_growing_pred, /* execute_on_growing_pred */
5508   tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
5509   tree_duplicate_loop_to_header_edge, /* duplicate loop for trees */
5510   tree_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5511   tree_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
5512   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
5513   flush_pending_stmts           /* flush_pending_stmts */
5514 };
5515
5516
5517 /* Split all critical edges.  */
5518
5519 static unsigned int
5520 split_critical_edges (void)
5521 {
5522   basic_block bb;
5523   edge e;
5524   edge_iterator ei;
5525
5526   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
5527      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
5528      mappings around the calls to split_edge.  */
5529   start_recording_case_labels ();
5530   FOR_ALL_BB (bb)
5531     {
5532       FOR_EACH_EDGE (e, ei, bb->succs)
5533         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
5534           {
5535             split_edge (e);
5536           }
5537     }
5538   end_recording_case_labels ();
5539   return 0;
5540 }
5541
5542 struct tree_opt_pass pass_split_crit_edges =
5543 {
5544   "crited",                          /* name */
5545   NULL,                          /* gate */
5546   split_critical_edges,          /* execute */
5547   NULL,                          /* sub */
5548   NULL,                          /* next */
5549   0,                             /* static_pass_number */
5550   TV_TREE_SPLIT_EDGES,           /* tv_id */
5551   PROP_cfg,                      /* properties required */
5552   PROP_no_crit_edges,            /* properties_provided */
5553   0,                             /* properties_destroyed */
5554   0,                             /* todo_flags_start */
5555   TODO_dump_func,                /* todo_flags_finish */
5556   0                              /* letter */
5557 };
5558
5559 \f
5560 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
5561    a temporary, make sure and register it to be renamed if necessary,
5562    and finally return the temporary.  Put the statements to compute
5563    EXP before the current statement in BSI.  */
5564
5565 tree
5566 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
5567 {
5568   tree t, new_stmt, orig_stmt;
5569
5570   if (is_gimple_val (exp))
5571     return exp;
5572
5573   t = make_rename_temp (type, NULL);
5574   new_stmt = build2 (MODIFY_EXPR, type, t, exp);
5575
5576   orig_stmt = bsi_stmt (*bsi);
5577   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
5578   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
5579
5580   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
5581
5582   return t;
5583 }
5584
5585 /* Build a ternary operation and gimplify it.  Emit code before BSI.
5586    Return the gimple_val holding the result.  */
5587
5588 tree
5589 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
5590                  tree type, tree a, tree b, tree c)
5591 {
5592   tree ret;
5593
5594   ret = fold_build3 (code, type, a, b, c);
5595   STRIP_NOPS (ret);
5596
5597   return gimplify_val (bsi, type, ret);
5598 }
5599
5600 /* Build a binary operation and gimplify it.  Emit code before BSI.
5601    Return the gimple_val holding the result.  */
5602
5603 tree
5604 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
5605                  tree type, tree a, tree b)
5606 {
5607   tree ret;
5608
5609   ret = fold_build2 (code, type, a, b);
5610   STRIP_NOPS (ret);
5611
5612   return gimplify_val (bsi, type, ret);
5613 }
5614
5615 /* Build a unary operation and gimplify it.  Emit code before BSI.
5616    Return the gimple_val holding the result.  */
5617
5618 tree
5619 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
5620                  tree a)
5621 {
5622   tree ret;
5623
5624   ret = fold_build1 (code, type, a);
5625   STRIP_NOPS (ret);
5626
5627   return gimplify_val (bsi, type, ret);
5628 }
5629
5630
5631 \f
5632 /* Emit return warnings.  */
5633
5634 static unsigned int
5635 execute_warn_function_return (void)
5636 {
5637 #ifdef USE_MAPPED_LOCATION
5638   source_location location;
5639 #else
5640   location_t *locus;
5641 #endif
5642   tree last;
5643   edge e;
5644   edge_iterator ei;
5645
5646   /* If we have a path to EXIT, then we do return.  */
5647   if (TREE_THIS_VOLATILE (cfun->decl)
5648       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
5649     {
5650 #ifdef USE_MAPPED_LOCATION
5651       location = UNKNOWN_LOCATION;
5652 #else
5653       locus = NULL;
5654 #endif
5655       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5656         {
5657           last = last_stmt (e->src);
5658           if (TREE_CODE (last) == RETURN_EXPR
5659 #ifdef USE_MAPPED_LOCATION
5660               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
5661 #else
5662               && (locus = EXPR_LOCUS (last)) != NULL)
5663 #endif
5664             break;
5665         }
5666 #ifdef USE_MAPPED_LOCATION
5667       if (location == UNKNOWN_LOCATION)
5668         location = cfun->function_end_locus;
5669       warning (0, "%H%<noreturn%> function does return", &location);
5670 #else
5671       if (!locus)
5672         locus = &cfun->function_end_locus;
5673       warning (0, "%H%<noreturn%> function does return", locus);
5674 #endif
5675     }
5676
5677   /* If we see "return;" in some basic block, then we do reach the end
5678      without returning a value.  */
5679   else if (warn_return_type
5680            && !TREE_NO_WARNING (cfun->decl)
5681            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
5682            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
5683     {
5684       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5685         {
5686           tree last = last_stmt (e->src);
5687           if (TREE_CODE (last) == RETURN_EXPR
5688               && TREE_OPERAND (last, 0) == NULL
5689               && !TREE_NO_WARNING (last))
5690             {
5691 #ifdef USE_MAPPED_LOCATION
5692               location = EXPR_LOCATION (last);
5693               if (location == UNKNOWN_LOCATION)
5694                   location = cfun->function_end_locus;
5695               warning (0, "%Hcontrol reaches end of non-void function", &location);
5696 #else
5697               locus = EXPR_LOCUS (last);
5698               if (!locus)
5699                 locus = &cfun->function_end_locus;
5700               warning (0, "%Hcontrol reaches end of non-void function", locus);
5701 #endif
5702               TREE_NO_WARNING (cfun->decl) = 1;
5703               break;
5704             }
5705         }
5706     }
5707   return 0;
5708 }
5709
5710
5711 /* Given a basic block B which ends with a conditional and has
5712    precisely two successors, determine which of the edges is taken if
5713    the conditional is true and which is taken if the conditional is
5714    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
5715
5716 void
5717 extract_true_false_edges_from_block (basic_block b,
5718                                      edge *true_edge,
5719                                      edge *false_edge)
5720 {
5721   edge e = EDGE_SUCC (b, 0);
5722
5723   if (e->flags & EDGE_TRUE_VALUE)
5724     {
5725       *true_edge = e;
5726       *false_edge = EDGE_SUCC (b, 1);
5727     }
5728   else
5729     {
5730       *false_edge = e;
5731       *true_edge = EDGE_SUCC (b, 1);
5732     }
5733 }
5734
5735 struct tree_opt_pass pass_warn_function_return =
5736 {
5737   NULL,                                 /* name */
5738   NULL,                                 /* gate */
5739   execute_warn_function_return,         /* execute */
5740   NULL,                                 /* sub */
5741   NULL,                                 /* next */
5742   0,                                    /* static_pass_number */
5743   0,                                    /* tv_id */
5744   PROP_cfg,                             /* properties_required */
5745   0,                                    /* properties_provided */
5746   0,                                    /* properties_destroyed */
5747   0,                                    /* todo_flags_start */
5748   0,                                    /* todo_flags_finish */
5749   0                                     /* letter */
5750 };
5751
5752 /* Emit noreturn warnings.  */
5753
5754 static unsigned int
5755 execute_warn_function_noreturn (void)
5756 {
5757   if (warn_missing_noreturn
5758       && !TREE_THIS_VOLATILE (cfun->decl)
5759       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
5760       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
5761     warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
5762              "for attribute %<noreturn%>",
5763              cfun->decl);
5764   return 0;
5765 }
5766
5767 struct tree_opt_pass pass_warn_function_noreturn =
5768 {
5769   NULL,                                 /* name */
5770   NULL,                                 /* gate */
5771   execute_warn_function_noreturn,       /* execute */
5772   NULL,                                 /* sub */
5773   NULL,                                 /* next */
5774   0,                                    /* static_pass_number */
5775   0,                                    /* tv_id */
5776   PROP_cfg,                             /* properties_required */
5777   0,                                    /* properties_provided */
5778   0,                                    /* properties_destroyed */
5779   0,                                    /* todo_flags_start */
5780   0,                                    /* todo_flags_finish */
5781   0                                     /* letter */
5782 };