gcc/tree-cfg.c

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