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