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