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