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