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