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       mark_new_vars_to_rename (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 all single-valued PHI nodes from block B of the form
1308      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1309   bsi = bsi_last (a);
1310   for (phi = phi_nodes (b); phi; phi = phi_nodes (b))
1311     {
1312       tree def = PHI_RESULT (phi), use = PHI_ARG_DEF (phi, 0);
1313       tree copy;
1314
1315       if (!may_propagate_copy (def, use))
1316         {
1317           gcc_assert (is_gimple_reg (def));
1318
1319           /* Note that just emitting the copies is fine -- there is no problem
1320              with ordering of phi nodes.  This is because A is the single
1321              predecessor of B, therefore results of the phi nodes cannot
1322              appear as arguments of the phi nodes.  */
1323           copy = build2 (MODIFY_EXPR, void_type_node, def, use);
1324           bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
1325           SET_PHI_RESULT (phi, NULL_TREE);
1326           SSA_NAME_DEF_STMT (def) = copy;
1327         }
1328       else
1329         replace_uses_by (def, use);
1330
1331       remove_phi_node (phi, NULL);
1332     }
1333
1334   /* Ensure that B follows A.  */
1335   move_block_after (b, a);
1336
1337   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1338   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1339
1340   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
1341   for (bsi = bsi_start (b); !bsi_end_p (bsi);)
1342     {
1343       if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
1344         {
1345           tree label = bsi_stmt (bsi);
1346
1347           bsi_remove (&bsi);
1348           /* Now that we can thread computed gotos, we might have
1349              a situation where we have a forced label in block B
1350              However, the label at the start of block B might still be
1351              used in other ways (think about the runtime checking for
1352              Fortran assigned gotos).  So we can not just delete the
1353              label.  Instead we move the label to the start of block A.  */
1354           if (FORCED_LABEL (LABEL_EXPR_LABEL (label)))
1355             {
1356               block_stmt_iterator dest_bsi = bsi_start (a);
1357               bsi_insert_before (&dest_bsi, label, BSI_NEW_STMT);
1358             }
1359         }
1360       else
1361         {
1362           set_bb_for_stmt (bsi_stmt (bsi), a);
1363           bsi_next (&bsi);
1364         }
1365     }
1366
1367   /* Merge the chains.  */
1368   last = tsi_last (a->stmt_list);
1369   tsi_link_after (&last, b->stmt_list, TSI_NEW_STMT);
1370   b->stmt_list = NULL;
1371 }
1372
1373
1374 /* Walk the function tree removing unnecessary statements.
1375
1376      * Empty statement nodes are removed
1377
1378      * Unnecessary TRY_FINALLY and TRY_CATCH blocks are removed
1379
1380      * Unnecessary COND_EXPRs are removed
1381
1382      * Some unnecessary BIND_EXPRs are removed
1383
1384    Clearly more work could be done.  The trick is doing the analysis
1385    and removal fast enough to be a net improvement in compile times.
1386
1387    Note that when we remove a control structure such as a COND_EXPR
1388    BIND_EXPR, or TRY block, we will need to repeat this optimization pass
1389    to ensure we eliminate all the useless code.  */
1390
1391 struct rus_data
1392 {
1393   tree *last_goto;
1394   bool repeat;
1395   bool may_throw;
1396   bool may_branch;
1397   bool has_label;
1398 };
1399
1400 static void remove_useless_stmts_1 (tree *, struct rus_data *);
1401
1402 static bool
1403 remove_useless_stmts_warn_notreached (tree stmt)
1404 {
1405   if (EXPR_HAS_LOCATION (stmt))
1406     {
1407       location_t loc = EXPR_LOCATION (stmt);
1408       if (LOCATION_LINE (loc) > 0)
1409         {
1410           warning (0, "%Hwill never be executed", &loc);
1411           return true;
1412         }
1413     }
1414
1415   switch (TREE_CODE (stmt))
1416     {
1417     case STATEMENT_LIST:
1418       {
1419         tree_stmt_iterator i;
1420         for (i = tsi_start (stmt); !tsi_end_p (i); tsi_next (&i))
1421           if (remove_useless_stmts_warn_notreached (tsi_stmt (i)))
1422             return true;
1423       }
1424       break;
1425
1426     case COND_EXPR:
1427       if (remove_useless_stmts_warn_notreached (COND_EXPR_COND (stmt)))
1428         return true;
1429       if (remove_useless_stmts_warn_notreached (COND_EXPR_THEN (stmt)))
1430         return true;
1431       if (remove_useless_stmts_warn_notreached (COND_EXPR_ELSE (stmt)))
1432         return true;
1433       break;
1434
1435     case TRY_FINALLY_EXPR:
1436     case TRY_CATCH_EXPR:
1437       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 0)))
1438         return true;
1439       if (remove_useless_stmts_warn_notreached (TREE_OPERAND (stmt, 1)))
1440         return true;
1441       break;
1442
1443     case CATCH_EXPR:
1444       return remove_useless_stmts_warn_notreached (CATCH_BODY (stmt));
1445     case EH_FILTER_EXPR:
1446       return remove_useless_stmts_warn_notreached (EH_FILTER_FAILURE (stmt));
1447     case BIND_EXPR:
1448       return remove_useless_stmts_warn_notreached (BIND_EXPR_BLOCK (stmt));
1449
1450     default:
1451       /* Not a live container.  */
1452       break;
1453     }
1454
1455   return false;
1456 }
1457
1458 static void
1459 remove_useless_stmts_cond (tree *stmt_p, struct rus_data *data)
1460 {
1461   tree then_clause, else_clause, cond;
1462   bool save_has_label, then_has_label, else_has_label;
1463
1464   save_has_label = data->has_label;
1465   data->has_label = false;
1466   data->last_goto = NULL;
1467
1468   remove_useless_stmts_1 (&COND_EXPR_THEN (*stmt_p), data);
1469
1470   then_has_label = data->has_label;
1471   data->has_label = false;
1472   data->last_goto = NULL;
1473
1474   remove_useless_stmts_1 (&COND_EXPR_ELSE (*stmt_p), data);
1475
1476   else_has_label = data->has_label;
1477   data->has_label = save_has_label | then_has_label | else_has_label;
1478
1479   then_clause = COND_EXPR_THEN (*stmt_p);
1480   else_clause = COND_EXPR_ELSE (*stmt_p);
1481   cond = fold (COND_EXPR_COND (*stmt_p));
1482
1483   /* If neither arm does anything at all, we can remove the whole IF.  */
1484   if (!TREE_SIDE_EFFECTS (then_clause) && !TREE_SIDE_EFFECTS (else_clause))
1485     {
1486       *stmt_p = build_empty_stmt ();
1487       data->repeat = true;
1488     }
1489
1490   /* If there are no reachable statements in an arm, then we can
1491      zap the entire conditional.  */
1492   else if (integer_nonzerop (cond) && !else_has_label)
1493     {
1494       if (warn_notreached)
1495         remove_useless_stmts_warn_notreached (else_clause);
1496       *stmt_p = then_clause;
1497       data->repeat = true;
1498     }
1499   else if (integer_zerop (cond) && !then_has_label)
1500     {
1501       if (warn_notreached)
1502         remove_useless_stmts_warn_notreached (then_clause);
1503       *stmt_p = else_clause;
1504       data->repeat = true;
1505     }
1506
1507   /* Check a couple of simple things on then/else with single stmts.  */
1508   else
1509     {
1510       tree then_stmt = expr_only (then_clause);
1511       tree else_stmt = expr_only (else_clause);
1512
1513       /* Notice branches to a common destination.  */
1514       if (then_stmt && else_stmt
1515           && TREE_CODE (then_stmt) == GOTO_EXPR
1516           && TREE_CODE (else_stmt) == GOTO_EXPR
1517           && (GOTO_DESTINATION (then_stmt) == GOTO_DESTINATION (else_stmt)))
1518         {
1519           *stmt_p = then_stmt;
1520           data->repeat = true;
1521         }
1522
1523       /* If the THEN/ELSE clause merely assigns a value to a variable or
1524          parameter which is already known to contain that value, then
1525          remove the useless THEN/ELSE clause.  */
1526       else if (TREE_CODE (cond) == VAR_DECL || TREE_CODE (cond) == PARM_DECL)
1527         {
1528           if (else_stmt
1529               && TREE_CODE (else_stmt) == MODIFY_EXPR
1530               && TREE_OPERAND (else_stmt, 0) == cond
1531               && integer_zerop (TREE_OPERAND (else_stmt, 1)))
1532             COND_EXPR_ELSE (*stmt_p) = alloc_stmt_list ();
1533         }
1534       else if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1535                && (TREE_CODE (TREE_OPERAND (cond, 0)) == VAR_DECL
1536                    || TREE_CODE (TREE_OPERAND (cond, 0)) == PARM_DECL)
1537                && TREE_CONSTANT (TREE_OPERAND (cond, 1)))
1538         {
1539           tree stmt = (TREE_CODE (cond) == EQ_EXPR
1540                        ? then_stmt : else_stmt);
1541           tree *location = (TREE_CODE (cond) == EQ_EXPR
1542                             ? &COND_EXPR_THEN (*stmt_p)
1543                             : &COND_EXPR_ELSE (*stmt_p));
1544
1545           if (stmt
1546               && TREE_CODE (stmt) == MODIFY_EXPR
1547               && TREE_OPERAND (stmt, 0) == TREE_OPERAND (cond, 0)
1548               && TREE_OPERAND (stmt, 1) == TREE_OPERAND (cond, 1))
1549             *location = alloc_stmt_list ();
1550         }
1551     }
1552
1553   /* Protect GOTOs in the arm of COND_EXPRs from being removed.  They
1554      would be re-introduced during lowering.  */
1555   data->last_goto = NULL;
1556 }
1557
1558
1559 static void
1560 remove_useless_stmts_tf (tree *stmt_p, struct rus_data *data)
1561 {
1562   bool save_may_branch, save_may_throw;
1563   bool this_may_branch, this_may_throw;
1564
1565   /* Collect may_branch and may_throw information for the body only.  */
1566   save_may_branch = data->may_branch;
1567   save_may_throw = data->may_throw;
1568   data->may_branch = false;
1569   data->may_throw = false;
1570   data->last_goto = NULL;
1571
1572   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1573
1574   this_may_branch = data->may_branch;
1575   this_may_throw = data->may_throw;
1576   data->may_branch |= save_may_branch;
1577   data->may_throw |= save_may_throw;
1578   data->last_goto = NULL;
1579
1580   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1581
1582   /* If the body is empty, then we can emit the FINALLY block without
1583      the enclosing TRY_FINALLY_EXPR.  */
1584   if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 0)))
1585     {
1586       *stmt_p = TREE_OPERAND (*stmt_p, 1);
1587       data->repeat = true;
1588     }
1589
1590   /* If the handler is empty, then we can emit the TRY block without
1591      the enclosing TRY_FINALLY_EXPR.  */
1592   else if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1593     {
1594       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1595       data->repeat = true;
1596     }
1597
1598   /* If the body neither throws, nor branches, then we can safely
1599      string the TRY and FINALLY blocks together.  */
1600   else if (!this_may_branch && !this_may_throw)
1601     {
1602       tree stmt = *stmt_p;
1603       *stmt_p = TREE_OPERAND (stmt, 0);
1604       append_to_statement_list (TREE_OPERAND (stmt, 1), stmt_p);
1605       data->repeat = true;
1606     }
1607 }
1608
1609
1610 static void
1611 remove_useless_stmts_tc (tree *stmt_p, struct rus_data *data)
1612 {
1613   bool save_may_throw, this_may_throw;
1614   tree_stmt_iterator i;
1615   tree stmt;
1616
1617   /* Collect may_throw information for the body only.  */
1618   save_may_throw = data->may_throw;
1619   data->may_throw = false;
1620   data->last_goto = NULL;
1621
1622   remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 0), data);
1623
1624   this_may_throw = data->may_throw;
1625   data->may_throw = save_may_throw;
1626
1627   /* If the body cannot throw, then we can drop the entire TRY_CATCH_EXPR.  */
1628   if (!this_may_throw)
1629     {
1630       if (warn_notreached)
1631         remove_useless_stmts_warn_notreached (TREE_OPERAND (*stmt_p, 1));
1632       *stmt_p = TREE_OPERAND (*stmt_p, 0);
1633       data->repeat = true;
1634       return;
1635     }
1636
1637   /* Process the catch clause specially.  We may be able to tell that
1638      no exceptions propagate past this point.  */
1639
1640   this_may_throw = true;
1641   i = tsi_start (TREE_OPERAND (*stmt_p, 1));
1642   stmt = tsi_stmt (i);
1643   data->last_goto = NULL;
1644
1645   switch (TREE_CODE (stmt))
1646     {
1647     case CATCH_EXPR:
1648       for (; !tsi_end_p (i); tsi_next (&i))
1649         {
1650           stmt = tsi_stmt (i);
1651           /* If we catch all exceptions, then the body does not
1652              propagate exceptions past this point.  */
1653           if (CATCH_TYPES (stmt) == NULL)
1654             this_may_throw = false;
1655           data->last_goto = NULL;
1656           remove_useless_stmts_1 (&CATCH_BODY (stmt), data);
1657         }
1658       break;
1659
1660     case EH_FILTER_EXPR:
1661       if (EH_FILTER_MUST_NOT_THROW (stmt))
1662         this_may_throw = false;
1663       else if (EH_FILTER_TYPES (stmt) == NULL)
1664         this_may_throw = false;
1665       remove_useless_stmts_1 (&EH_FILTER_FAILURE (stmt), data);
1666       break;
1667
1668     default:
1669       /* Otherwise this is a cleanup.  */
1670       remove_useless_stmts_1 (&TREE_OPERAND (*stmt_p, 1), data);
1671
1672       /* If the cleanup is empty, then we can emit the TRY block without
1673          the enclosing TRY_CATCH_EXPR.  */
1674       if (!TREE_SIDE_EFFECTS (TREE_OPERAND (*stmt_p, 1)))
1675         {
1676           *stmt_p = TREE_OPERAND (*stmt_p, 0);
1677           data->repeat = true;
1678         }
1679       break;
1680     }
1681   data->may_throw |= this_may_throw;
1682 }
1683
1684
1685 static void
1686 remove_useless_stmts_bind (tree *stmt_p, struct rus_data *data)
1687 {
1688   tree block;
1689
1690   /* First remove anything underneath the BIND_EXPR.  */
1691   remove_useless_stmts_1 (&BIND_EXPR_BODY (*stmt_p), data);
1692
1693   /* If the BIND_EXPR has no variables, then we can pull everything
1694      up one level and remove the BIND_EXPR, unless this is the toplevel
1695      BIND_EXPR for the current function or an inlined function.
1696
1697      When this situation occurs we will want to apply this
1698      optimization again.  */
1699   block = BIND_EXPR_BLOCK (*stmt_p);
1700   if (BIND_EXPR_VARS (*stmt_p) == NULL_TREE
1701       && *stmt_p != DECL_SAVED_TREE (current_function_decl)
1702       && (! block
1703           || ! BLOCK_ABSTRACT_ORIGIN (block)
1704           || (TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block))
1705               != FUNCTION_DECL)))
1706     {
1707       *stmt_p = BIND_EXPR_BODY (*stmt_p);
1708       data->repeat = true;
1709     }
1710 }
1711
1712
1713 static void
1714 remove_useless_stmts_goto (tree *stmt_p, struct rus_data *data)
1715 {
1716   tree dest = GOTO_DESTINATION (*stmt_p);
1717
1718   data->may_branch = true;
1719   data->last_goto = NULL;
1720
1721   /* Record the last goto expr, so that we can delete it if unnecessary.  */
1722   if (TREE_CODE (dest) == LABEL_DECL)
1723     data->last_goto = stmt_p;
1724 }
1725
1726
1727 static void
1728 remove_useless_stmts_label (tree *stmt_p, struct rus_data *data)
1729 {
1730   tree label = LABEL_EXPR_LABEL (*stmt_p);
1731
1732   data->has_label = true;
1733
1734   /* We do want to jump across non-local label receiver code.  */
1735   if (DECL_NONLOCAL (label))
1736     data->last_goto = NULL;
1737
1738   else if (data->last_goto && GOTO_DESTINATION (*data->last_goto) == label)
1739     {
1740       *data->last_goto = build_empty_stmt ();
1741       data->repeat = true;
1742     }
1743
1744   /* ??? Add something here to delete unused labels.  */
1745 }
1746
1747
1748 /* If the function is "const" or "pure", then clear TREE_SIDE_EFFECTS on its
1749    decl.  This allows us to eliminate redundant or useless
1750    calls to "const" functions.
1751
1752    Gimplifier already does the same operation, but we may notice functions
1753    being const and pure once their calls has been gimplified, so we need
1754    to update the flag.  */
1755
1756 static void
1757 update_call_expr_flags (tree call)
1758 {
1759   tree decl = get_callee_fndecl (call);
1760   if (!decl)
1761     return;
1762   if (call_expr_flags (call) & (ECF_CONST | ECF_PURE))
1763     TREE_SIDE_EFFECTS (call) = 0;
1764   if (TREE_NOTHROW (decl))
1765     TREE_NOTHROW (call) = 1;
1766 }
1767
1768
1769 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1770
1771 void
1772 notice_special_calls (tree t)
1773 {
1774   int flags = call_expr_flags (t);
1775
1776   if (flags & ECF_MAY_BE_ALLOCA)
1777     current_function_calls_alloca = true;
1778   if (flags & ECF_RETURNS_TWICE)
1779     current_function_calls_setjmp = true;
1780 }
1781
1782
1783 /* Clear flags set by notice_special_calls.  Used by dead code removal
1784    to update the flags.  */
1785
1786 void
1787 clear_special_calls (void)
1788 {
1789   current_function_calls_alloca = false;
1790   current_function_calls_setjmp = false;
1791 }
1792
1793
1794 static void
1795 remove_useless_stmts_1 (tree *tp, struct rus_data *data)
1796 {
1797   tree t = *tp, op;
1798
1799   switch (TREE_CODE (t))
1800     {
1801     case COND_EXPR:
1802       remove_useless_stmts_cond (tp, data);
1803       break;
1804
1805     case TRY_FINALLY_EXPR:
1806       remove_useless_stmts_tf (tp, data);
1807       break;
1808
1809     case TRY_CATCH_EXPR:
1810       remove_useless_stmts_tc (tp, data);
1811       break;
1812
1813     case BIND_EXPR:
1814       remove_useless_stmts_bind (tp, data);
1815       break;
1816
1817     case GOTO_EXPR:
1818       remove_useless_stmts_goto (tp, data);
1819       break;
1820
1821     case LABEL_EXPR:
1822       remove_useless_stmts_label (tp, data);
1823       break;
1824
1825     case RETURN_EXPR:
1826       fold_stmt (tp);
1827       data->last_goto = NULL;
1828       data->may_branch = true;
1829       break;
1830
1831     case CALL_EXPR:
1832       fold_stmt (tp);
1833       data->last_goto = NULL;
1834       notice_special_calls (t);
1835       update_call_expr_flags (t);
1836       if (tree_could_throw_p (t))
1837         data->may_throw = true;
1838       break;
1839
1840     case MODIFY_EXPR:
1841       data->last_goto = NULL;
1842       fold_stmt (tp);
1843       op = get_call_expr_in (t);
1844       if (op)
1845         {
1846           update_call_expr_flags (op);
1847           notice_special_calls (op);
1848         }
1849       if (tree_could_throw_p (t))
1850         data->may_throw = true;
1851       break;
1852
1853     case STATEMENT_LIST:
1854       {
1855         tree_stmt_iterator i = tsi_start (t);
1856         while (!tsi_end_p (i))
1857           {
1858             t = tsi_stmt (i);
1859             if (IS_EMPTY_STMT (t))
1860               {
1861                 tsi_delink (&i);
1862                 continue;
1863               }
1864
1865             remove_useless_stmts_1 (tsi_stmt_ptr (i), data);
1866
1867             t = tsi_stmt (i);
1868             if (TREE_CODE (t) == STATEMENT_LIST)
1869               {
1870                 tsi_link_before (&i, t, TSI_SAME_STMT);
1871                 tsi_delink (&i);
1872               }
1873             else
1874               tsi_next (&i);
1875           }
1876       }
1877       break;
1878     case ASM_EXPR:
1879       fold_stmt (tp);
1880       data->last_goto = NULL;
1881       break;
1882
1883     default:
1884       data->last_goto = NULL;
1885       break;
1886     }
1887 }
1888
1889 static void
1890 remove_useless_stmts (void)
1891 {
1892   struct rus_data data;
1893
1894   clear_special_calls ();
1895
1896   do
1897     {
1898       memset (&data, 0, sizeof (data));
1899       remove_useless_stmts_1 (&DECL_SAVED_TREE (current_function_decl), &data);
1900     }
1901   while (data.repeat);
1902 }
1903
1904
1905 struct tree_opt_pass pass_remove_useless_stmts =
1906 {
1907   "useless",                            /* name */
1908   NULL,                                 /* gate */
1909   remove_useless_stmts,                 /* execute */
1910   NULL,                                 /* sub */
1911   NULL,                                 /* next */
1912   0,                                    /* static_pass_number */
1913   0,                                    /* tv_id */
1914   PROP_gimple_any,                      /* properties_required */
1915   0,                                    /* properties_provided */
1916   0,                                    /* properties_destroyed */
1917   0,                                    /* todo_flags_start */
1918   TODO_dump_func,                       /* todo_flags_finish */
1919   0                                     /* letter */
1920 };
1921
1922 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1923
1924 static void
1925 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1926 {
1927   tree phi;
1928
1929   /* Since this block is no longer reachable, we can just delete all
1930      of its PHI nodes.  */
1931   phi = phi_nodes (bb);
1932   while (phi)
1933     {
1934       tree next = PHI_CHAIN (phi);
1935       remove_phi_node (phi, NULL_TREE);
1936       phi = next;
1937     }
1938
1939   /* Remove edges to BB's successors.  */
1940   while (EDGE_COUNT (bb->succs) > 0)
1941     remove_edge (EDGE_SUCC (bb, 0));
1942 }
1943
1944
1945 /* Remove statements of basic block BB.  */
1946
1947 static void
1948 remove_bb (basic_block bb)
1949 {
1950   block_stmt_iterator i;
1951 #ifdef USE_MAPPED_LOCATION
1952   source_location loc = UNKNOWN_LOCATION;
1953 #else
1954   source_locus loc = 0;
1955 #endif
1956
1957   if (dump_file)
1958     {
1959       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1960       if (dump_flags & TDF_DETAILS)
1961         {
1962           dump_bb (bb, dump_file, 0);
1963           fprintf (dump_file, "\n");
1964         }
1965     }
1966
1967   /* If we remove the header or the latch of a loop, mark the loop for
1968      removal by setting its header and latch to NULL.  */
1969   if (current_loops)
1970     {
1971       struct loop *loop = bb->loop_father;
1972
1973       if (loop->latch == bb
1974           || loop->header == bb)
1975         {
1976           loop->latch = NULL;
1977           loop->header = NULL;
1978         }
1979     }
1980
1981   /* Remove all the instructions in the block.  */
1982   for (i = bsi_start (bb); !bsi_end_p (i);)
1983     {
1984       tree stmt = bsi_stmt (i);
1985       if (TREE_CODE (stmt) == LABEL_EXPR
1986           && FORCED_LABEL (LABEL_EXPR_LABEL (stmt)))
1987         {
1988           basic_block new_bb = bb->prev_bb;
1989           block_stmt_iterator new_bsi = bsi_start (new_bb);
1990
1991           bsi_remove (&i);
1992           bsi_insert_before (&new_bsi, stmt, BSI_NEW_STMT);
1993         }
1994       else
1995         {
1996           /* Release SSA definitions if we are in SSA.  Note that we
1997              may be called when not in SSA.  For example,
1998              final_cleanup calls this function via
1999              cleanup_tree_cfg.  */
2000           if (in_ssa_p)
2001             release_defs (stmt);
2002
2003           bsi_remove (&i);
2004         }
2005
2006       /* Don't warn for removed gotos.  Gotos are often removed due to
2007          jump threading, thus resulting in bogus warnings.  Not great,
2008          since this way we lose warnings for gotos in the original
2009          program that are indeed unreachable.  */
2010       if (TREE_CODE (stmt) != GOTO_EXPR && EXPR_HAS_LOCATION (stmt) && !loc)
2011         {
2012 #ifdef USE_MAPPED_LOCATION
2013           if (EXPR_HAS_LOCATION (stmt))
2014             loc = EXPR_LOCATION (stmt);
2015 #else
2016           source_locus t;
2017           t = EXPR_LOCUS (stmt);
2018           if (t && LOCATION_LINE (*t) > 0)
2019             loc = t;
2020 #endif
2021         }
2022     }
2023
2024   /* If requested, give a warning that the first statement in the
2025      block is unreachable.  We walk statements backwards in the
2026      loop above, so the last statement we process is the first statement
2027      in the block.  */
2028 #ifdef USE_MAPPED_LOCATION
2029   if (loc > BUILTINS_LOCATION)
2030     warning (OPT_Wunreachable_code, "%Hwill never be executed", &loc);
2031 #else
2032   if (loc)
2033     warning (OPT_Wunreachable_code, "%Hwill never be executed", loc);
2034 #endif
2035
2036   remove_phi_nodes_and_edges_for_unreachable_block (bb);
2037 }
2038
2039
2040 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
2041    predicate VAL, return the edge that will be taken out of the block.
2042    If VAL does not match a unique edge, NULL is returned.  */
2043
2044 edge
2045 find_taken_edge (basic_block bb, tree val)
2046 {
2047   tree stmt;
2048
2049   stmt = last_stmt (bb);
2050
2051   gcc_assert (stmt);
2052   gcc_assert (is_ctrl_stmt (stmt));
2053   gcc_assert (val);
2054
2055   if (! is_gimple_min_invariant (val))
2056     return NULL;
2057
2058   if (TREE_CODE (stmt) == COND_EXPR)
2059     return find_taken_edge_cond_expr (bb, val);
2060
2061   if (TREE_CODE (stmt) == SWITCH_EXPR)
2062     return find_taken_edge_switch_expr (bb, val);
2063
2064   if (computed_goto_p (stmt))
2065     return find_taken_edge_computed_goto (bb, TREE_OPERAND( val, 0));
2066
2067   gcc_unreachable ();
2068 }
2069
2070 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
2071    statement, determine which of the outgoing edges will be taken out of the
2072    block.  Return NULL if either edge may be taken.  */
2073
2074 static edge
2075 find_taken_edge_computed_goto (basic_block bb, tree val)
2076 {
2077   basic_block dest;
2078   edge e = NULL;
2079
2080   dest = label_to_block (val);
2081   if (dest)
2082     {
2083       e = find_edge (bb, dest);
2084       gcc_assert (e != NULL);
2085     }
2086
2087   return e;
2088 }
2089
2090 /* Given a constant value VAL and the entry block BB to a COND_EXPR
2091    statement, determine which of the two edges will be taken out of the
2092    block.  Return NULL if either edge may be taken.  */
2093
2094 static edge
2095 find_taken_edge_cond_expr (basic_block bb, tree val)
2096 {
2097   edge true_edge, false_edge;
2098
2099   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
2100
2101   gcc_assert (TREE_CODE (val) == INTEGER_CST);
2102   return (zero_p (val) ? false_edge : true_edge);
2103 }
2104
2105 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2106    statement, determine which edge will be taken out of the block.  Return
2107    NULL if any edge may be taken.  */
2108
2109 static edge
2110 find_taken_edge_switch_expr (basic_block bb, tree val)
2111 {
2112   tree switch_expr, taken_case;
2113   basic_block dest_bb;
2114   edge e;
2115
2116   switch_expr = last_stmt (bb);
2117   taken_case = find_case_label_for_value (switch_expr, val);
2118   dest_bb = label_to_block (CASE_LABEL (taken_case));
2119
2120   e = find_edge (bb, dest_bb);
2121   gcc_assert (e);
2122   return e;
2123 }
2124
2125
2126 /* Return the CASE_LABEL_EXPR that SWITCH_EXPR will take for VAL.
2127    We can make optimal use here of the fact that the case labels are
2128    sorted: We can do a binary search for a case matching VAL.  */
2129
2130 static tree
2131 find_case_label_for_value (tree switch_expr, tree val)
2132 {
2133   tree vec = SWITCH_LABELS (switch_expr);
2134   size_t low, high, n = TREE_VEC_LENGTH (vec);
2135   tree default_case = TREE_VEC_ELT (vec, n - 1);
2136
2137   for (low = -1, high = n - 1; high - low > 1; )
2138     {
2139       size_t i = (high + low) / 2;
2140       tree t = TREE_VEC_ELT (vec, i);
2141       int cmp;
2142
2143       /* Cache the result of comparing CASE_LOW and val.  */
2144       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2145
2146       if (cmp > 0)
2147         high = i;
2148       else
2149         low = i;
2150
2151       if (CASE_HIGH (t) == NULL)
2152         {
2153           /* A singe-valued case label.  */
2154           if (cmp == 0)
2155             return t;
2156         }
2157       else
2158         {
2159           /* A case range.  We can only handle integer ranges.  */
2160           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2161             return t;
2162         }
2163     }
2164
2165   return default_case;
2166 }
2167
2168
2169
2170
2171 /*---------------------------------------------------------------------------
2172                               Debugging functions
2173 ---------------------------------------------------------------------------*/
2174
2175 /* Dump tree-specific information of block BB to file OUTF.  */
2176
2177 void
2178 tree_dump_bb (basic_block bb, FILE *outf, int indent)
2179 {
2180   dump_generic_bb (outf, bb, indent, TDF_VOPS);
2181 }
2182
2183
2184 /* Dump a basic block on stderr.  */
2185
2186 void
2187 debug_tree_bb (basic_block bb)
2188 {
2189   dump_bb (bb, stderr, 0);
2190 }
2191
2192
2193 /* Dump basic block with index N on stderr.  */
2194
2195 basic_block
2196 debug_tree_bb_n (int n)
2197 {
2198   debug_tree_bb (BASIC_BLOCK (n));
2199   return BASIC_BLOCK (n);
2200 }
2201
2202
2203 /* Dump the CFG on stderr.
2204
2205    FLAGS are the same used by the tree dumping functions
2206    (see TDF_* in tree.h).  */
2207
2208 void
2209 debug_tree_cfg (int flags)
2210 {
2211   dump_tree_cfg (stderr, flags);
2212 }
2213
2214
2215 /* Dump the program showing basic block boundaries on the given FILE.
2216
2217    FLAGS are the same used by the tree dumping functions (see TDF_* in
2218    tree.h).  */
2219
2220 void
2221 dump_tree_cfg (FILE *file, int flags)
2222 {
2223   if (flags & TDF_DETAILS)
2224     {
2225       const char *funcname
2226         = lang_hooks.decl_printable_name (current_function_decl, 2);
2227
2228       fputc ('\n', file);
2229       fprintf (file, ";; Function %s\n\n", funcname);
2230       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2231                n_basic_blocks, n_edges, last_basic_block);
2232
2233       brief_dump_cfg (file);
2234       fprintf (file, "\n");
2235     }
2236
2237   if (flags & TDF_STATS)
2238     dump_cfg_stats (file);
2239
2240   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2241 }
2242
2243
2244 /* Dump CFG statistics on FILE.  */
2245
2246 void
2247 dump_cfg_stats (FILE *file)
2248 {
2249   static long max_num_merged_labels = 0;
2250   unsigned long size, total = 0;
2251   long num_edges;
2252   basic_block bb;
2253   const char * const fmt_str   = "%-30s%-13s%12s\n";
2254   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2255   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2256   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2257   const char *funcname
2258     = lang_hooks.decl_printable_name (current_function_decl, 2);
2259
2260
2261   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2262
2263   fprintf (file, "---------------------------------------------------------\n");
2264   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2265   fprintf (file, fmt_str, "", "  instances  ", "used ");
2266   fprintf (file, "---------------------------------------------------------\n");
2267
2268   size = n_basic_blocks * sizeof (struct basic_block_def);
2269   total += size;
2270   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2271            SCALE (size), LABEL (size));
2272
2273   num_edges = 0;
2274   FOR_EACH_BB (bb)
2275     num_edges += EDGE_COUNT (bb->succs);
2276   size = num_edges * sizeof (struct edge_def);
2277   total += size;
2278   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2279
2280   fprintf (file, "---------------------------------------------------------\n");
2281   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2282            LABEL (total));
2283   fprintf (file, "---------------------------------------------------------\n");
2284   fprintf (file, "\n");
2285
2286   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2287     max_num_merged_labels = cfg_stats.num_merged_labels;
2288
2289   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2290            cfg_stats.num_merged_labels, max_num_merged_labels);
2291
2292   fprintf (file, "\n");
2293 }
2294
2295
2296 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2297    linked in the final executable.  */
2298
2299 void
2300 debug_cfg_stats (void)
2301 {
2302   dump_cfg_stats (stderr);
2303 }
2304
2305
2306 /* Dump the flowgraph to a .vcg FILE.  */
2307
2308 static void
2309 tree_cfg2vcg (FILE *file)
2310 {
2311   edge e;
2312   edge_iterator ei;
2313   basic_block bb;
2314   const char *funcname
2315     = lang_hooks.decl_printable_name (current_function_decl, 2);
2316
2317   /* Write the file header.  */
2318   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2319   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2320   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2321
2322   /* Write blocks and edges.  */
2323   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2324     {
2325       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2326                e->dest->index);
2327
2328       if (e->flags & EDGE_FAKE)
2329         fprintf (file, " linestyle: dotted priority: 10");
2330       else
2331         fprintf (file, " linestyle: solid priority: 100");
2332
2333       fprintf (file, " }\n");
2334     }
2335   fputc ('\n', file);
2336
2337   FOR_EACH_BB (bb)
2338     {
2339       enum tree_code head_code, end_code;
2340       const char *head_name, *end_name;
2341       int head_line = 0;
2342       int end_line = 0;
2343       tree first = first_stmt (bb);
2344       tree last = last_stmt (bb);
2345
2346       if (first)
2347         {
2348           head_code = TREE_CODE (first);
2349           head_name = tree_code_name[head_code];
2350           head_line = get_lineno (first);
2351         }
2352       else
2353         head_name = "no-statement";
2354
2355       if (last)
2356         {
2357           end_code = TREE_CODE (last);
2358           end_name = tree_code_name[end_code];
2359           end_line = get_lineno (last);
2360         }
2361       else
2362         end_name = "no-statement";
2363
2364       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2365                bb->index, bb->index, head_name, head_line, end_name,
2366                end_line);
2367
2368       FOR_EACH_EDGE (e, ei, bb->succs)
2369         {
2370           if (e->dest == EXIT_BLOCK_PTR)
2371             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2372           else
2373             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2374
2375           if (e->flags & EDGE_FAKE)
2376             fprintf (file, " priority: 10 linestyle: dotted");
2377           else
2378             fprintf (file, " priority: 100 linestyle: solid");
2379
2380           fprintf (file, " }\n");
2381         }
2382
2383       if (bb->next_bb != EXIT_BLOCK_PTR)
2384         fputc ('\n', file);
2385     }
2386
2387   fputs ("}\n\n", file);
2388 }
2389
2390
2391
2392 /*---------------------------------------------------------------------------
2393                              Miscellaneous helpers
2394 ---------------------------------------------------------------------------*/
2395
2396 /* Return true if T represents a stmt that always transfers control.  */
2397
2398 bool
2399 is_ctrl_stmt (tree t)
2400 {
2401   return (TREE_CODE (t) == COND_EXPR
2402           || TREE_CODE (t) == SWITCH_EXPR
2403           || TREE_CODE (t) == GOTO_EXPR
2404           || TREE_CODE (t) == RETURN_EXPR
2405           || TREE_CODE (t) == RESX_EXPR);
2406 }
2407
2408
2409 /* Return true if T is a statement that may alter the flow of control
2410    (e.g., a call to a non-returning function).  */
2411
2412 bool
2413 is_ctrl_altering_stmt (tree t)
2414 {
2415   tree call;
2416
2417   gcc_assert (t);
2418   call = get_call_expr_in (t);
2419   if (call)
2420     {
2421       /* A non-pure/const CALL_EXPR alters flow control if the current
2422          function has nonlocal labels.  */
2423       if (TREE_SIDE_EFFECTS (call) && current_function_has_nonlocal_label)
2424         return true;
2425
2426       /* A CALL_EXPR also alters control flow if it does not return.  */
2427       if (call_expr_flags (call) & ECF_NORETURN)
2428         return true;
2429     }
2430
2431   /* If a statement can throw, it alters control flow.  */
2432   return tree_can_throw_internal (t);
2433 }
2434
2435
2436 /* Return true if T is a computed goto.  */
2437
2438 bool
2439 computed_goto_p (tree t)
2440 {
2441   return (TREE_CODE (t) == GOTO_EXPR
2442           && TREE_CODE (GOTO_DESTINATION (t)) != LABEL_DECL);
2443 }
2444
2445
2446 /* Checks whether EXPR is a simple local goto.  */
2447
2448 bool
2449 simple_goto_p (tree expr)
2450 {
2451   return (TREE_CODE (expr) == GOTO_EXPR
2452           && TREE_CODE (GOTO_DESTINATION (expr)) == LABEL_DECL);
2453 }
2454
2455
2456 /* Return true if T should start a new basic block.  PREV_T is the
2457    statement preceding T.  It is used when T is a label or a case label.
2458    Labels should only start a new basic block if their previous statement
2459    wasn't a label.  Otherwise, sequence of labels would generate
2460    unnecessary basic blocks that only contain a single label.  */
2461
2462 static inline bool
2463 stmt_starts_bb_p (tree t, tree prev_t)
2464 {
2465   if (t == NULL_TREE)
2466     return false;
2467
2468   /* LABEL_EXPRs start a new basic block only if the preceding
2469      statement wasn't a label of the same type.  This prevents the
2470      creation of consecutive blocks that have nothing but a single
2471      label.  */
2472   if (TREE_CODE (t) == LABEL_EXPR)
2473     {
2474       /* Nonlocal and computed GOTO targets always start a new block.  */
2475       if (DECL_NONLOCAL (LABEL_EXPR_LABEL (t))
2476           || FORCED_LABEL (LABEL_EXPR_LABEL (t)))
2477         return true;
2478
2479       if (prev_t && TREE_CODE (prev_t) == LABEL_EXPR)
2480         {
2481           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (prev_t)))
2482             return true;
2483
2484           cfg_stats.num_merged_labels++;
2485           return false;
2486         }
2487       else
2488         return true;
2489     }
2490
2491   return false;
2492 }
2493
2494
2495 /* Return true if T should end a basic block.  */
2496
2497 bool
2498 stmt_ends_bb_p (tree t)
2499 {
2500   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2501 }
2502
2503
2504 /* Add gotos that used to be represented implicitly in the CFG.  */
2505
2506 void
2507 disband_implicit_edges (void)
2508 {
2509   basic_block bb;
2510   block_stmt_iterator last;
2511   edge e;
2512   edge_iterator ei;
2513   tree stmt, label;
2514
2515   FOR_EACH_BB (bb)
2516     {
2517       last = bsi_last (bb);
2518       stmt = last_stmt (bb);
2519
2520       if (stmt && TREE_CODE (stmt) == COND_EXPR)
2521         {
2522           /* Remove superfluous gotos from COND_EXPR branches.  Moved
2523              from cfg_remove_useless_stmts here since it violates the
2524              invariants for tree--cfg correspondence and thus fits better
2525              here where we do it anyway.  */
2526           e = find_edge (bb, bb->next_bb);
2527           if (e)
2528             {
2529               if (e->flags & EDGE_TRUE_VALUE)
2530                 COND_EXPR_THEN (stmt) = build_empty_stmt ();
2531               else if (e->flags & EDGE_FALSE_VALUE)
2532                 COND_EXPR_ELSE (stmt) = build_empty_stmt ();
2533               else
2534                 gcc_unreachable ();
2535               e->flags |= EDGE_FALLTHRU;
2536             }
2537
2538           continue;
2539         }
2540
2541       if (stmt && TREE_CODE (stmt) == RETURN_EXPR)
2542         {
2543           /* Remove the RETURN_EXPR if we may fall though to the exit
2544              instead.  */
2545           gcc_assert (single_succ_p (bb));
2546           gcc_assert (single_succ (bb) == EXIT_BLOCK_PTR);
2547
2548           if (bb->next_bb == EXIT_BLOCK_PTR
2549               && !TREE_OPERAND (stmt, 0))
2550             {
2551               bsi_remove (&last);
2552               single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
2553             }
2554           continue;
2555         }
2556
2557       /* There can be no fallthru edge if the last statement is a control
2558          one.  */
2559       if (stmt && is_ctrl_stmt (stmt))
2560         continue;
2561
2562       /* Find a fallthru edge and emit the goto if necessary.  */
2563       FOR_EACH_EDGE (e, ei, bb->succs)
2564         if (e->flags & EDGE_FALLTHRU)
2565           break;
2566
2567       if (!e || e->dest == bb->next_bb)
2568         continue;
2569
2570       gcc_assert (e->dest != EXIT_BLOCK_PTR);
2571       label = tree_block_label (e->dest);
2572
2573       stmt = build1 (GOTO_EXPR, void_type_node, label);
2574 #ifdef USE_MAPPED_LOCATION
2575       SET_EXPR_LOCATION (stmt, e->goto_locus);
2576 #else
2577       SET_EXPR_LOCUS (stmt, e->goto_locus);
2578 #endif
2579       bsi_insert_after (&last, stmt, BSI_NEW_STMT);
2580       e->flags &= ~EDGE_FALLTHRU;
2581     }
2582 }
2583
2584 /* Remove block annotations and other datastructures.  */
2585
2586 void
2587 delete_tree_cfg_annotations (void)
2588 {
2589   label_to_block_map = NULL;
2590 }
2591
2592
2593 /* Return the first statement in basic block BB.  */
2594
2595 tree
2596 first_stmt (basic_block bb)
2597 {
2598   block_stmt_iterator i = bsi_start (bb);
2599   return !bsi_end_p (i) ? bsi_stmt (i) : NULL_TREE;
2600 }
2601
2602
2603 /* Return the last statement in basic block BB.  */
2604
2605 tree
2606 last_stmt (basic_block bb)
2607 {
2608   block_stmt_iterator b = bsi_last (bb);
2609   return !bsi_end_p (b) ? bsi_stmt (b) : NULL_TREE;
2610 }
2611
2612
2613 /* Return a pointer to the last statement in block BB.  */
2614
2615 tree *
2616 last_stmt_ptr (basic_block bb)
2617 {
2618   block_stmt_iterator last = bsi_last (bb);
2619   return !bsi_end_p (last) ? bsi_stmt_ptr (last) : NULL;
2620 }
2621
2622
2623 /* Return the last statement of an otherwise empty block.  Return NULL
2624    if the block is totally empty, or if it contains more than one
2625    statement.  */
2626
2627 tree
2628 last_and_only_stmt (basic_block bb)
2629 {
2630   block_stmt_iterator i = bsi_last (bb);
2631   tree last, prev;
2632
2633   if (bsi_end_p (i))
2634     return NULL_TREE;
2635
2636   last = bsi_stmt (i);
2637   bsi_prev (&i);
2638   if (bsi_end_p (i))
2639     return last;
2640
2641   /* Empty statements should no longer appear in the instruction stream.
2642      Everything that might have appeared before should be deleted by
2643      remove_useless_stmts, and the optimizers should just bsi_remove
2644      instead of smashing with build_empty_stmt.
2645
2646      Thus the only thing that should appear here in a block containing
2647      one executable statement is a label.  */
2648   prev = bsi_stmt (i);
2649   if (TREE_CODE (prev) == LABEL_EXPR)
2650     return last;
2651   else
2652     return NULL_TREE;
2653 }
2654
2655
2656 /* Mark BB as the basic block holding statement T.  */
2657
2658 void
2659 set_bb_for_stmt (tree t, basic_block bb)
2660 {
2661   if (TREE_CODE (t) == PHI_NODE)
2662     PHI_BB (t) = bb;
2663   else if (TREE_CODE (t) == STATEMENT_LIST)
2664     {
2665       tree_stmt_iterator i;
2666       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2667         set_bb_for_stmt (tsi_stmt (i), bb);
2668     }
2669   else
2670     {
2671       stmt_ann_t ann = get_stmt_ann (t);
2672       ann->bb = bb;
2673
2674       /* If the statement is a label, add the label to block-to-labels map
2675          so that we can speed up edge creation for GOTO_EXPRs.  */
2676       if (TREE_CODE (t) == LABEL_EXPR)
2677         {
2678           int uid;
2679
2680           t = LABEL_EXPR_LABEL (t);
2681           uid = LABEL_DECL_UID (t);
2682           if (uid == -1)
2683             {
2684               LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
2685               if (VARRAY_SIZE (label_to_block_map) <= (unsigned) uid)
2686                 VARRAY_GROW (label_to_block_map, 3 * uid / 2);
2687             }
2688           else
2689             /* We're moving an existing label.  Make sure that we've
2690                 removed it from the old block.  */
2691             gcc_assert (!bb || !VARRAY_BB (label_to_block_map, uid));
2692           VARRAY_BB (label_to_block_map, uid) = bb;
2693         }
2694     }
2695 }
2696
2697 /* Finds iterator for STMT.  */
2698
2699 extern block_stmt_iterator
2700 bsi_for_stmt (tree stmt)
2701 {
2702   block_stmt_iterator bsi;
2703
2704   for (bsi = bsi_start (bb_for_stmt (stmt)); !bsi_end_p (bsi); bsi_next (&bsi))
2705     if (bsi_stmt (bsi) == stmt)
2706       return bsi;
2707
2708   gcc_unreachable ();
2709 }
2710
2711 /* Mark statement T as modified, and update it.  */
2712 static inline void
2713 update_modified_stmts (tree t)
2714 {
2715   if (TREE_CODE (t) == STATEMENT_LIST)
2716     {
2717       tree_stmt_iterator i;
2718       tree stmt;
2719       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
2720         {
2721           stmt = tsi_stmt (i);
2722           update_stmt_if_modified (stmt);
2723         }
2724     }
2725   else
2726     update_stmt_if_modified (t);
2727 }
2728
2729 /* Insert statement (or statement list) T before the statement
2730    pointed-to by iterator I.  M specifies how to update iterator I
2731    after insertion (see enum bsi_iterator_update).  */
2732
2733 void
2734 bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2735 {
2736   set_bb_for_stmt (t, i->bb);
2737   update_modified_stmts (t);
2738   tsi_link_before (&i->tsi, t, m);
2739 }
2740
2741
2742 /* Insert statement (or statement list) T after the statement
2743    pointed-to by iterator I.  M specifies how to update iterator I
2744    after insertion (see enum bsi_iterator_update).  */
2745
2746 void
2747 bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
2748 {
2749   set_bb_for_stmt (t, i->bb);
2750   update_modified_stmts (t);
2751   tsi_link_after (&i->tsi, t, m);
2752 }
2753
2754
2755 /* Remove the statement pointed to by iterator I.  The iterator is updated
2756    to the next statement.  */
2757
2758 void
2759 bsi_remove (block_stmt_iterator *i)
2760 {
2761   tree t = bsi_stmt (*i);
2762   set_bb_for_stmt (t, NULL);
2763   delink_stmt_imm_use (t);
2764   tsi_delink (&i->tsi);
2765   mark_stmt_modified (t);
2766 }
2767
2768
2769 /* Move the statement at FROM so it comes right after the statement at TO.  */
2770
2771 void
2772 bsi_move_after (block_stmt_iterator *from, block_stmt_iterator *to)
2773 {
2774   tree stmt = bsi_stmt (*from);
2775   bsi_remove (from);
2776   bsi_insert_after (to, stmt, BSI_SAME_STMT);
2777 }
2778
2779
2780 /* Move the statement at FROM so it comes right before the statement at TO.  */
2781
2782 void
2783 bsi_move_before (block_stmt_iterator *from, block_stmt_iterator *to)
2784 {
2785   tree stmt = bsi_stmt (*from);
2786   bsi_remove (from);
2787   bsi_insert_before (to, stmt, BSI_SAME_STMT);
2788 }
2789
2790
2791 /* Move the statement at FROM to the end of basic block BB.  */
2792
2793 void
2794 bsi_move_to_bb_end (block_stmt_iterator *from, basic_block bb)
2795 {
2796   block_stmt_iterator last = bsi_last (bb);
2797
2798   /* Have to check bsi_end_p because it could be an empty block.  */
2799   if (!bsi_end_p (last) && is_ctrl_stmt (bsi_stmt (last)))
2800     bsi_move_before (from, &last);
2801   else
2802     bsi_move_after (from, &last);
2803 }
2804
2805
2806 /* Replace the contents of the statement pointed to by iterator BSI
2807    with STMT.  If PRESERVE_EH_INFO is true, the exception handling
2808    information of the original statement is preserved.  */
2809
2810 void
2811 bsi_replace (const block_stmt_iterator *bsi, tree stmt, bool preserve_eh_info)
2812 {
2813   int eh_region;
2814   tree orig_stmt = bsi_stmt (*bsi);
2815
2816   SET_EXPR_LOCUS (stmt, EXPR_LOCUS (orig_stmt));
2817   set_bb_for_stmt (stmt, bsi->bb);
2818
2819   /* Preserve EH region information from the original statement, if
2820      requested by the caller.  */
2821   if (preserve_eh_info)
2822     {
2823       eh_region = lookup_stmt_eh_region (orig_stmt);
2824       if (eh_region >= 0)
2825         add_stmt_to_eh_region (stmt, eh_region);
2826     }
2827
2828   delink_stmt_imm_use (orig_stmt);
2829   *bsi_stmt_ptr (*bsi) = stmt;
2830   mark_stmt_modified (stmt);
2831   update_modified_stmts (stmt);
2832 }
2833
2834
2835 /* Insert the statement pointed-to by BSI into edge E.  Every attempt
2836    is made to place the statement in an existing basic block, but
2837    sometimes that isn't possible.  When it isn't possible, the edge is
2838    split and the statement is added to the new block.
2839
2840    In all cases, the returned *BSI points to the correct location.  The
2841    return value is true if insertion should be done after the location,
2842    or false if it should be done before the location.  If new basic block
2843    has to be created, it is stored in *NEW_BB.  */
2844
2845 static bool
2846 tree_find_edge_insert_loc (edge e, block_stmt_iterator *bsi,
2847                            basic_block *new_bb)
2848 {
2849   basic_block dest, src;
2850   tree tmp;
2851
2852   dest = e->dest;
2853  restart:
2854
2855   /* If the destination has one predecessor which has no PHI nodes,
2856      insert there.  Except for the exit block.
2857
2858      The requirement for no PHI nodes could be relaxed.  Basically we
2859      would have to examine the PHIs to prove that none of them used
2860      the value set by the statement we want to insert on E.  That
2861      hardly seems worth the effort.  */
2862   if (single_pred_p (dest)
2863       && ! phi_nodes (dest)
2864       && dest != EXIT_BLOCK_PTR)
2865     {
2866       *bsi = bsi_start (dest);
2867       if (bsi_end_p (*bsi))
2868         return true;
2869
2870       /* Make sure we insert after any leading labels.  */
2871       tmp = bsi_stmt (*bsi);
2872       while (TREE_CODE (tmp) == LABEL_EXPR)
2873         {
2874           bsi_next (bsi);
2875           if (bsi_end_p (*bsi))
2876             break;
2877           tmp = bsi_stmt (*bsi);
2878         }
2879
2880       if (bsi_end_p (*bsi))
2881         {
2882           *bsi = bsi_last (dest);
2883           return true;
2884         }
2885       else
2886         return false;
2887     }
2888
2889   /* If the source has one successor, the edge is not abnormal and
2890      the last statement does not end a basic block, insert there.
2891      Except for the entry block.  */
2892   src = e->src;
2893   if ((e->flags & EDGE_ABNORMAL) == 0
2894       && single_succ_p (src)
2895       && src != ENTRY_BLOCK_PTR)
2896     {
2897       *bsi = bsi_last (src);
2898       if (bsi_end_p (*bsi))
2899         return true;
2900
2901       tmp = bsi_stmt (*bsi);
2902       if (!stmt_ends_bb_p (tmp))
2903         return true;
2904
2905       /* Insert code just before returning the value.  We may need to decompose
2906          the return in the case it contains non-trivial operand.  */
2907       if (TREE_CODE (tmp) == RETURN_EXPR)
2908         {
2909           tree op = TREE_OPERAND (tmp, 0);
2910           if (!is_gimple_val (op))
2911             {
2912               gcc_assert (TREE_CODE (op) == MODIFY_EXPR);
2913               bsi_insert_before (bsi, op, BSI_NEW_STMT);
2914               TREE_OPERAND (tmp, 0) = TREE_OPERAND (op, 0);
2915             }
2916           bsi_prev (bsi);
2917           return true;
2918         }
2919     }
2920
2921   /* Otherwise, create a new basic block, and split this edge.  */
2922   dest = split_edge (e);
2923   if (new_bb)
2924     *new_bb = dest;
2925   e = single_pred_edge (dest);
2926   goto restart;
2927 }
2928
2929
2930 /* This routine will commit all pending edge insertions, creating any new
2931    basic blocks which are necessary.  */
2932
2933 void
2934 bsi_commit_edge_inserts (void)
2935 {
2936   basic_block bb;
2937   edge e;
2938   edge_iterator ei;
2939
2940   bsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
2941
2942   FOR_EACH_BB (bb)
2943     FOR_EACH_EDGE (e, ei, bb->succs)
2944       bsi_commit_one_edge_insert (e, NULL);
2945 }
2946
2947
2948 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
2949    to this block, otherwise set it to NULL.  */
2950
2951 void
2952 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
2953 {
2954   if (new_bb)
2955     *new_bb = NULL;
2956   if (PENDING_STMT (e))
2957     {
2958       block_stmt_iterator bsi;
2959       tree stmt = PENDING_STMT (e);
2960
2961       PENDING_STMT (e) = NULL_TREE;
2962
2963       if (tree_find_edge_insert_loc (e, &bsi, new_bb))
2964         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2965       else
2966         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2967     }
2968 }
2969
2970
2971 /* Add STMT to the pending list of edge E.  No actual insertion is
2972    made until a call to bsi_commit_edge_inserts () is made.  */
2973
2974 void
2975 bsi_insert_on_edge (edge e, tree stmt)
2976 {
2977   append_to_statement_list (stmt, &PENDING_STMT (e));
2978 }
2979
2980 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If a new
2981    block has to be created, it is returned.  */
2982
2983 basic_block
2984 bsi_insert_on_edge_immediate (edge e, tree stmt)
2985 {
2986   block_stmt_iterator bsi;
2987   basic_block new_bb = NULL;
2988
2989   gcc_assert (!PENDING_STMT (e));
2990
2991   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
2992     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2993   else
2994     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2995
2996   return new_bb;
2997 }
2998
2999 /*---------------------------------------------------------------------------
3000              Tree specific functions for CFG manipulation
3001 ---------------------------------------------------------------------------*/
3002
3003 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
3004
3005 static void
3006 reinstall_phi_args (edge new_edge, edge old_edge)
3007 {
3008   tree var, phi;
3009
3010   if (!PENDING_STMT (old_edge))
3011     return;
3012
3013   for (var = PENDING_STMT (old_edge), phi = phi_nodes (new_edge->dest);
3014        var && phi;
3015        var = TREE_CHAIN (var), phi = PHI_CHAIN (phi))
3016     {
3017       tree result = TREE_PURPOSE (var);
3018       tree arg = TREE_VALUE (var);
3019
3020       gcc_assert (result == PHI_RESULT (phi));
3021
3022       add_phi_arg (phi, arg, new_edge);
3023     }
3024
3025   PENDING_STMT (old_edge) = NULL;
3026 }
3027
3028 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3029    Abort on abnormal edges.  */
3030
3031 static basic_block
3032 tree_split_edge (edge edge_in)
3033 {
3034   basic_block new_bb, after_bb, dest, src;
3035   edge new_edge, e;
3036
3037   /* Abnormal edges cannot be split.  */
3038   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3039
3040   src = edge_in->src;
3041   dest = edge_in->dest;
3042
3043   /* Place the new block in the block list.  Try to keep the new block
3044      near its "logical" location.  This is of most help to humans looking
3045      at debugging dumps.  */
3046   if (dest->prev_bb && find_edge (dest->prev_bb, dest))
3047     after_bb = edge_in->src;
3048   else
3049     after_bb = dest->prev_bb;
3050
3051   new_bb = create_empty_bb (after_bb);
3052   new_bb->frequency = EDGE_FREQUENCY (edge_in);
3053   new_bb->count = edge_in->count;
3054   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3055   new_edge->probability = REG_BR_PROB_BASE;
3056   new_edge->count = edge_in->count;
3057
3058   e = redirect_edge_and_branch (edge_in, new_bb);
3059   gcc_assert (e);
3060   reinstall_phi_args (new_edge, e);
3061
3062   return new_bb;
3063 }
3064
3065
3066 /* Return true when BB has label LABEL in it.  */
3067
3068 static bool
3069 has_label_p (basic_block bb, tree label)
3070 {
3071   block_stmt_iterator bsi;
3072
3073   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3074     {
3075       tree stmt = bsi_stmt (bsi);
3076
3077       if (TREE_CODE (stmt) != LABEL_EXPR)
3078         return false;
3079       if (LABEL_EXPR_LABEL (stmt) == label)
3080         return true;
3081     }
3082   return false;
3083 }
3084
3085
3086 /* Callback for walk_tree, check that all elements with address taken are
3087    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
3088    inside a PHI node.  */
3089
3090 static tree
3091 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3092 {
3093   tree t = *tp, x;
3094   bool in_phi = (data != NULL);
3095
3096   if (TYPE_P (t))
3097     *walk_subtrees = 0;
3098
3099   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
3100 #define CHECK_OP(N, MSG) \
3101   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
3102        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3103
3104   switch (TREE_CODE (t))
3105     {
3106     case SSA_NAME:
3107       if (SSA_NAME_IN_FREE_LIST (t))
3108         {
3109           error ("SSA name in freelist but still referenced");
3110           return *tp;
3111         }
3112       break;
3113
3114     case ASSERT_EXPR:
3115       x = fold (ASSERT_EXPR_COND (t));
3116       if (x == boolean_false_node)
3117         {
3118           error ("ASSERT_EXPR with an always-false condition");
3119           return *tp;
3120         }
3121       break;
3122
3123     case MODIFY_EXPR:
3124       x = TREE_OPERAND (t, 0);
3125       if (TREE_CODE (x) == BIT_FIELD_REF
3126           && is_gimple_reg (TREE_OPERAND (x, 0)))
3127         {
3128           error ("GIMPLE register modified with BIT_FIELD_REF");
3129           return t;
3130         }
3131       break;
3132
3133     case ADDR_EXPR:
3134       {
3135         bool old_invariant;
3136         bool old_constant;
3137         bool old_side_effects;
3138         bool new_invariant;
3139         bool new_constant;
3140         bool new_side_effects;
3141
3142         /* ??? tree-ssa-alias.c may have overlooked dead PHI nodes, missing
3143            dead PHIs that take the address of something.  But if the PHI
3144            result is dead, the fact that it takes the address of anything
3145            is irrelevant.  Because we can not tell from here if a PHI result
3146            is dead, we just skip this check for PHIs altogether.  This means
3147            we may be missing "valid" checks, but what can you do?
3148            This was PR19217.  */
3149         if (in_phi)
3150           break;
3151
3152         old_invariant = TREE_INVARIANT (t);
3153         old_constant = TREE_CONSTANT (t);
3154         old_side_effects = TREE_SIDE_EFFECTS (t);
3155
3156         recompute_tree_invarant_for_addr_expr (t);
3157         new_invariant = TREE_INVARIANT (t);
3158         new_side_effects = TREE_SIDE_EFFECTS (t);
3159         new_constant = TREE_CONSTANT (t);
3160
3161         if (old_invariant != new_invariant)
3162           {
3163             error ("invariant not recomputed when ADDR_EXPR changed");
3164             return t;
3165           }
3166
3167         if (old_constant != new_constant)
3168           {
3169             error ("constant not recomputed when ADDR_EXPR changed");
3170             return t;
3171           }
3172         if (old_side_effects != new_side_effects)
3173           {
3174             error ("side effects not recomputed when ADDR_EXPR changed");
3175             return t;
3176           }
3177
3178         /* Skip any references (they will be checked when we recurse down the
3179            tree) and ensure that any variable used as a prefix is marked
3180            addressable.  */
3181         for (x = TREE_OPERAND (t, 0);
3182              handled_component_p (x);
3183              x = TREE_OPERAND (x, 0))
3184           ;
3185
3186         if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3187           return NULL;
3188         if (!TREE_ADDRESSABLE (x))
3189           {
3190             error ("address taken, but ADDRESSABLE bit not set");
3191             return x;
3192           }
3193         break;
3194       }
3195
3196     case COND_EXPR:
3197       x = COND_EXPR_COND (t);
3198       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3199         {
3200           error ("non-boolean used in condition");
3201           return x;
3202         }
3203       if (!is_gimple_condexpr (x))
3204         {
3205           error ("invalid conditional operand");
3206           return x;
3207         }
3208       break;
3209
3210     case NOP_EXPR:
3211     case CONVERT_EXPR:
3212     case FIX_TRUNC_EXPR:
3213     case FIX_CEIL_EXPR:
3214     case FIX_FLOOR_EXPR:
3215     case FIX_ROUND_EXPR:
3216     case FLOAT_EXPR:
3217     case NEGATE_EXPR:
3218     case ABS_EXPR:
3219     case BIT_NOT_EXPR:
3220     case NON_LVALUE_EXPR:
3221     case TRUTH_NOT_EXPR:
3222       CHECK_OP (0, "invalid operand to unary operator");
3223       break;
3224
3225     case REALPART_EXPR:
3226     case IMAGPART_EXPR:
3227     case COMPONENT_REF:
3228     case ARRAY_REF:
3229     case ARRAY_RANGE_REF:
3230     case BIT_FIELD_REF:
3231     case VIEW_CONVERT_EXPR:
3232       /* We have a nest of references.  Verify that each of the operands
3233          that determine where to reference is either a constant or a variable,
3234          verify that the base is valid, and then show we've already checked
3235          the subtrees.  */
3236       while (handled_component_p (t))
3237         {
3238           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3239             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
3240           else if (TREE_CODE (t) == ARRAY_REF
3241                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3242             {
3243               CHECK_OP (1, "invalid array index");
3244               if (TREE_OPERAND (t, 2))
3245                 CHECK_OP (2, "invalid array lower bound");
3246               if (TREE_OPERAND (t, 3))
3247                 CHECK_OP (3, "invalid array stride");
3248             }
3249           else if (TREE_CODE (t) == BIT_FIELD_REF)
3250             {
3251               CHECK_OP (1, "invalid operand to BIT_FIELD_REF");
3252               CHECK_OP (2, "invalid operand to BIT_FIELD_REF");
3253             }
3254
3255           t = TREE_OPERAND (t, 0);
3256         }
3257
3258       if (!CONSTANT_CLASS_P (t) && !is_gimple_lvalue (t))
3259         {
3260           error ("invalid reference prefix");
3261           return t;
3262         }
3263       *walk_subtrees = 0;
3264       break;
3265
3266     case LT_EXPR:
3267     case LE_EXPR:
3268     case GT_EXPR:
3269     case GE_EXPR:
3270     case EQ_EXPR:
3271     case NE_EXPR:
3272     case UNORDERED_EXPR:
3273     case ORDERED_EXPR:
3274     case UNLT_EXPR:
3275     case UNLE_EXPR:
3276     case UNGT_EXPR:
3277     case UNGE_EXPR:
3278     case UNEQ_EXPR:
3279     case LTGT_EXPR:
3280     case PLUS_EXPR:
3281     case MINUS_EXPR:
3282     case MULT_EXPR:
3283     case TRUNC_DIV_EXPR:
3284     case CEIL_DIV_EXPR:
3285     case FLOOR_DIV_EXPR:
3286     case ROUND_DIV_EXPR:
3287     case TRUNC_MOD_EXPR:
3288     case CEIL_MOD_EXPR:
3289     case FLOOR_MOD_EXPR:
3290     case ROUND_MOD_EXPR:
3291     case RDIV_EXPR:
3292     case EXACT_DIV_EXPR:
3293     case MIN_EXPR:
3294     case MAX_EXPR:
3295     case LSHIFT_EXPR:
3296     case RSHIFT_EXPR:
3297     case LROTATE_EXPR:
3298     case RROTATE_EXPR:
3299     case BIT_IOR_EXPR:
3300     case BIT_XOR_EXPR:
3301     case BIT_AND_EXPR:
3302       CHECK_OP (0, "invalid operand to binary operator");
3303       CHECK_OP (1, "invalid operand to binary operator");
3304       break;
3305
3306     default:
3307       break;
3308     }
3309   return NULL;
3310
3311 #undef CHECK_OP
3312 }
3313
3314
3315 /* Verify STMT, return true if STMT is not in GIMPLE form.
3316    TODO: Implement type checking.  */
3317
3318 static bool
3319 verify_stmt (tree stmt, bool last_in_block)
3320 {
3321   tree addr;
3322
3323   if (!is_gimple_stmt (stmt))
3324     {
3325       error ("is not a valid GIMPLE statement");
3326       goto fail;
3327     }
3328
3329   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3330   if (addr)
3331     {
3332       debug_generic_stmt (addr);
3333       return true;
3334     }
3335
3336   /* If the statement is marked as part of an EH region, then it is
3337      expected that the statement could throw.  Verify that when we
3338      have optimizations that simplify statements such that we prove
3339      that they cannot throw, that we update other data structures
3340      to match.  */
3341   if (lookup_stmt_eh_region (stmt) >= 0)
3342     {
3343       if (!tree_could_throw_p (stmt))
3344         {
3345           error ("statement marked for throw, but doesn%'t");
3346           goto fail;
3347         }
3348       if (!last_in_block && tree_can_throw_internal (stmt))
3349         {
3350           error ("statement marked for throw in middle of block");
3351           goto fail;
3352         }
3353     }
3354
3355   return false;
3356
3357  fail:
3358   debug_generic_stmt (stmt);
3359   return true;
3360 }
3361
3362
3363 /* Return true when the T can be shared.  */
3364
3365 static bool
3366 tree_node_can_be_shared (tree t)
3367 {
3368   if (IS_TYPE_OR_DECL_P (t)
3369       /* We check for constants explicitly since they are not considered
3370          gimple invariants if they overflowed.  */
3371       || CONSTANT_CLASS_P (t)
3372       || is_gimple_min_invariant (t)
3373       || TREE_CODE (t) == SSA_NAME
3374       || t == error_mark_node)
3375     return true;
3376
3377   if (TREE_CODE (t) == CASE_LABEL_EXPR)
3378     return true;
3379
3380   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3381           /* We check for constants explicitly since they are not considered
3382              gimple invariants if they overflowed.  */
3383           && (CONSTANT_CLASS_P (TREE_OPERAND (t, 1))
3384               || is_gimple_min_invariant (TREE_OPERAND (t, 1))))
3385          || (TREE_CODE (t) == COMPONENT_REF
3386              || TREE_CODE (t) == REALPART_EXPR
3387              || TREE_CODE (t) == IMAGPART_EXPR))
3388     t = TREE_OPERAND (t, 0);
3389
3390   if (DECL_P (t))
3391     return true;
3392
3393   return false;
3394 }
3395
3396
3397 /* Called via walk_trees.  Verify tree sharing.  */
3398
3399 static tree
3400 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3401 {
3402   htab_t htab = (htab_t) data;
3403   void **slot;
3404
3405   if (tree_node_can_be_shared (*tp))
3406     {
3407       *walk_subtrees = false;
3408       return NULL;
3409     }
3410
3411   slot = htab_find_slot (htab, *tp, INSERT);
3412   if (*slot)
3413     return *slot;
3414   *slot = *tp;
3415
3416   return NULL;
3417 }
3418
3419
3420 /* Verify the GIMPLE statement chain.  */
3421
3422 void
3423 verify_stmts (void)
3424 {
3425   basic_block bb;
3426   block_stmt_iterator bsi;
3427   bool err = false;
3428   htab_t htab;
3429   tree addr;
3430
3431   timevar_push (TV_TREE_STMT_VERIFY);
3432   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3433
3434   FOR_EACH_BB (bb)
3435     {
3436       tree phi;
3437       int i;
3438
3439       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3440         {
3441           int phi_num_args = PHI_NUM_ARGS (phi);
3442
3443           if (bb_for_stmt (phi) != bb)
3444             {
3445               error ("bb_for_stmt (phi) is set to a wrong basic block");
3446               err |= true;
3447             }
3448
3449           for (i = 0; i < phi_num_args; i++)
3450             {
3451               tree t = PHI_ARG_DEF (phi, i);
3452               tree addr;
3453
3454               /* Addressable variables do have SSA_NAMEs but they
3455                  are not considered gimple values.  */
3456               if (TREE_CODE (t) != SSA_NAME
3457                   && TREE_CODE (t) != FUNCTION_DECL
3458                   && !is_gimple_val (t))
3459                 {
3460                   error ("PHI def is not a GIMPLE value");
3461                   debug_generic_stmt (phi);
3462                   debug_generic_stmt (t);
3463                   err |= true;
3464                 }
3465
3466               addr = walk_tree (&t, verify_expr, (void *) 1, NULL);
3467               if (addr)
3468                 {
3469                   debug_generic_stmt (addr);
3470                   err |= true;
3471                 }
3472
3473               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3474               if (addr)
3475                 {
3476                   error ("incorrect sharing of tree nodes");
3477                   debug_generic_stmt (phi);
3478                   debug_generic_stmt (addr);
3479                   err |= true;
3480                 }
3481             }
3482         }
3483
3484       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3485         {
3486           tree stmt = bsi_stmt (bsi);
3487
3488           if (bb_for_stmt (stmt) != bb)
3489             {
3490               error ("bb_for_stmt (stmt) is set to a wrong basic block");
3491               err |= true;
3492             }
3493
3494           bsi_next (&bsi);
3495           err |= verify_stmt (stmt, bsi_end_p (bsi));
3496           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3497           if (addr)
3498             {
3499               error ("incorrect sharing of tree nodes");
3500               debug_generic_stmt (stmt);
3501               debug_generic_stmt (addr);
3502               err |= true;
3503             }
3504         }
3505     }
3506
3507   if (err)
3508     internal_error ("verify_stmts failed");
3509
3510   htab_delete (htab);
3511   timevar_pop (TV_TREE_STMT_VERIFY);
3512 }
3513
3514
3515 /* Verifies that the flow information is OK.  */
3516
3517 static int
3518 tree_verify_flow_info (void)
3519 {
3520   int err = 0;
3521   basic_block bb;
3522   block_stmt_iterator bsi;
3523   tree stmt;
3524   edge e;
3525   edge_iterator ei;
3526
3527   if (ENTRY_BLOCK_PTR->stmt_list)
3528     {
3529       error ("ENTRY_BLOCK has a statement list associated with it");
3530       err = 1;
3531     }
3532
3533   if (EXIT_BLOCK_PTR->stmt_list)
3534     {
3535       error ("EXIT_BLOCK has a statement list associated with it");
3536       err = 1;
3537     }
3538
3539   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
3540     if (e->flags & EDGE_FALLTHRU)
3541       {
3542         error ("fallthru to exit from bb %d", e->src->index);
3543         err = 1;
3544       }
3545
3546   FOR_EACH_BB (bb)
3547     {
3548       bool found_ctrl_stmt = false;
3549
3550       stmt = NULL_TREE;
3551
3552       /* Skip labels on the start of basic block.  */
3553       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3554         {
3555           tree prev_stmt = stmt;
3556
3557           stmt = bsi_stmt (bsi);
3558
3559           if (TREE_CODE (stmt) != LABEL_EXPR)
3560             break;
3561
3562           if (prev_stmt && DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3563             {
3564               error ("nonlocal label %s is not first "
3565                      "in a sequence of labels in bb %d",
3566                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3567                      bb->index);
3568               err = 1;
3569             }
3570
3571           if (label_to_block (LABEL_EXPR_LABEL (stmt)) != bb)
3572             {
3573               error ("label %s to block does not match in bb %d",
3574                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3575                      bb->index);
3576               err = 1;
3577             }
3578
3579           if (decl_function_context (LABEL_EXPR_LABEL (stmt))
3580               != current_function_decl)
3581             {
3582               error ("label %s has incorrect context in bb %d",
3583                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3584                      bb->index);
3585               err = 1;
3586             }
3587         }
3588
3589       /* Verify that body of basic block BB is free of control flow.  */
3590       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3591         {
3592           tree stmt = bsi_stmt (bsi);
3593
3594           if (found_ctrl_stmt)
3595             {
3596               error ("control flow in the middle of basic block %d",
3597                      bb->index);
3598               err = 1;
3599             }
3600
3601           if (stmt_ends_bb_p (stmt))
3602             found_ctrl_stmt = true;
3603
3604           if (TREE_CODE (stmt) == LABEL_EXPR)
3605             {
3606               error ("label %s in the middle of basic block %d",
3607                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3608                      bb->index);
3609               err = 1;
3610             }
3611         }
3612       bsi = bsi_last (bb);
3613       if (bsi_end_p (bsi))
3614         continue;
3615
3616       stmt = bsi_stmt (bsi);
3617
3618       err |= verify_eh_edges (stmt);
3619
3620       if (is_ctrl_stmt (stmt))
3621         {
3622           FOR_EACH_EDGE (e, ei, bb->succs)
3623             if (e->flags & EDGE_FALLTHRU)
3624               {
3625                 error ("fallthru edge after a control statement in bb %d",
3626                        bb->index);
3627                 err = 1;
3628               }
3629         }
3630
3631       switch (TREE_CODE (stmt))
3632         {
3633         case COND_EXPR:
3634           {
3635             edge true_edge;
3636             edge false_edge;
3637             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3638                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3639               {
3640                 error ("structured COND_EXPR at the end of bb %d", bb->index);
3641                 err = 1;
3642               }
3643
3644             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3645
3646             if (!true_edge || !false_edge
3647                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3648                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3649                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3650                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3651                 || EDGE_COUNT (bb->succs) >= 3)
3652               {
3653                 error ("wrong outgoing edge flags at end of bb %d",
3654                        bb->index);
3655                 err = 1;
3656               }
3657
3658             if (!has_label_p (true_edge->dest,
3659                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3660               {
3661                 error ("%<then%> label does not match edge at end of bb %d",
3662                        bb->index);
3663                 err = 1;
3664               }
3665
3666             if (!has_label_p (false_edge->dest,
3667                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3668               {
3669                 error ("%<else%> label does not match edge at end of bb %d",
3670                        bb->index);
3671                 err = 1;
3672               }
3673           }
3674           break;
3675
3676         case GOTO_EXPR:
3677           if (simple_goto_p (stmt))
3678             {
3679               error ("explicit goto at end of bb %d", bb->index);
3680               err = 1;
3681             }
3682           else
3683             {
3684               /* FIXME.  We should double check that the labels in the
3685                  destination blocks have their address taken.  */
3686               FOR_EACH_EDGE (e, ei, bb->succs)
3687                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3688                                  | EDGE_FALSE_VALUE))
3689                     || !(e->flags & EDGE_ABNORMAL))
3690                   {
3691                     error ("wrong outgoing edge flags at end of bb %d",
3692                            bb->index);
3693                     err = 1;
3694                   }
3695             }
3696           break;
3697
3698         case RETURN_EXPR:
3699           if (!single_succ_p (bb)
3700               || (single_succ_edge (bb)->flags
3701                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
3702                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3703             {
3704               error ("wrong outgoing edge flags at end of bb %d", bb->index);
3705               err = 1;
3706             }
3707           if (single_succ (bb) != EXIT_BLOCK_PTR)
3708             {
3709               error ("return edge does not point to exit in bb %d",
3710                      bb->index);
3711               err = 1;
3712             }
3713           break;
3714
3715         case SWITCH_EXPR:
3716           {
3717             tree prev;
3718             edge e;
3719             size_t i, n;
3720             tree vec;
3721
3722             vec = SWITCH_LABELS (stmt);
3723             n = TREE_VEC_LENGTH (vec);
3724
3725             /* Mark all the destination basic blocks.  */
3726             for (i = 0; i < n; ++i)
3727               {
3728                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3729                 basic_block label_bb = label_to_block (lab);
3730
3731                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
3732                 label_bb->aux = (void *)1;
3733               }
3734
3735             /* Verify that the case labels are sorted.  */
3736             prev = TREE_VEC_ELT (vec, 0);
3737             for (i = 1; i < n - 1; ++i)
3738               {
3739                 tree c = TREE_VEC_ELT (vec, i);
3740                 if (! CASE_LOW (c))
3741                   {
3742                     error ("found default case not at end of case vector");
3743                     err = 1;
3744                     continue;
3745                   }
3746                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
3747                   {
3748                     error ("case labels not sorted:");
3749                     print_generic_expr (stderr, prev, 0);
3750                     fprintf (stderr," is greater than ");
3751                     print_generic_expr (stderr, c, 0);
3752                     fprintf (stderr," but comes before it.\n");
3753                     err = 1;
3754                   }
3755                 prev = c;
3756               }
3757             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
3758               {
3759                 error ("no default case found at end of case vector");
3760                 err = 1;
3761               }
3762
3763             FOR_EACH_EDGE (e, ei, bb->succs)
3764               {
3765                 if (!e->dest->aux)
3766                   {
3767                     error ("extra outgoing edge %d->%d",
3768                            bb->index, e->dest->index);
3769                     err = 1;
3770                   }
3771                 e->dest->aux = (void *)2;
3772                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3773                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3774                   {
3775                     error ("wrong outgoing edge flags at end of bb %d",
3776                            bb->index);
3777                     err = 1;
3778                   }
3779               }
3780
3781             /* Check that we have all of them.  */
3782             for (i = 0; i < n; ++i)
3783               {
3784                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3785                 basic_block label_bb = label_to_block (lab);
3786
3787                 if (label_bb->aux != (void *)2)
3788                   {
3789                     error ("missing edge %i->%i",
3790                            bb->index, label_bb->index);
3791                     err = 1;
3792                   }
3793               }
3794
3795             FOR_EACH_EDGE (e, ei, bb->succs)
3796               e->dest->aux = (void *)0;
3797           }
3798
3799         default: ;
3800         }
3801     }
3802
3803   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
3804     verify_dominators (CDI_DOMINATORS);
3805
3806   return err;
3807 }
3808
3809
3810 /* Updates phi nodes after creating a forwarder block joined
3811    by edge FALLTHRU.  */
3812
3813 static void
3814 tree_make_forwarder_block (edge fallthru)
3815 {
3816   edge e;
3817   edge_iterator ei;
3818   basic_block dummy, bb;
3819   tree phi, new_phi, var;
3820
3821   dummy = fallthru->src;
3822   bb = fallthru->dest;
3823
3824   if (single_pred_p (bb))
3825     return;
3826
3827   /* If we redirected a branch we must create new phi nodes at the
3828      start of BB.  */
3829   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
3830     {
3831       var = PHI_RESULT (phi);
3832       new_phi = create_phi_node (var, bb);
3833       SSA_NAME_DEF_STMT (var) = new_phi;
3834       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
3835       add_phi_arg (new_phi, PHI_RESULT (phi), fallthru);
3836     }
3837
3838   /* Ensure that the PHI node chain is in the same order.  */
3839   set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
3840
3841   /* Add the arguments we have stored on edges.  */
3842   FOR_EACH_EDGE (e, ei, bb->preds)
3843     {
3844       if (e == fallthru)
3845         continue;
3846
3847       flush_pending_stmts (e);
3848     }
3849 }
3850
3851
3852 /* Return a non-special label in the head of basic block BLOCK.
3853    Create one if it doesn't exist.  */
3854
3855 tree
3856 tree_block_label (basic_block bb)
3857 {
3858   block_stmt_iterator i, s = bsi_start (bb);
3859   bool first = true;
3860   tree label, stmt;
3861
3862   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
3863     {
3864       stmt = bsi_stmt (i);
3865       if (TREE_CODE (stmt) != LABEL_EXPR)
3866         break;
3867       label = LABEL_EXPR_LABEL (stmt);
3868       if (!DECL_NONLOCAL (label))
3869         {
3870           if (!first)
3871             bsi_move_before (&i, &s);
3872           return label;
3873         }
3874     }
3875
3876   label = create_artificial_label ();
3877   stmt = build1 (LABEL_EXPR, void_type_node, label);
3878   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
3879   return label;
3880 }
3881
3882
3883 /* Attempt to perform edge redirection by replacing a possibly complex
3884    jump instruction by a goto or by removing the jump completely.
3885    This can apply only if all edges now point to the same block.  The
3886    parameters and return values are equivalent to
3887    redirect_edge_and_branch.  */
3888
3889 static edge
3890 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
3891 {
3892   basic_block src = e->src;
3893   block_stmt_iterator b;
3894   tree stmt;
3895
3896   /* We can replace or remove a complex jump only when we have exactly
3897      two edges.  */
3898   if (EDGE_COUNT (src->succs) != 2
3899       /* Verify that all targets will be TARGET.  Specifically, the
3900          edge that is not E must also go to TARGET.  */
3901       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
3902     return NULL;
3903
3904   b = bsi_last (src);
3905   if (bsi_end_p (b))
3906     return NULL;
3907   stmt = bsi_stmt (b);
3908
3909   if (TREE_CODE (stmt) == COND_EXPR
3910       || TREE_CODE (stmt) == SWITCH_EXPR)
3911     {
3912       bsi_remove (&b);
3913       e = ssa_redirect_edge (e, target);
3914       e->flags = EDGE_FALLTHRU;
3915       return e;
3916     }
3917
3918   return NULL;
3919 }
3920
3921
3922 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
3923    edge representing the redirected branch.  */
3924
3925 static edge
3926 tree_redirect_edge_and_branch (edge e, basic_block dest)
3927 {
3928   basic_block bb = e->src;
3929   block_stmt_iterator bsi;
3930   edge ret;
3931   tree label, stmt;
3932
3933   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
3934     return NULL;
3935
3936   if (e->src != ENTRY_BLOCK_PTR
3937       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
3938     return ret;
3939
3940   if (e->dest == dest)
3941     return NULL;
3942
3943   label = tree_block_label (dest);
3944
3945   bsi = bsi_last (bb);
3946   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
3947
3948   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
3949     {
3950     case COND_EXPR:
3951       stmt = (e->flags & EDGE_TRUE_VALUE
3952               ? COND_EXPR_THEN (stmt)
3953               : COND_EXPR_ELSE (stmt));
3954       GOTO_DESTINATION (stmt) = label;
3955       break;
3956
3957     case GOTO_EXPR:
3958       /* No non-abnormal edges should lead from a non-simple goto, and
3959          simple ones should be represented implicitly.  */
3960       gcc_unreachable ();
3961
3962     case SWITCH_EXPR:
3963       {
3964         tree cases = get_cases_for_edge (e, stmt);
3965
3966         /* If we have a list of cases associated with E, then use it
3967            as it's a lot faster than walking the entire case vector.  */
3968         if (cases)
3969           {
3970             edge e2 = find_edge (e->src, dest);
3971             tree last, first;
3972
3973             first = cases;
3974             while (cases)
3975               {
3976                 last = cases;
3977                 CASE_LABEL (cases) = label;
3978                 cases = TREE_CHAIN (cases);
3979               }
3980
3981             /* If there was already an edge in the CFG, then we need
3982                to move all the cases associated with E to E2.  */
3983             if (e2)
3984               {
3985                 tree cases2 = get_cases_for_edge (e2, stmt);
3986
3987                 TREE_CHAIN (last) = TREE_CHAIN (cases2);
3988                 TREE_CHAIN (cases2) = first;
3989               }
3990           }
3991         else
3992           {
3993             tree vec = SWITCH_LABELS (stmt);
3994             size_t i, n = TREE_VEC_LENGTH (vec);
3995
3996             for (i = 0; i < n; i++)
3997               {
3998                 tree elt = TREE_VEC_ELT (vec, i);
3999
4000                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
4001                   CASE_LABEL (elt) = label;
4002               }
4003           }
4004
4005         break;
4006       }
4007
4008     case RETURN_EXPR:
4009       bsi_remove (&bsi);
4010       e->flags |= EDGE_FALLTHRU;
4011       break;
4012
4013     default:
4014       /* Otherwise it must be a fallthru edge, and we don't need to
4015          do anything besides redirecting it.  */
4016       gcc_assert (e->flags & EDGE_FALLTHRU);
4017       break;
4018     }
4019
4020   /* Update/insert PHI nodes as necessary.  */
4021
4022   /* Now update the edges in the CFG.  */
4023   e = ssa_redirect_edge (e, dest);
4024
4025   return e;
4026 }
4027
4028
4029 /* Simple wrapper, as we can always redirect fallthru edges.  */
4030
4031 static basic_block
4032 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4033 {
4034   e = tree_redirect_edge_and_branch (e, dest);
4035   gcc_assert (e);
4036
4037   return NULL;
4038 }
4039
4040
4041 /* Splits basic block BB after statement STMT (but at least after the
4042    labels).  If STMT is NULL, BB is split just after the labels.  */
4043
4044 static basic_block
4045 tree_split_block (basic_block bb, void *stmt)
4046 {
4047   block_stmt_iterator bsi, bsi_tgt;
4048   tree act;
4049   basic_block new_bb;
4050   edge e;
4051   edge_iterator ei;
4052
4053   new_bb = create_empty_bb (bb);
4054
4055   /* Redirect the outgoing edges.  */
4056   new_bb->succs = bb->succs;
4057   bb->succs = NULL;
4058   FOR_EACH_EDGE (e, ei, new_bb->succs)
4059     e->src = new_bb;
4060
4061   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4062     stmt = NULL;
4063
4064   /* Move everything from BSI to the new basic block.  */
4065   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4066     {
4067       act = bsi_stmt (bsi);
4068       if (TREE_CODE (act) == LABEL_EXPR)
4069         continue;
4070
4071       if (!stmt)
4072         break;
4073
4074       if (stmt == act)
4075         {
4076           bsi_next (&bsi);
4077           break;
4078         }
4079     }
4080
4081   bsi_tgt = bsi_start (new_bb);
4082   while (!bsi_end_p (bsi))
4083     {
4084       act = bsi_stmt (bsi);
4085       bsi_remove (&bsi);
4086       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
4087     }
4088
4089   return new_bb;
4090 }
4091
4092
4093 /* Moves basic block BB after block AFTER.  */
4094
4095 static bool
4096 tree_move_block_after (basic_block bb, basic_block after)
4097 {
4098   if (bb->prev_bb == after)
4099     return true;
4100
4101   unlink_block (bb);
4102   link_block (bb, after);
4103
4104   return true;
4105 }
4106
4107
4108 /* Return true if basic_block can be duplicated.  */
4109
4110 static bool
4111 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4112 {
4113   return true;
4114 }
4115
4116
4117 /* Create a duplicate of the basic block BB.  NOTE: This does not
4118    preserve SSA form.  */
4119
4120 static basic_block
4121 tree_duplicate_bb (basic_block bb)
4122 {
4123   basic_block new_bb;
4124   block_stmt_iterator bsi, bsi_tgt;
4125   tree phi;
4126
4127   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4128
4129   /* Copy the PHI nodes.  We ignore PHI node arguments here because
4130      the incoming edges have not been setup yet.  */
4131   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4132     {
4133       tree copy = create_phi_node (PHI_RESULT (phi), new_bb);
4134       create_new_def_for (PHI_RESULT (copy), copy, PHI_RESULT_PTR (copy));
4135     }
4136
4137   /* Keep the chain of PHI nodes in the same order so that they can be
4138      updated by ssa_redirect_edge.  */
4139   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
4140
4141   bsi_tgt = bsi_start (new_bb);
4142   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4143     {
4144       def_operand_p def_p;
4145       ssa_op_iter op_iter;
4146       tree stmt, copy;
4147       int region;
4148
4149       stmt = bsi_stmt (bsi);
4150       if (TREE_CODE (stmt) == LABEL_EXPR)
4151         continue;
4152
4153       /* Create a new copy of STMT and duplicate STMT's virtual
4154          operands.  */
4155       copy = unshare_expr (stmt);
4156       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4157       copy_virtual_operands (copy, stmt);
4158       region = lookup_stmt_eh_region (stmt);
4159       if (region >= 0)
4160         add_stmt_to_eh_region (copy, region);
4161
4162       /* Create new names for all the definitions created by COPY and
4163          add replacement mappings for each new name.  */
4164       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
4165         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
4166     }
4167
4168   return new_bb;
4169 }
4170
4171
4172 /* Basic block BB_COPY was created by code duplication.  Add phi node
4173    arguments for edges going out of BB_COPY.  The blocks that were
4174    duplicated have BB_DUPLICATED set.  */
4175
4176 void
4177 add_phi_args_after_copy_bb (basic_block bb_copy)
4178 {
4179   basic_block bb, dest;
4180   edge e, e_copy;
4181   edge_iterator ei;
4182   tree phi, phi_copy, phi_next, def;
4183
4184   bb = get_bb_original (bb_copy);
4185
4186   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
4187     {
4188       if (!phi_nodes (e_copy->dest))
4189         continue;
4190
4191       if (e_copy->dest->flags & BB_DUPLICATED)
4192         dest = get_bb_original (e_copy->dest);
4193       else
4194         dest = e_copy->dest;
4195
4196       e = find_edge (bb, dest);
4197       if (!e)
4198         {
4199           /* During loop unrolling the target of the latch edge is copied.
4200              In this case we are not looking for edge to dest, but to
4201              duplicated block whose original was dest.  */
4202           FOR_EACH_EDGE (e, ei, bb->succs)
4203             if ((e->dest->flags & BB_DUPLICATED)
4204                 && get_bb_original (e->dest) == dest)
4205               break;
4206
4207           gcc_assert (e != NULL);
4208         }
4209
4210       for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
4211            phi;
4212            phi = phi_next, phi_copy = PHI_CHAIN (phi_copy))
4213         {
4214           phi_next = PHI_CHAIN (phi);
4215           def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4216           add_phi_arg (phi_copy, def, e_copy);
4217         }
4218     }
4219 }
4220
4221 /* Blocks in REGION_COPY array of length N_REGION were created by
4222    duplication of basic blocks.  Add phi node arguments for edges
4223    going from these blocks.  */
4224
4225 void
4226 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
4227 {
4228   unsigned i;
4229
4230   for (i = 0; i < n_region; i++)
4231     region_copy[i]->flags |= BB_DUPLICATED;
4232
4233   for (i = 0; i < n_region; i++)
4234     add_phi_args_after_copy_bb (region_copy[i]);
4235
4236   for (i = 0; i < n_region; i++)
4237     region_copy[i]->flags &= ~BB_DUPLICATED;
4238 }
4239
4240 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
4241    important exit edge EXIT.  By important we mean that no SSA name defined
4242    inside region is live over the other exit edges of the region.  All entry
4243    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
4244    to the duplicate of the region.  SSA form, dominance and loop information
4245    is updated.  The new basic blocks are stored to REGION_COPY in the same
4246    order as they had in REGION, provided that REGION_COPY is not NULL.
4247    The function returns false if it is unable to copy the region,
4248    true otherwise.  */
4249
4250 bool
4251 tree_duplicate_sese_region (edge entry, edge exit,
4252                             basic_block *region, unsigned n_region,
4253                             basic_block *region_copy)
4254 {
4255   unsigned i, n_doms;
4256   bool free_region_copy = false, copying_header = false;
4257   struct loop *loop = entry->dest->loop_father;
4258   edge exit_copy;
4259   basic_block *doms;
4260   edge redirected;
4261   int total_freq = 0, entry_freq = 0;
4262   gcov_type total_count = 0, entry_count = 0;
4263
4264   if (!can_copy_bbs_p (region, n_region))
4265     return false;
4266
4267   /* Some sanity checking.  Note that we do not check for all possible
4268      missuses of the functions.  I.e. if you ask to copy something weird,
4269      it will work, but the state of structures probably will not be
4270      correct.  */
4271   for (i = 0; i < n_region; i++)
4272     {
4273       /* We do not handle subloops, i.e. all the blocks must belong to the
4274          same loop.  */
4275       if (region[i]->loop_father != loop)
4276         return false;
4277
4278       if (region[i] != entry->dest
4279           && region[i] == loop->header)
4280         return false;
4281     }
4282
4283   loop->copy = loop;
4284
4285   /* In case the function is used for loop header copying (which is the primary
4286      use), ensure that EXIT and its copy will be new latch and entry edges.  */
4287   if (loop->header == entry->dest)
4288     {
4289       copying_header = true;
4290       loop->copy = loop->outer;
4291
4292       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
4293         return false;
4294
4295       for (i = 0; i < n_region; i++)
4296         if (region[i] != exit->src
4297             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
4298           return false;
4299     }
4300
4301   if (!region_copy)
4302     {
4303       region_copy = xmalloc (sizeof (basic_block) * n_region);
4304       free_region_copy = true;
4305     }
4306
4307   gcc_assert (!need_ssa_update_p ());
4308
4309   /* Record blocks outside the region that are dominated by something
4310      inside.  */
4311   doms = xmalloc (sizeof (basic_block) * n_basic_blocks);
4312   initialize_original_copy_tables ();
4313
4314   n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
4315
4316   if (entry->dest->count)
4317     {
4318       total_count = entry->dest->count;
4319       entry_count = entry->count;
4320       /* Fix up corner cases, to avoid division by zero or creation of negative
4321          frequencies.  */
4322       if (entry_count > total_count)
4323         entry_count = total_count;
4324     }
4325   else
4326     {
4327       total_freq = entry->dest->frequency;
4328       entry_freq = EDGE_FREQUENCY (entry);
4329       /* Fix up corner cases, to avoid division by zero or creation of negative
4330          frequencies.  */
4331       if (total_freq == 0)
4332         total_freq = 1;
4333       else if (entry_freq > total_freq)
4334         entry_freq = total_freq;
4335     }
4336
4337   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
4338   if (total_count)
4339     {
4340       scale_bbs_frequencies_gcov_type (region, n_region,
4341                                        total_count - entry_count,
4342                                        total_count);
4343       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
4344                                        total_count);
4345     }
4346   else
4347     {
4348       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
4349                                  total_freq);
4350       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
4351     }
4352
4353   if (copying_header)
4354     {
4355       loop->header = exit->dest;
4356       loop->latch = exit->src;
4357     }
4358
4359   /* Redirect the entry and add the phi node arguments.  */
4360   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
4361   gcc_assert (redirected != NULL);
4362   flush_pending_stmts (entry);
4363
4364   /* Concerning updating of dominators:  We must recount dominators
4365      for entry block and its copy.  Anything that is outside of the
4366      region, but was dominated by something inside needs recounting as
4367      well.  */
4368   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
4369   doms[n_doms++] = get_bb_original (entry->dest);
4370   iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
4371   free (doms);
4372
4373   /* Add the other PHI node arguments.  */
4374   add_phi_args_after_copy (region_copy, n_region);
4375
4376   /* Update the SSA web.  */
4377   update_ssa (TODO_update_ssa);
4378
4379   if (free_region_copy)
4380     free (region_copy);
4381
4382   free_original_copy_tables ();
4383   return true;
4384 }
4385
4386
4387 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4388
4389 void
4390 dump_function_to_file (tree fn, FILE *file, int flags)
4391 {
4392   tree arg, vars, var;
4393   bool ignore_topmost_bind = false, any_var = false;
4394   basic_block bb;
4395   tree chain;
4396
4397   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4398
4399   arg = DECL_ARGUMENTS (fn);
4400   while (arg)
4401     {
4402       print_generic_expr (file, arg, dump_flags);
4403       if (TREE_CHAIN (arg))
4404         fprintf (file, ", ");
4405       arg = TREE_CHAIN (arg);
4406     }
4407   fprintf (file, ")\n");
4408
4409   if (flags & TDF_DETAILS)
4410     dump_eh_tree (file, DECL_STRUCT_FUNCTION (fn));
4411   if (flags & TDF_RAW)
4412     {
4413       dump_node (fn, TDF_SLIM | flags, file);
4414       return;
4415     }
4416
4417   /* When GIMPLE is lowered, the variables are no longer available in
4418      BIND_EXPRs, so display them separately.  */
4419   if (cfun && cfun->decl == fn && cfun->unexpanded_var_list)
4420     {
4421       ignore_topmost_bind = true;
4422
4423       fprintf (file, "{\n");
4424       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
4425         {
4426           var = TREE_VALUE (vars);
4427
4428           print_generic_decl (file, var, flags);
4429           fprintf (file, "\n");
4430
4431           any_var = true;
4432         }
4433     }
4434
4435   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
4436     {
4437       /* Make a CFG based dump.  */
4438       check_bb_profile (ENTRY_BLOCK_PTR, file);
4439       if (!ignore_topmost_bind)
4440         fprintf (file, "{\n");
4441
4442       if (any_var && n_basic_blocks)
4443         fprintf (file, "\n");
4444
4445       FOR_EACH_BB (bb)
4446         dump_generic_bb (file, bb, 2, flags);
4447
4448       fprintf (file, "}\n");
4449       check_bb_profile (EXIT_BLOCK_PTR, file);
4450     }
4451   else
4452     {
4453       int indent;
4454
4455       /* Make a tree based dump.  */
4456       chain = DECL_SAVED_TREE (fn);
4457
4458       if (TREE_CODE (chain) == BIND_EXPR)
4459         {
4460           if (ignore_topmost_bind)
4461             {
4462               chain = BIND_EXPR_BODY (chain);
4463               indent = 2;
4464             }
4465           else
4466             indent = 0;
4467         }
4468       else
4469         {
4470           if (!ignore_topmost_bind)
4471             fprintf (file, "{\n");
4472           indent = 2;
4473         }
4474
4475       if (any_var)
4476         fprintf (file, "\n");
4477
4478       print_generic_stmt_indented (file, chain, flags, indent);
4479       if (ignore_topmost_bind)
4480         fprintf (file, "}\n");
4481     }
4482
4483   fprintf (file, "\n\n");
4484 }
4485
4486
4487 /* Pretty print of the loops intermediate representation.  */
4488 static void print_loop (FILE *, struct loop *, int);
4489 static void print_pred_bbs (FILE *, basic_block bb);
4490 static void print_succ_bbs (FILE *, basic_block bb);
4491
4492
4493 /* Print the predecessors indexes of edge E on FILE.  */
4494
4495 static void
4496 print_pred_bbs (FILE *file, basic_block bb)
4497 {
4498   edge e;
4499   edge_iterator ei;
4500
4501   FOR_EACH_EDGE (e, ei, bb->preds)
4502     fprintf (file, "bb_%d", e->src->index);
4503 }
4504
4505
4506 /* Print the successors indexes of edge E on FILE.  */
4507
4508 static void
4509 print_succ_bbs (FILE *file, basic_block bb)
4510 {
4511   edge e;
4512   edge_iterator ei;
4513
4514   FOR_EACH_EDGE (e, ei, bb->succs)
4515     fprintf (file, "bb_%d", e->src->index);
4516 }
4517
4518
4519 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
4520
4521 static void
4522 print_loop (FILE *file, struct loop *loop, int indent)
4523 {
4524   char *s_indent;
4525   basic_block bb;
4526
4527   if (loop == NULL)
4528     return;
4529
4530   s_indent = (char *) alloca ((size_t) indent + 1);
4531   memset ((void *) s_indent, ' ', (size_t) indent);
4532   s_indent[indent] = '\0';
4533
4534   /* Print the loop's header.  */
4535   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
4536
4537   /* Print the loop's body.  */
4538   fprintf (file, "%s{\n", s_indent);
4539   FOR_EACH_BB (bb)
4540     if (bb->loop_father == loop)
4541       {
4542         /* Print the basic_block's header.  */
4543         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
4544         print_pred_bbs (file, bb);
4545         fprintf (file, "}, succs = {");
4546         print_succ_bbs (file, bb);
4547         fprintf (file, "})\n");
4548
4549         /* Print the basic_block's body.  */
4550         fprintf (file, "%s  {\n", s_indent);
4551         tree_dump_bb (bb, file, indent + 4);
4552         fprintf (file, "%s  }\n", s_indent);
4553       }
4554
4555   print_loop (file, loop->inner, indent + 2);
4556   fprintf (file, "%s}\n", s_indent);
4557   print_loop (file, loop->next, indent);
4558 }
4559
4560
4561 /* Follow a CFG edge from the entry point of the program, and on entry
4562    of a loop, pretty print the loop structure on FILE.  */
4563
4564 void
4565 print_loop_ir (FILE *file)
4566 {
4567   basic_block bb;
4568
4569   bb = BASIC_BLOCK (0);
4570   if (bb && bb->loop_father)
4571     print_loop (file, bb->loop_father, 0);
4572 }
4573
4574
4575 /* Debugging loops structure at tree level.  */
4576
4577 void
4578 debug_loop_ir (void)
4579 {
4580   print_loop_ir (stderr);
4581 }
4582
4583
4584 /* Return true if BB ends with a call, possibly followed by some
4585    instructions that must stay with the call.  Return false,
4586    otherwise.  */
4587
4588 static bool
4589 tree_block_ends_with_call_p (basic_block bb)
4590 {
4591   block_stmt_iterator bsi = bsi_last (bb);
4592   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
4593 }
4594
4595
4596 /* Return true if BB ends with a conditional branch.  Return false,
4597    otherwise.  */
4598
4599 static bool
4600 tree_block_ends_with_condjump_p (basic_block bb)
4601 {
4602   tree stmt = last_stmt (bb);
4603   return (stmt && TREE_CODE (stmt) == COND_EXPR);
4604 }
4605
4606
4607 /* Return true if we need to add fake edge to exit at statement T.
4608    Helper function for tree_flow_call_edges_add.  */
4609
4610 static bool
4611 need_fake_edge_p (tree t)
4612 {
4613   tree call;
4614
4615   /* NORETURN and LONGJMP calls already have an edge to exit.
4616      CONST and PURE calls do not need one.
4617      We don't currently check for CONST and PURE here, although
4618      it would be a good idea, because those attributes are
4619      figured out from the RTL in mark_constant_function, and
4620      the counter incrementation code from -fprofile-arcs
4621      leads to different results from -fbranch-probabilities.  */
4622   call = get_call_expr_in (t);
4623   if (call
4624       && !(call_expr_flags (call) & ECF_NORETURN))
4625     return true;
4626
4627   if (TREE_CODE (t) == ASM_EXPR
4628        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
4629     return true;
4630
4631   return false;
4632 }
4633
4634
4635 /* Add fake edges to the function exit for any non constant and non
4636    noreturn calls, volatile inline assembly in the bitmap of blocks
4637    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
4638    the number of blocks that were split.
4639
4640    The goal is to expose cases in which entering a basic block does
4641    not imply that all subsequent instructions must be executed.  */
4642
4643 static int
4644 tree_flow_call_edges_add (sbitmap blocks)
4645 {
4646   int i;
4647   int blocks_split = 0;
4648   int last_bb = last_basic_block;
4649   bool check_last_block = false;
4650
4651   if (n_basic_blocks == 0)
4652     return 0;
4653
4654   if (! blocks)
4655     check_last_block = true;
4656   else
4657     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
4658
4659   /* In the last basic block, before epilogue generation, there will be
4660      a fallthru edge to EXIT.  Special care is required if the last insn
4661      of the last basic block is a call because make_edge folds duplicate
4662      edges, which would result in the fallthru edge also being marked
4663      fake, which would result in the fallthru edge being removed by
4664      remove_fake_edges, which would result in an invalid CFG.
4665
4666      Moreover, we can't elide the outgoing fake edge, since the block
4667      profiler needs to take this into account in order to solve the minimal
4668      spanning tree in the case that the call doesn't return.
4669
4670      Handle this by adding a dummy instruction in a new last basic block.  */
4671   if (check_last_block)
4672     {
4673       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
4674       block_stmt_iterator bsi = bsi_last (bb);
4675       tree t = NULL_TREE;
4676       if (!bsi_end_p (bsi))
4677         t = bsi_stmt (bsi);
4678
4679       if (need_fake_edge_p (t))
4680         {
4681           edge e;
4682
4683           e = find_edge (bb, EXIT_BLOCK_PTR);
4684           if (e)
4685             {
4686               bsi_insert_on_edge (e, build_empty_stmt ());
4687               bsi_commit_edge_inserts ();
4688             }
4689         }
4690     }
4691
4692   /* Now add fake edges to the function exit for any non constant
4693      calls since there is no way that we can determine if they will
4694      return or not...  */
4695   for (i = 0; i < last_bb; i++)
4696     {
4697       basic_block bb = BASIC_BLOCK (i);
4698       block_stmt_iterator bsi;
4699       tree stmt, last_stmt;
4700
4701       if (!bb)
4702         continue;
4703
4704       if (blocks && !TEST_BIT (blocks, i))
4705         continue;
4706
4707       bsi = bsi_last (bb);
4708       if (!bsi_end_p (bsi))
4709         {
4710           last_stmt = bsi_stmt (bsi);
4711           do
4712             {
4713               stmt = bsi_stmt (bsi);
4714               if (need_fake_edge_p (stmt))
4715                 {
4716                   edge e;
4717                   /* The handling above of the final block before the
4718                      epilogue should be enough to verify that there is
4719                      no edge to the exit block in CFG already.
4720                      Calling make_edge in such case would cause us to
4721                      mark that edge as fake and remove it later.  */
4722 #ifdef ENABLE_CHECKING
4723                   if (stmt == last_stmt)
4724                     {
4725                       e = find_edge (bb, EXIT_BLOCK_PTR);
4726                       gcc_assert (e == NULL);
4727                     }
4728 #endif
4729
4730                   /* Note that the following may create a new basic block
4731                      and renumber the existing basic blocks.  */
4732                   if (stmt != last_stmt)
4733                     {
4734                       e = split_block (bb, stmt);
4735                       if (e)
4736                         blocks_split++;
4737                     }
4738                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
4739                 }
4740               bsi_prev (&bsi);
4741             }
4742           while (!bsi_end_p (bsi));
4743         }
4744     }
4745
4746   if (blocks_split)
4747     verify_flow_info ();
4748
4749   return blocks_split;
4750 }
4751
4752 bool
4753 tree_purge_dead_eh_edges (basic_block bb)
4754 {
4755   bool changed = false;
4756   edge e;
4757   edge_iterator ei;
4758   tree stmt = last_stmt (bb);
4759
4760   if (stmt && tree_can_throw_internal (stmt))
4761     return false;
4762
4763   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
4764     {
4765       if (e->flags & EDGE_EH)
4766         {
4767           remove_edge (e);
4768           changed = true;
4769         }
4770       else
4771         ei_next (&ei);
4772     }
4773
4774   /* Removal of dead EH edges might change dominators of not
4775      just immediate successors.  E.g. when bb1 is changed so that
4776      it no longer can throw and bb1->bb3 and bb1->bb4 are dead
4777      eh edges purged by this function in:
4778            0
4779           / \
4780          v   v
4781          1-->2
4782         / \  |
4783        v   v |
4784        3-->4 |
4785         \    v
4786          --->5
4787              |
4788              -
4789      idom(bb5) must be recomputed.  For now just free the dominance
4790      info.  */
4791   if (changed)
4792     free_dominance_info (CDI_DOMINATORS);
4793
4794   return changed;
4795 }
4796
4797 bool
4798 tree_purge_all_dead_eh_edges (bitmap blocks)
4799 {
4800   bool changed = false;
4801   unsigned i;
4802   bitmap_iterator bi;
4803
4804   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
4805     {
4806       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
4807     }
4808
4809   return changed;
4810 }
4811
4812 /* This function is called whenever a new edge is created or
4813    redirected.  */
4814
4815 static void
4816 tree_execute_on_growing_pred (edge e)
4817 {
4818   basic_block bb = e->dest;
4819
4820   if (phi_nodes (bb))
4821     reserve_phi_args_for_new_edge (bb);
4822 }
4823
4824 /* This function is called immediately before edge E is removed from
4825    the edge vector E->dest->preds.  */
4826
4827 static void
4828 tree_execute_on_shrinking_pred (edge e)
4829 {
4830   if (phi_nodes (e->dest))
4831     remove_phi_args (e);
4832 }
4833
4834 /*---------------------------------------------------------------------------
4835   Helper functions for Loop versioning
4836   ---------------------------------------------------------------------------*/
4837
4838 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
4839    of 'first'. Both of them are dominated by 'new_head' basic block. When
4840    'new_head' was created by 'second's incoming edge it received phi arguments
4841    on the edge by split_edge(). Later, additional edge 'e' was created to
4842    connect 'new_head' and 'first'. Now this routine adds phi args on this
4843    additional edge 'e' that new_head to second edge received as part of edge
4844    splitting.
4845 */
4846
4847 static void
4848 tree_lv_adjust_loop_header_phi (basic_block first, basic_block second,
4849                                 basic_block new_head, edge e)
4850 {
4851   tree phi1, phi2;
4852   edge e2 = find_edge (new_head, second);
4853
4854   /* Because NEW_HEAD has been created by splitting SECOND's incoming
4855      edge, we should always have an edge from NEW_HEAD to SECOND.  */
4856   gcc_assert (e2 != NULL);
4857
4858   /* Browse all 'second' basic block phi nodes and add phi args to
4859      edge 'e' for 'first' head. PHI args are always in correct order.  */
4860
4861   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first);
4862        phi2 && phi1;
4863        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
4864     {
4865       tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
4866       add_phi_arg (phi1, def, e);
4867     }
4868 }
4869
4870 /* Adds a if else statement to COND_BB with condition COND_EXPR.
4871    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
4872    the destination of the ELSE part.  */
4873 static void
4874 tree_lv_add_condition_to_bb (basic_block first_head, basic_block second_head,
4875                             basic_block cond_bb, void *cond_e)
4876 {
4877   block_stmt_iterator bsi;
4878   tree goto1 = NULL_TREE;
4879   tree goto2 = NULL_TREE;
4880   tree new_cond_expr = NULL_TREE;
4881   tree cond_expr = (tree) cond_e;
4882   edge e0;
4883
4884   /* Build new conditional expr */
4885   goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
4886   goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
4887   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
4888
4889   /* Add new cond in cond_bb.  */
4890   bsi = bsi_start (cond_bb);
4891   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
4892   /* Adjust edges appropriately to connect new head with first head
4893      as well as second head.  */
4894   e0 = single_succ_edge (cond_bb);
4895   e0->flags &= ~EDGE_FALLTHRU;
4896   e0->flags |= EDGE_FALSE_VALUE;
4897 }
4898
4899 struct cfg_hooks tree_cfg_hooks = {
4900   "tree",
4901   tree_verify_flow_info,
4902   tree_dump_bb,                 /* dump_bb  */
4903   create_bb,                    /* create_basic_block  */
4904   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
4905   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
4906   remove_bb,                    /* delete_basic_block  */
4907   tree_split_block,             /* split_block  */
4908   tree_move_block_after,        /* move_block_after  */
4909   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
4910   tree_merge_blocks,            /* merge_blocks  */
4911   tree_predict_edge,            /* predict_edge  */
4912   tree_predicted_by_p,          /* predicted_by_p  */
4913   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
4914   tree_duplicate_bb,            /* duplicate_block  */
4915   tree_split_edge,              /* split_edge  */
4916   tree_make_forwarder_block,    /* make_forward_block  */
4917   NULL,                         /* tidy_fallthru_edge  */
4918   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
4919   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
4920   tree_flow_call_edges_add,     /* flow_call_edges_add */
4921   tree_execute_on_growing_pred, /* execute_on_growing_pred */
4922   tree_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
4923   tree_duplicate_loop_to_header_edge, /* duplicate loop for trees */
4924   tree_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
4925   tree_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
4926   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
4927   flush_pending_stmts           /* flush_pending_stmts */
4928 };
4929
4930
4931 /* Split all critical edges.  */
4932
4933 static void
4934 split_critical_edges (void)
4935 {
4936   basic_block bb;
4937   edge e;
4938   edge_iterator ei;
4939
4940   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
4941      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
4942      mappings around the calls to split_edge.  */
4943   start_recording_case_labels ();
4944   FOR_ALL_BB (bb)
4945     {
4946       FOR_EACH_EDGE (e, ei, bb->succs)
4947         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
4948           {
4949             split_edge (e);
4950           }
4951     }
4952   end_recording_case_labels ();
4953 }
4954
4955 struct tree_opt_pass pass_split_crit_edges =
4956 {
4957   "crited",                          /* name */
4958   NULL,                          /* gate */
4959   split_critical_edges,          /* execute */
4960   NULL,                          /* sub */
4961   NULL,                          /* next */
4962   0,                             /* static_pass_number */
4963   TV_TREE_SPLIT_EDGES,           /* tv_id */
4964   PROP_cfg,                      /* properties required */
4965   PROP_no_crit_edges,            /* properties_provided */
4966   0,                             /* properties_destroyed */
4967   0,                             /* todo_flags_start */
4968   TODO_dump_func,                /* todo_flags_finish */
4969   0                              /* letter */
4970 };
4971
4972 \f
4973 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
4974    a temporary, make sure and register it to be renamed if necessary,
4975    and finally return the temporary.  Put the statements to compute
4976    EXP before the current statement in BSI.  */
4977
4978 tree
4979 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
4980 {
4981   tree t, new_stmt, orig_stmt;
4982
4983   if (is_gimple_val (exp))
4984     return exp;
4985
4986   t = make_rename_temp (type, NULL);
4987   new_stmt = build (MODIFY_EXPR, type, t, exp);
4988
4989   orig_stmt = bsi_stmt (*bsi);
4990   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
4991   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
4992
4993   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
4994
4995   return t;
4996 }
4997
4998 /* Build a ternary operation and gimplify it.  Emit code before BSI.
4999    Return the gimple_val holding the result.  */
5000
5001 tree
5002 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
5003                  tree type, tree a, tree b, tree c)
5004 {
5005   tree ret;
5006
5007   ret = fold_build3 (code, type, a, b, c);
5008   STRIP_NOPS (ret);
5009
5010   return gimplify_val (bsi, type, ret);
5011 }
5012
5013 /* Build a binary operation and gimplify it.  Emit code before BSI.
5014    Return the gimple_val holding the result.  */
5015
5016 tree
5017 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
5018                  tree type, tree a, tree b)
5019 {
5020   tree ret;
5021
5022   ret = fold_build2 (code, type, a, b);
5023   STRIP_NOPS (ret);
5024
5025   return gimplify_val (bsi, type, ret);
5026 }
5027
5028 /* Build a unary operation and gimplify it.  Emit code before BSI.
5029    Return the gimple_val holding the result.  */
5030
5031 tree
5032 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
5033                  tree a)
5034 {
5035   tree ret;
5036
5037   ret = fold_build1 (code, type, a);
5038   STRIP_NOPS (ret);
5039
5040   return gimplify_val (bsi, type, ret);
5041 }
5042
5043
5044 \f
5045 /* Emit return warnings.  */
5046
5047 static void
5048 execute_warn_function_return (void)
5049 {
5050 #ifdef USE_MAPPED_LOCATION
5051   source_location location;
5052 #else
5053   location_t *locus;
5054 #endif
5055   tree last;
5056   edge e;
5057   edge_iterator ei;
5058
5059   /* If we have a path to EXIT, then we do return.  */
5060   if (TREE_THIS_VOLATILE (cfun->decl)
5061       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
5062     {
5063 #ifdef USE_MAPPED_LOCATION
5064       location = UNKNOWN_LOCATION;
5065 #else
5066       locus = NULL;
5067 #endif
5068       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5069         {
5070           last = last_stmt (e->src);
5071           if (TREE_CODE (last) == RETURN_EXPR
5072 #ifdef USE_MAPPED_LOCATION
5073               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
5074 #else
5075               && (locus = EXPR_LOCUS (last)) != NULL)
5076 #endif
5077             break;
5078         }
5079 #ifdef USE_MAPPED_LOCATION
5080       if (location == UNKNOWN_LOCATION)
5081         location = cfun->function_end_locus;
5082       warning (0, "%H%<noreturn%> function does return", &location);
5083 #else
5084       if (!locus)
5085         locus = &cfun->function_end_locus;
5086       warning (0, "%H%<noreturn%> function does return", locus);
5087 #endif
5088     }
5089
5090   /* If we see "return;" in some basic block, then we do reach the end
5091      without returning a value.  */
5092   else if (warn_return_type
5093            && !TREE_NO_WARNING (cfun->decl)
5094            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
5095            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
5096     {
5097       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5098         {
5099           tree last = last_stmt (e->src);
5100           if (TREE_CODE (last) == RETURN_EXPR
5101               && TREE_OPERAND (last, 0) == NULL)
5102             {
5103 #ifdef USE_MAPPED_LOCATION
5104               location = EXPR_LOCATION (last);
5105               if (location == UNKNOWN_LOCATION)
5106                   location = cfun->function_end_locus;
5107               warning (0, "%Hcontrol reaches end of non-void function", &location);
5108 #else
5109               locus = EXPR_LOCUS (last);
5110               if (!locus)
5111                 locus = &cfun->function_end_locus;
5112               warning (0, "%Hcontrol reaches end of non-void function", locus);
5113 #endif
5114               TREE_NO_WARNING (cfun->decl) = 1;
5115               break;
5116             }
5117         }
5118     }
5119 }
5120
5121
5122 /* Given a basic block B which ends with a conditional and has
5123    precisely two successors, determine which of the edges is taken if
5124    the conditional is true and which is taken if the conditional is
5125    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
5126
5127 void
5128 extract_true_false_edges_from_block (basic_block b,
5129                                      edge *true_edge,
5130                                      edge *false_edge)
5131 {
5132   edge e = EDGE_SUCC (b, 0);
5133
5134   if (e->flags & EDGE_TRUE_VALUE)
5135     {
5136       *true_edge = e;
5137       *false_edge = EDGE_SUCC (b, 1);
5138     }
5139   else
5140     {
5141       *false_edge = e;
5142       *true_edge = EDGE_SUCC (b, 1);
5143     }
5144 }
5145
5146 struct tree_opt_pass pass_warn_function_return =
5147 {
5148   NULL,                                 /* name */
5149   NULL,                                 /* gate */
5150   execute_warn_function_return,         /* execute */
5151   NULL,                                 /* sub */
5152   NULL,                                 /* next */
5153   0,                                    /* static_pass_number */
5154   0,                                    /* tv_id */
5155   PROP_cfg,                             /* properties_required */
5156   0,                                    /* properties_provided */
5157   0,                                    /* properties_destroyed */
5158   0,                                    /* todo_flags_start */
5159   0,                                    /* todo_flags_finish */
5160   0                                     /* letter */
5161 };
5162
5163 /* Emit noreturn warnings.  */
5164
5165 static void
5166 execute_warn_function_noreturn (void)
5167 {
5168   if (warn_missing_noreturn
5169       && !TREE_THIS_VOLATILE (cfun->decl)
5170       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
5171       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
5172     warning (OPT_Wmissing_noreturn, "%Jfunction might be possible candidate "
5173              "for attribute %<noreturn%>",
5174              cfun->decl);
5175 }
5176
5177 struct tree_opt_pass pass_warn_function_noreturn =
5178 {
5179   NULL,                                 /* name */
5180   NULL,                                 /* gate */
5181   execute_warn_function_noreturn,       /* execute */
5182   NULL,                                 /* sub */
5183   NULL,                                 /* next */
5184   0,                                    /* static_pass_number */
5185   0,                                    /* tv_id */
5186   PROP_cfg,                             /* properties_required */
5187   0,                                    /* properties_provided */
5188   0,                                    /* properties_destroyed */
5189   0,                                    /* todo_flags_start */
5190   0,                                    /* todo_flags_finish */
5191   0                                     /* letter */
5192 };