gcc/tree-cfg.c

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