gcc/tree-cfg.c

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