gcc/tree-cfg.c

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