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