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