gcc/tree-cfg.c

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