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