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