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