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