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