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