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
2936   /* Otherwise, create a new basic block, and split this edge.  */
2937   dest = split_edge (e);
2938   e = dest->pred;
2939   goto restart;
2940 }
2941
2942
2943 /* This routine will commit all pending edge insertions, creating any new
2944    basic blocks which are necessary.
2945
2946    If specified, NEW_BLOCKS returns a count of the number of new basic
2947    blocks which were created.  */
2948
2949 void
2950 bsi_commit_edge_inserts (int *new_blocks)
2951 {
2952   basic_block bb;
2953   edge e;
2954   int blocks;
2955
2956   blocks = n_basic_blocks;
2957
2958   bsi_commit_edge_inserts_1 (ENTRY_BLOCK_PTR->succ);
2959
2960   FOR_EACH_BB (bb)
2961     for (e = bb->succ; e; e = e->succ_next)
2962       bsi_commit_edge_inserts_1 (e);
2963
2964   if (new_blocks)
2965     *new_blocks = n_basic_blocks - blocks;
2966 }
2967
2968
2969 /* Commit insertions pending at edge E.  */
2970
2971 static void
2972 bsi_commit_edge_inserts_1 (edge e)
2973 {
2974   if (PENDING_STMT (e))
2975     {
2976       block_stmt_iterator bsi;
2977       tree stmt = PENDING_STMT (e);
2978
2979       PENDING_STMT (e) = NULL_TREE;
2980
2981       if (tree_find_edge_insert_loc (e, &bsi))
2982         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2983       else
2984         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2985     }
2986 }
2987
2988
2989 /* Add STMT to the pending list of edge E.  No actual insertion is
2990    made until a call to bsi_commit_edge_inserts () is made.  */
2991
2992 void
2993 bsi_insert_on_edge (edge e, tree stmt)
2994 {
2995   append_to_statement_list (stmt, &PENDING_STMT (e));
2996 }
2997
2998
2999 /* Specialized edge insertion for SSA-PRE.  FIXME: This should
3000    probably disappear.  The only reason it's here is because PRE needs
3001    the call to tree_find_edge_insert_loc().  */
3002
3003 void pre_insert_on_edge (edge e, tree stmt);
3004
3005 void
3006 pre_insert_on_edge (edge e, tree stmt)
3007 {
3008   block_stmt_iterator bsi;
3009
3010   if (PENDING_STMT (e))
3011     abort ();
3012
3013   if (tree_find_edge_insert_loc (e, &bsi))
3014     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3015   else
3016     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3017 }
3018
3019
3020 /*---------------------------------------------------------------------------
3021              Tree specific functions for CFG manipulation
3022 ---------------------------------------------------------------------------*/
3023
3024 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3025    Abort on abnormal edges.  */
3026
3027 static basic_block
3028 tree_split_edge (edge edge_in)
3029 {
3030   basic_block new_bb, after_bb, dest, src;
3031   edge new_edge, e;
3032   tree phi;
3033   int i, num_elem;
3034
3035   /* Abnormal edges cannot be split.  */
3036   if (edge_in->flags & EDGE_ABNORMAL)
3037     abort ();
3038
3039   src = edge_in->src;
3040   dest = edge_in->dest;
3041
3042   /* Place the new block in the block list.  Try to keep the new block
3043      near its "logical" location.  This is of most help to humans looking
3044      at debugging dumps.  */
3045   for (e = dest->pred; e; e = e->pred_next)
3046     if (e->src->next_bb == dest)
3047       break;
3048   if (!e)
3049     after_bb = dest->prev_bb;
3050   else
3051     after_bb = edge_in->src;
3052
3053   new_bb = create_empty_bb (after_bb);
3054   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3055
3056   /* Find all the PHI arguments on the original edge, and change them to
3057      the new edge.  Do it before redirection, so that the argument does not
3058      get removed.  */
3059   for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
3060     {
3061       num_elem = PHI_NUM_ARGS (phi);
3062       for (i = 0; i < num_elem; i++)
3063         if (PHI_ARG_EDGE (phi, i) == edge_in)
3064           {
3065             PHI_ARG_EDGE (phi, i) = new_edge;
3066             break;
3067           }
3068     }
3069
3070   if (!redirect_edge_and_branch (edge_in, new_bb))
3071     abort ();
3072
3073   if (PENDING_STMT (edge_in))
3074     abort ();
3075
3076   return new_bb;
3077 }
3078
3079
3080 /* Return true when BB has label LABEL in it.  */
3081
3082 static bool
3083 has_label_p (basic_block bb, tree label)
3084 {
3085   block_stmt_iterator bsi;
3086
3087   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3088     {
3089       tree stmt = bsi_stmt (bsi);
3090
3091       if (TREE_CODE (stmt) != LABEL_EXPR)
3092         return false;
3093       if (LABEL_EXPR_LABEL (stmt) == label)
3094         return true;
3095     }
3096   return false;
3097 }
3098
3099
3100 /* Callback for walk_tree, check that all elements with address taken are
3101    properly noticed as such.  */
3102
3103 static tree
3104 verify_expr (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
3105              void *data ATTRIBUTE_UNUSED)
3106 {
3107   tree t = *tp, x;
3108
3109   if (TYPE_P (t))
3110     *walk_subtrees = 0;
3111
3112   switch (TREE_CODE (t))
3113     {
3114     case SSA_NAME:
3115       if (SSA_NAME_IN_FREE_LIST (t))
3116         {
3117           error ("SSA name in freelist but still referenced");
3118           return *tp;
3119         }
3120       break;
3121
3122     case MODIFY_EXPR:
3123       x = TREE_OPERAND (t, 0);
3124       if (TREE_CODE (x) == BIT_FIELD_REF
3125           && is_gimple_reg (TREE_OPERAND (x, 0)))
3126         {
3127           error ("GIMPLE register modified with BIT_FIELD_REF");
3128           return *tp;
3129         }
3130       break;
3131
3132     case ADDR_EXPR:
3133       x = TREE_OPERAND (t, 0);
3134       while (TREE_CODE (x) == ARRAY_REF
3135              || TREE_CODE (x) == COMPONENT_REF
3136              || TREE_CODE (x) == REALPART_EXPR
3137              || TREE_CODE (x) == IMAGPART_EXPR)
3138         x = TREE_OPERAND (x, 0);
3139       if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3140         return NULL;
3141       if (!TREE_ADDRESSABLE (x))
3142         {
3143           error ("address taken, but ADDRESSABLE bit not set");
3144           return x;
3145         }
3146       break;
3147
3148     case COND_EXPR:
3149       x = TREE_OPERAND (t, 0);
3150       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3151         {
3152           error ("non-boolean used in condition");
3153           return x;
3154         }
3155       break;
3156
3157     case NOP_EXPR:
3158     case CONVERT_EXPR:
3159     case FIX_TRUNC_EXPR:
3160     case FIX_CEIL_EXPR:
3161     case FIX_FLOOR_EXPR:
3162     case FIX_ROUND_EXPR:
3163     case FLOAT_EXPR:
3164     case NEGATE_EXPR:
3165     case ABS_EXPR:
3166     case BIT_NOT_EXPR:
3167     case NON_LVALUE_EXPR:
3168     case TRUTH_NOT_EXPR:
3169       x = TREE_OPERAND (t, 0);
3170       /* We check for constants explicitly since they are not considered
3171          gimple invariants if they overflowed.  */
3172       if (TREE_CODE_CLASS (TREE_CODE (x)) != 'c'
3173           && !is_gimple_val (x))
3174         {
3175           error ("Invalid operand to unary operator");
3176           return x;
3177         }
3178       break;
3179
3180     case REALPART_EXPR:
3181     case IMAGPART_EXPR:
3182       break;
3183
3184     case LT_EXPR:
3185     case LE_EXPR:
3186     case GT_EXPR:
3187     case GE_EXPR:
3188     case EQ_EXPR:
3189     case NE_EXPR:
3190     case UNORDERED_EXPR:
3191     case ORDERED_EXPR:
3192     case UNLT_EXPR:
3193     case UNLE_EXPR:
3194     case UNGT_EXPR:
3195     case UNGE_EXPR:
3196     case UNEQ_EXPR:
3197     case PLUS_EXPR:
3198     case MINUS_EXPR:
3199     case MULT_EXPR:
3200     case TRUNC_DIV_EXPR:
3201     case CEIL_DIV_EXPR:
3202     case FLOOR_DIV_EXPR:
3203     case ROUND_DIV_EXPR:
3204     case TRUNC_MOD_EXPR:
3205     case CEIL_MOD_EXPR:
3206     case FLOOR_MOD_EXPR:
3207     case ROUND_MOD_EXPR:
3208     case RDIV_EXPR:
3209     case EXACT_DIV_EXPR:
3210     case MIN_EXPR:
3211     case MAX_EXPR:
3212     case LSHIFT_EXPR:
3213     case RSHIFT_EXPR:
3214     case LROTATE_EXPR:
3215     case RROTATE_EXPR:
3216     case BIT_IOR_EXPR:
3217     case BIT_XOR_EXPR:
3218     case BIT_AND_EXPR:
3219       x = TREE_OPERAND (t, 0);
3220       /* We check for constants explicitly since they are not considered
3221          gimple invariants if they overflowed.  */
3222       if (TREE_CODE_CLASS (TREE_CODE (x)) != 'c'
3223           && !is_gimple_val (x))
3224         {
3225           error ("Invalid operand to binary operator");
3226           return x;
3227         }
3228       x = TREE_OPERAND (t, 1);
3229       /* We check for constants explicitly since they are not considered
3230          gimple invariants if they overflowed.  */
3231       if (TREE_CODE_CLASS (TREE_CODE (x)) != 'c'
3232           && !is_gimple_val (x))
3233         {
3234           error ("Invalid operand to binary operator");
3235           return x;
3236         }
3237       break;
3238
3239     default:
3240       break;
3241     }
3242   return NULL;
3243 }
3244
3245
3246 /* Verify STMT, return true if STMT is not in GIMPLE form.
3247    TODO: Implement type checking.  */
3248
3249 static bool
3250 verify_stmt (tree stmt)
3251 {
3252   tree addr;
3253
3254   if (!is_gimple_stmt (stmt))
3255     {
3256       error ("Is not a valid GIMPLE statement.");
3257       debug_generic_stmt (stmt);
3258       return true;
3259     }
3260
3261   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3262   if (addr)
3263     {
3264       debug_generic_stmt (addr);
3265       return true;
3266     }
3267
3268   return false;
3269 }
3270
3271
3272 /* Return true when the T can be shared.  */
3273
3274 static bool
3275 tree_node_can_be_shared (tree t)
3276 {
3277   if (TYPE_P (t) || DECL_P (t)
3278       /* We check for constants explicitly since they are not considered
3279          gimple invariants if they overflowed.  */
3280       || TREE_CODE_CLASS (TREE_CODE (t)) == 'c'
3281       || is_gimple_min_invariant (t)
3282       || TREE_CODE (t) == SSA_NAME)
3283     return true;
3284
3285   while ((TREE_CODE (t) == ARRAY_REF
3286           /* We check for constants explicitly since they are not considered
3287              gimple invariants if they overflowed.  */
3288           && (TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (t, 1))) == 'c'
3289               || is_gimple_min_invariant (TREE_OPERAND (t, 1))))
3290          || (TREE_CODE (t) == COMPONENT_REF
3291              || TREE_CODE (t) == REALPART_EXPR
3292              || TREE_CODE (t) == IMAGPART_EXPR))
3293     t = TREE_OPERAND (t, 0);
3294
3295   if (DECL_P (t))
3296     return true;
3297
3298   return false;
3299 }
3300
3301
3302 /* Called via walk_trees.  Verify tree sharing.  */
3303
3304 static tree
3305 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3306 {
3307   htab_t htab = (htab_t) data;
3308   void **slot;
3309
3310   if (tree_node_can_be_shared (*tp))
3311     {
3312       *walk_subtrees = false;
3313       return NULL;
3314     }
3315
3316   slot = htab_find_slot (htab, *tp, INSERT);
3317   if (*slot)
3318     return *slot;
3319   *slot = *tp;
3320
3321   return NULL;
3322 }
3323
3324
3325 /* Verify the GIMPLE statement chain.  */
3326
3327 void
3328 verify_stmts (void)
3329 {
3330   basic_block bb;
3331   block_stmt_iterator bsi;
3332   bool err = false;
3333   htab_t htab;
3334   tree addr;
3335
3336   timevar_push (TV_TREE_STMT_VERIFY);
3337   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3338
3339   FOR_EACH_BB (bb)
3340     {
3341       tree phi;
3342       int i;
3343
3344       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
3345         {
3346           int phi_num_args = PHI_NUM_ARGS (phi);
3347
3348           for (i = 0; i < phi_num_args; i++)
3349             {
3350               tree t = PHI_ARG_DEF (phi, i);
3351               tree addr;
3352
3353               /* Addressable variables do have SSA_NAMEs but they
3354                  are not considered gimple values.  */
3355               if (TREE_CODE (t) != SSA_NAME
3356                   && TREE_CODE (t) != FUNCTION_DECL
3357                   && !is_gimple_val (t))
3358                 {
3359                   error ("PHI def is not a GIMPLE value");
3360                   debug_generic_stmt (phi);
3361                   debug_generic_stmt (t);
3362                   err |= true;
3363                 }
3364
3365               addr = walk_tree (&t, verify_expr, NULL, NULL);
3366               if (addr)
3367                 {
3368                   debug_generic_stmt (addr);
3369                   err |= true;
3370                 }
3371
3372               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3373               if (addr)
3374                 {
3375                   error ("Incorrect sharing of tree nodes");
3376                   debug_generic_stmt (phi);
3377                   debug_generic_stmt (addr);
3378                   err |= true;
3379                 }
3380             }
3381         }
3382
3383       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3384         {
3385           tree stmt = bsi_stmt (bsi);
3386           err |= verify_stmt (stmt);
3387           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3388           if (addr)
3389             {
3390               error ("Incorrect sharing of tree nodes");
3391               debug_generic_stmt (stmt);
3392               debug_generic_stmt (addr);
3393               err |= true;
3394             }
3395         }
3396     }
3397
3398   if (err)
3399     internal_error ("verify_stmts failed.");
3400
3401   htab_delete (htab);
3402   timevar_pop (TV_TREE_STMT_VERIFY);
3403 }
3404
3405
3406 /* Verifies that the flow information is OK.  */
3407
3408 static int
3409 tree_verify_flow_info (void)
3410 {
3411   int err = 0;
3412   basic_block bb;
3413   block_stmt_iterator bsi;
3414   tree stmt;
3415   edge e;
3416
3417   if (ENTRY_BLOCK_PTR->stmt_list)
3418     {
3419       error ("ENTRY_BLOCK has a statement list associated with it\n");
3420       err = 1;
3421     }
3422
3423   if (EXIT_BLOCK_PTR->stmt_list)
3424     {
3425       error ("EXIT_BLOCK has a statement list associated with it\n");
3426       err = 1;
3427     }
3428
3429   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
3430     if (e->flags & EDGE_FALLTHRU)
3431       {
3432         error ("Fallthru to exit from bb %d\n", e->src->index);
3433         err = 1;
3434       }
3435
3436   FOR_EACH_BB (bb)
3437     {
3438       bool found_ctrl_stmt = false;
3439
3440       /* Skip labels on the start of basic block.  */
3441       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3442         {
3443           if (TREE_CODE (bsi_stmt (bsi)) != LABEL_EXPR)
3444             break;
3445
3446           if (label_to_block (LABEL_EXPR_LABEL (bsi_stmt (bsi))) != bb)
3447             {
3448               error ("Label %s to block does not match in bb %d\n",
3449                      IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi))),
3450                      bb->index);
3451               err = 1;
3452             }
3453
3454           if (decl_function_context (LABEL_EXPR_LABEL (bsi_stmt (bsi)))
3455               != current_function_decl)
3456             {
3457               error ("Label %s has incorrect context in bb %d\n",
3458                      IDENTIFIER_POINTER (DECL_NAME (bsi_stmt (bsi))),
3459                      bb->index);
3460               err = 1;
3461             }
3462         }
3463
3464       /* Verify that body of basic block BB is free of control flow.  */
3465       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3466         {
3467           tree stmt = bsi_stmt (bsi);
3468
3469           if (found_ctrl_stmt)
3470             {
3471               error ("Control flow in the middle of basic block %d\n",
3472                      bb->index);
3473               err = 1;
3474             }
3475
3476           if (stmt_ends_bb_p (stmt))
3477             found_ctrl_stmt = true;
3478
3479           if (TREE_CODE (stmt) == LABEL_EXPR)
3480             {
3481               error ("Label %s in the middle of basic block %d\n",
3482                      IDENTIFIER_POINTER (DECL_NAME (stmt)),
3483                      bb->index);
3484               err = 1;
3485             }
3486         }
3487       bsi = bsi_last (bb);
3488       if (bsi_end_p (bsi))
3489         continue;
3490
3491       stmt = bsi_stmt (bsi);
3492
3493       if (is_ctrl_stmt (stmt))
3494         {
3495           for (e = bb->succ; e; e = e->succ_next)
3496             if (e->flags & EDGE_FALLTHRU)
3497               {
3498                 error ("Fallthru edge after a control statement in bb %d \n",
3499                        bb->index);
3500                 err = 1;
3501               }
3502         }
3503
3504       switch (TREE_CODE (stmt))
3505         {
3506         case COND_EXPR:
3507           {
3508             edge true_edge;
3509             edge false_edge;
3510             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3511                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3512               {
3513                 error ("Structured COND_EXPR at the end of bb %d\n", bb->index);
3514                 err = 1;
3515               }
3516
3517             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3518
3519             if (!true_edge || !false_edge
3520                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3521                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3522                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3523                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3524                 || bb->succ->succ_next->succ_next)
3525               {
3526                 error ("Wrong outgoing edge flags at end of bb %d\n",
3527                        bb->index);
3528                 err = 1;
3529               }
3530
3531             if (!has_label_p (true_edge->dest,
3532                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3533               {
3534                 error ("`then' label does not match edge at end of bb %d\n",
3535                        bb->index);
3536                 err = 1;
3537               }
3538
3539             if (!has_label_p (false_edge->dest,
3540                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3541               {
3542                 error ("`else' label does not match edge at end of bb %d\n",
3543                        bb->index);
3544                 err = 1;
3545               }
3546           }
3547           break;
3548
3549         case GOTO_EXPR:
3550           if (simple_goto_p (stmt))
3551             {
3552               error ("Explicit goto at end of bb %d\n", bb->index);
3553               err = 1;
3554             }
3555           else
3556             {
3557               /* FIXME.  We should double check that the labels in the
3558                  destination blocks have their address taken.  */
3559               for (e = bb->succ; e; e = e->succ_next)
3560                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3561                                  | EDGE_FALSE_VALUE))
3562                     || !(e->flags & EDGE_ABNORMAL))
3563                   {
3564                     error ("Wrong outgoing edge flags at end of bb %d\n",
3565                            bb->index);
3566                     err = 1;
3567                   }
3568             }
3569           break;
3570
3571         case RETURN_EXPR:
3572           if (!bb->succ || bb->succ->succ_next
3573               || (bb->succ->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3574                                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3575             {
3576               error ("Wrong outgoing edge flags at end of bb %d\n", bb->index);
3577               err = 1;
3578             }
3579           if (bb->succ->dest != EXIT_BLOCK_PTR)
3580             {
3581               error ("Return edge does not point to exit in bb %d\n",
3582                      bb->index);
3583               err = 1;
3584             }
3585           break;
3586
3587         case SWITCH_EXPR:
3588           {
3589             edge e;
3590             size_t i, n;
3591             tree vec;
3592
3593             vec = SWITCH_LABELS (stmt);
3594             n = TREE_VEC_LENGTH (vec);
3595
3596             /* Mark all the destination basic blocks.  */
3597             for (i = 0; i < n; ++i)
3598               {
3599                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3600                 basic_block label_bb = label_to_block (lab);
3601
3602                 if (label_bb->aux && label_bb->aux != (void *)1)
3603                   abort ();
3604                 label_bb->aux = (void *)1;
3605               }
3606
3607             for (e = bb->succ; e; e = e->succ_next)
3608               {
3609                 if (!e->dest->aux)
3610                   {
3611                     error ("Extra outgoing edge %d->%d\n",
3612                            bb->index, e->dest->index);
3613                     err = 1;
3614                   }
3615                 e->dest->aux = (void *)2;
3616                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3617                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3618                   {
3619                     error ("Wrong outgoing edge flags at end of bb %d\n",
3620                            bb->index);
3621                     err = 1;
3622                   }
3623               }
3624
3625             /* Check that we have all of them.  */
3626             for (i = 0; i < n; ++i)
3627               {
3628                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3629                 basic_block label_bb = label_to_block (lab);
3630
3631                 if (label_bb->aux != (void *)2)
3632                   {
3633                     error ("Missing edge %i->%i\n",
3634                            bb->index, label_bb->index);
3635                     err = 1;
3636                   }
3637               }
3638
3639             for (e = bb->succ; e; e = e->succ_next)
3640               e->dest->aux = (void *)0;
3641           }
3642
3643         default: ;
3644         }
3645     }
3646
3647   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
3648     verify_dominators (CDI_DOMINATORS);
3649
3650   return err;
3651 }
3652
3653
3654 /* Updates phi nodes after creating forwarder block joined
3655    by edge FALLTHRU.  */
3656
3657 static void
3658 tree_make_forwarder_block (edge fallthru)
3659 {
3660   edge e;
3661   basic_block dummy, bb;
3662   tree phi, new_phi, var;
3663
3664   dummy = fallthru->src;
3665   bb = fallthru->dest;
3666
3667   if (!bb->pred->pred_next)
3668     return;
3669
3670   /* If we redirected a branch we must create new phi nodes at the
3671      start of BB.  */
3672   for (phi = phi_nodes (dummy); phi; phi = TREE_CHAIN (phi))
3673     {
3674       var = PHI_RESULT (phi);
3675       new_phi = create_phi_node (var, bb);
3676       SSA_NAME_DEF_STMT (var) = new_phi;
3677       PHI_RESULT (phi) = make_ssa_name (SSA_NAME_VAR (var), phi);
3678       add_phi_arg (&new_phi, PHI_RESULT (phi), fallthru);
3679     }
3680
3681   /* Ensure that the PHI node chains are in the same order.  */
3682   set_phi_nodes (bb, nreverse (phi_nodes (bb)));
3683
3684   /* Add the arguments we have stored on edges.  */
3685   for (e = bb->pred; e; e = e->pred_next)
3686     {
3687       if (e == fallthru)
3688         continue;
3689
3690       for (phi = phi_nodes (bb), var = PENDING_STMT (e);
3691            phi;
3692            phi = TREE_CHAIN (phi), var = TREE_CHAIN (var))
3693         add_phi_arg (&phi, TREE_VALUE (var), e);
3694
3695       PENDING_STMT (e) = NULL;
3696     }
3697 }
3698
3699
3700 /* Return true if basic block BB does nothing except pass control
3701    flow to another block and that we can safely insert a label at
3702    the start of the successor block.  */
3703
3704 static bool
3705 tree_forwarder_block_p (basic_block bb)
3706 {
3707   block_stmt_iterator bsi;
3708   edge e;
3709
3710   /* If we have already determined that this block is not forwardable,
3711      then no further checks are necessary.  */
3712   if (! bb_ann (bb)->forwardable)
3713     return false;
3714
3715   /* BB must have a single outgoing normal edge.  Otherwise it can not be
3716      a forwarder block.  */
3717   if (!bb->succ
3718       || bb->succ->succ_next
3719       || bb->succ->dest == EXIT_BLOCK_PTR
3720       || (bb->succ->flags & EDGE_ABNORMAL)
3721       || bb == ENTRY_BLOCK_PTR)
3722     {
3723       bb_ann (bb)->forwardable = 0;
3724       return false;
3725     }
3726
3727   /* Successors of the entry block are not forwarders.  */
3728   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
3729     if (e->dest == bb)
3730       {
3731         bb_ann (bb)->forwardable = 0;
3732         return false;
3733       }
3734
3735   /* BB can not have any PHI nodes.  This could potentially be relaxed
3736      early in compilation if we re-rewrote the variables appearing in
3737      any PHI nodes in forwarder blocks.  */
3738   if (phi_nodes (bb))
3739     {
3740       bb_ann (bb)->forwardable = 0;
3741       return false;
3742     }
3743
3744   /* Now walk through the statements.  We can ignore labels, anything else
3745      means this is not a forwarder block.  */
3746   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3747     {
3748       tree stmt = bsi_stmt (bsi);
3749
3750       switch (TREE_CODE (stmt))
3751         {
3752         case LABEL_EXPR:
3753           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3754             return false;
3755           break;
3756
3757         default:
3758           bb_ann (bb)->forwardable = 0;
3759           return false;
3760         }
3761     }
3762
3763   return true;
3764 }
3765
3766
3767 /* Thread jumps over empty statements.
3768
3769    This code should _not_ thread over obviously equivalent conditions
3770    as that requires nontrivial updates to the SSA graph.  */
3771
3772 static bool
3773 thread_jumps (void)
3774 {
3775   edge e, next, last, old;
3776   basic_block bb, dest, tmp;
3777   tree phi;
3778   int arg;
3779   bool retval = false;
3780
3781   FOR_EACH_BB (bb)
3782     bb_ann (bb)->forwardable = 1;
3783
3784   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
3785     {
3786       /* Don't waste time on unreachable blocks.  */
3787       if (!bb->pred)
3788         continue;
3789
3790       /* Nor on forwarders.  */
3791       if (tree_forwarder_block_p (bb))
3792         continue;
3793
3794       /* This block is now part of a forwarding path, mark it as not
3795          forwardable so that we can detect loops.  This bit will be
3796          reset below.  */
3797       bb_ann (bb)->forwardable = 0;
3798
3799       /* Examine each of our block's successors to see if it is
3800          forwardable.  */
3801       for (e = bb->succ; e; e = next)
3802         {
3803           next = e->succ_next;
3804
3805           /* If the edge is abnormal or its destination is not
3806              forwardable, then there's nothing to do.  */
3807           if ((e->flags & EDGE_ABNORMAL)
3808               || !tree_forwarder_block_p (e->dest))
3809             continue;
3810
3811           /* Now walk through as many forwarder block as possible to
3812              find the ultimate destination we want to thread our jump
3813              to.  */
3814           last = e->dest->succ;
3815           bb_ann (e->dest)->forwardable = 0;
3816           for (dest = e->dest->succ->dest;
3817                tree_forwarder_block_p (dest);
3818                last = dest->succ,
3819                dest = dest->succ->dest)
3820             {
3821               /* An infinite loop detected.  We redirect the edge anyway, so
3822                  that the loop is shrinked into single basic block.  */
3823               if (!bb_ann (dest)->forwardable)
3824                 break;
3825
3826               if (dest->succ->dest == EXIT_BLOCK_PTR)
3827                 break;
3828
3829               bb_ann (dest)->forwardable = 0;
3830             }
3831
3832           /* Reset the forwardable marks to 1.  */
3833           for (tmp = e->dest;
3834                tmp != dest;
3835                tmp = tmp->succ->dest)
3836             bb_ann (tmp)->forwardable = 1;
3837
3838           if (dest == e->dest)
3839             continue;
3840
3841           old = find_edge (bb, dest);
3842           if (old)
3843             {
3844               /* If there already is an edge, check whether the values
3845                  in phi nodes differ.  */
3846               if (!phi_alternatives_equal (dest, last, old))
3847                 {
3848                   /* The previous block is forwarder.  Redirect our jump
3849                      to that target instead since we know it has no PHI
3850                      nodes that will need updating.  */
3851                   dest = last->src;
3852
3853                   /* That might mean that no forwarding at all is possible.  */
3854                   if (dest == e->dest)
3855                     continue;
3856
3857                   old = find_edge (bb, dest);
3858                 }
3859             }
3860
3861           /* Perform the redirection.  */
3862           retval = true;
3863           e = redirect_edge_and_branch (e, dest);
3864
3865           /* TODO -- updating dominators in this case is simple.  */
3866           free_dominance_info (CDI_DOMINATORS);
3867
3868           if (!old)
3869             {
3870               /* Update PHI nodes.   We know that the new argument should
3871                  have the same value as the argument associated with LAST.
3872                  Otherwise we would have changed our target block above.  */
3873               for (phi = phi_nodes (dest); phi; phi = TREE_CHAIN (phi))
3874                 {
3875                   arg = phi_arg_from_edge (phi, last);
3876                   if (arg < 0)
3877                     abort ();
3878                   add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
3879                 }
3880             }
3881         }
3882
3883       /* Reset the forwardable bit on our block since it's no longer in
3884          a forwarding chain path.  */
3885       bb_ann (bb)->forwardable = 1;
3886     }
3887
3888   return retval;
3889 }
3890
3891
3892 /* Return a non-special label in the head of basic block BLOCK.
3893    Create one if it doesn't exist.  */
3894
3895 static tree
3896 tree_block_label (basic_block bb)
3897 {
3898   block_stmt_iterator i, s = bsi_start (bb);
3899   bool first = true;
3900   tree label, stmt;
3901
3902   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
3903     {
3904       stmt = bsi_stmt (i);
3905       if (TREE_CODE (stmt) != LABEL_EXPR)
3906         break;
3907       label = LABEL_EXPR_LABEL (stmt);
3908       if (!DECL_NONLOCAL (label))
3909         {
3910           if (!first)
3911             bsi_move_before (&i, &s);
3912           return label;
3913         }
3914     }
3915
3916   label = create_artificial_label ();
3917   stmt = build1 (LABEL_EXPR, void_type_node, label);
3918   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
3919   return label;
3920 }
3921
3922
3923 /* Attempt to perform edge redirection by replacing a possibly complex
3924    jump instruction by a goto or by removing the jump completely.
3925    This can apply only if all edges now point to the same block.  The
3926    parameters and return values are equivalent to
3927    redirect_edge_and_branch.  */
3928
3929 static edge
3930 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
3931 {
3932   basic_block src = e->src;
3933   edge tmp;
3934   block_stmt_iterator b;
3935   tree stmt;
3936
3937   /* Verify that all targets will be TARGET.  */
3938   for (tmp = src->succ; tmp; tmp = tmp->succ_next)
3939     if (tmp->dest != target && tmp != e)
3940       break;
3941
3942   if (tmp)
3943     return NULL;
3944
3945   b = bsi_last (src);
3946   if (bsi_end_p (b))
3947     return NULL;
3948   stmt = bsi_stmt (b);
3949
3950   if (TREE_CODE (stmt) == COND_EXPR
3951       || TREE_CODE (stmt) == SWITCH_EXPR)
3952     {
3953       bsi_remove (&b);
3954       e = ssa_redirect_edge (e, target);
3955       e->flags = EDGE_FALLTHRU;
3956       return e;
3957     }
3958
3959   return NULL;
3960 }
3961
3962
3963 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
3964    edge representing the redirected branch.  */
3965
3966 static edge
3967 tree_redirect_edge_and_branch (edge e, basic_block dest)
3968 {
3969   basic_block bb = e->src;
3970   block_stmt_iterator bsi;
3971   edge ret;
3972   tree label, stmt;
3973
3974   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
3975     return NULL;
3976
3977   if (e->src != ENTRY_BLOCK_PTR
3978       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
3979     return ret;
3980
3981   if (e->dest == dest)
3982     return NULL;
3983
3984   label = tree_block_label (dest);
3985
3986   bsi = bsi_last (bb);
3987   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
3988
3989   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
3990     {
3991     case COND_EXPR:
3992       stmt = (e->flags & EDGE_TRUE_VALUE
3993               ? COND_EXPR_THEN (stmt)
3994               : COND_EXPR_ELSE (stmt));
3995       GOTO_DESTINATION (stmt) = label;
3996       break;
3997
3998     case GOTO_EXPR:
3999       /* No non-abnormal edges should lead from a non-simple goto, and
4000          simple ones should be represented implicitly.  */
4001       abort ();
4002
4003     case SWITCH_EXPR:
4004       {
4005         tree vec = SWITCH_LABELS (stmt);
4006         size_t i, n = TREE_VEC_LENGTH (vec);
4007
4008         for (i = 0; i < n; ++i)
4009           {
4010             tree elt = TREE_VEC_ELT (vec, i);
4011             if (label_to_block (CASE_LABEL (elt)) == e->dest)
4012               CASE_LABEL (elt) = label;
4013           }
4014       }
4015       break;
4016
4017     case RETURN_EXPR:
4018       bsi_remove (&bsi);
4019       e->flags |= EDGE_FALLTHRU;
4020       break;
4021
4022     default:
4023       /* Otherwise it must be a fallthru edge, and we don't need to
4024          do anything besides redirecting it.  */
4025       if (!(e->flags & EDGE_FALLTHRU))
4026         abort ();
4027       break;
4028     }
4029
4030   /* Update/insert PHI nodes as necessary.  */
4031
4032   /* Now update the edges in the CFG.  */
4033   e = ssa_redirect_edge (e, dest);
4034
4035   return e;
4036 }
4037
4038
4039 /* Simple wrapper, as we can always redirect fallthru edges.  */
4040
4041 static basic_block
4042 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4043 {
4044   e = tree_redirect_edge_and_branch (e, dest);
4045   if (!e)
4046     abort ();
4047
4048   return NULL;
4049 }
4050
4051
4052 /* Splits basic block BB after statement STMT (but at least after the
4053    labels).  If STMT is NULL, BB is split just after the labels.  */
4054
4055 static basic_block
4056 tree_split_block (basic_block bb, void *stmt)
4057 {
4058   block_stmt_iterator bsi, bsi_tgt;
4059   tree act;
4060   basic_block new_bb;
4061   edge e;
4062
4063   new_bb = create_empty_bb (bb);
4064
4065   /* Redirect the outgoing edges.  */
4066   new_bb->succ = bb->succ;
4067   bb->succ = NULL;
4068   for (e = new_bb->succ; e; e = e->succ_next)
4069     e->src = new_bb;
4070
4071   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4072     stmt = NULL;
4073
4074   /* Move everything from BSI to the new basic block.  */
4075   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4076     {
4077       act = bsi_stmt (bsi);
4078       if (TREE_CODE (act) == LABEL_EXPR)
4079         continue;
4080
4081       if (!stmt)
4082         break;
4083
4084       if (stmt == act)
4085         {
4086           bsi_next (&bsi);
4087           break;
4088         }
4089     }
4090
4091   bsi_tgt = bsi_start (new_bb);
4092   while (!bsi_end_p (bsi))
4093     {
4094       act = bsi_stmt (bsi);
4095       bsi_remove (&bsi);
4096       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
4097     }
4098
4099   return new_bb;
4100 }
4101
4102
4103 /* Moves basic block BB after block AFTER.  */
4104
4105 static bool
4106 tree_move_block_after (basic_block bb, basic_block after)
4107 {
4108   if (bb->prev_bb == after)
4109     return true;
4110
4111   unlink_block (bb);
4112   link_block (bb, after);
4113
4114   return true;
4115 }
4116
4117
4118 /* Return true if basic_block can be duplicated.  */
4119
4120 static bool
4121 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4122 {
4123   return true;
4124 }
4125
4126
4127 /* Create a duplicate of the basic block BB.  NOTE: This does not
4128    preserve SSA form.  */
4129
4130 static basic_block
4131 tree_duplicate_bb (basic_block bb)
4132 {
4133   basic_block new_bb;
4134   block_stmt_iterator bsi, bsi_tgt;
4135
4136   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4137   bsi_tgt = bsi_start (new_bb);
4138   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4139     {
4140       tree stmt = bsi_stmt (bsi);
4141
4142       if (TREE_CODE (stmt) == LABEL_EXPR)
4143         continue;
4144
4145       bsi_insert_after (&bsi_tgt, unshare_expr (stmt), BSI_NEW_STMT);
4146     }
4147
4148   return new_bb;
4149 }
4150
4151
4152 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4153
4154 void
4155 dump_function_to_file (tree fn, FILE *file, int flags)
4156 {
4157   tree arg, vars, var;
4158   bool ignore_topmost_bind = false, any_var = false;
4159   basic_block bb;
4160   tree chain;
4161
4162   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4163
4164   arg = DECL_ARGUMENTS (fn);
4165   while (arg)
4166     {
4167       print_generic_expr (file, arg, dump_flags);
4168       if (TREE_CHAIN (arg))
4169         fprintf (file, ", ");
4170       arg = TREE_CHAIN (arg);
4171     }
4172   fprintf (file, ")\n");
4173
4174   if (flags & TDF_RAW)
4175     {
4176       dump_node (fn, TDF_SLIM | flags, file);
4177       return;
4178     }
4179
4180   /* When GIMPLE is lowered, the variables are no longer available in
4181      BIND_EXPRs, so display them separately.  */
4182   if (cfun && cfun->unexpanded_var_list)
4183     {
4184       ignore_topmost_bind = true;
4185
4186       fprintf (file, "{\n");
4187       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
4188         {
4189           var = TREE_VALUE (vars);
4190
4191           print_generic_decl (file, var, flags);
4192           fprintf (file, "\n");
4193
4194           any_var = true;
4195         }
4196     }
4197
4198   if (basic_block_info)
4199     {
4200       /* Make a CFG based dump.  */
4201       if (!ignore_topmost_bind)
4202         fprintf (file, "{\n");
4203
4204       if (any_var && n_basic_blocks)
4205         fprintf (file, "\n");
4206
4207       FOR_EACH_BB (bb)
4208         dump_generic_bb (file, bb, 2, flags);
4209
4210       fprintf (file, "}\n");
4211     }
4212   else
4213     {
4214       int indent;
4215
4216       /* Make a tree based dump.  */
4217       chain = DECL_SAVED_TREE (fn);
4218
4219       if (TREE_CODE (chain) == BIND_EXPR)
4220         {
4221           if (ignore_topmost_bind)
4222             {
4223               chain = BIND_EXPR_BODY (chain);
4224               indent = 2;
4225             }
4226           else
4227             indent = 0;
4228         }
4229       else
4230         {
4231           if (!ignore_topmost_bind)
4232             fprintf (file, "{\n");
4233           indent = 2;
4234         }
4235
4236       if (any_var)
4237         fprintf (file, "\n");
4238
4239       print_generic_stmt_indented (file, chain, flags, indent);
4240       if (ignore_topmost_bind)
4241         fprintf (file, "}\n");
4242     }
4243
4244   fprintf (file, "\n\n");
4245 }
4246
4247
4248 /* Pretty print of the loops intermediate representation.  */
4249 static void print_loop (FILE *, struct loop *, int);
4250 static void print_pred_bbs (FILE *, edge);
4251 static void print_succ_bbs (FILE *, edge);
4252
4253
4254 /* Print the predecessors indexes of edge E on FILE.  */
4255
4256 static void
4257 print_pred_bbs (FILE *file, edge e)
4258 {
4259   if (e == NULL)
4260     return;
4261
4262   else if (e->pred_next == NULL)
4263     fprintf (file, "bb_%d", e->src->index);
4264
4265   else
4266     {
4267       fprintf (file, "bb_%d, ", e->src->index);
4268       print_pred_bbs (file, e->pred_next);
4269     }
4270 }
4271
4272
4273 /* Print the successors indexes of edge E on FILE.  */
4274
4275 static void
4276 print_succ_bbs (FILE *file, edge e)
4277 {
4278   if (e == NULL)
4279     return;
4280   else if (e->succ_next == NULL)
4281     fprintf (file, "bb_%d", e->dest->index);
4282   else
4283     {
4284       fprintf (file, "bb_%d, ", e->dest->index);
4285       print_succ_bbs (file, e->succ_next);
4286     }
4287 }
4288
4289
4290 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
4291
4292 static void
4293 print_loop (FILE *file, struct loop *loop, int indent)
4294 {
4295   char *s_indent;
4296   basic_block bb;
4297
4298   if (loop == NULL)
4299     return;
4300
4301   s_indent = (char *) alloca ((size_t) indent + 1);
4302   memset ((void *) s_indent, ' ', (size_t) indent);
4303   s_indent[indent] = '\0';
4304
4305   /* Print the loop's header.  */
4306   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
4307
4308   /* Print the loop's body.  */
4309   fprintf (file, "%s{\n", s_indent);
4310   FOR_EACH_BB (bb)
4311     if (bb->loop_father == loop)
4312       {
4313         /* Print the basic_block's header.  */
4314         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
4315         print_pred_bbs (file, bb->pred);
4316         fprintf (file, "}, succs = {");
4317         print_succ_bbs (file, bb->succ);
4318         fprintf (file, "})\n");
4319
4320         /* Print the basic_block's body.  */
4321         fprintf (file, "%s  {\n", s_indent);
4322         tree_dump_bb (bb, file, indent + 4);
4323         fprintf (file, "%s  }\n", s_indent);
4324       }
4325
4326   print_loop (file, loop->inner, indent + 2);
4327   fprintf (file, "%s}\n", s_indent);
4328   print_loop (file, loop->next, indent);
4329 }
4330
4331
4332 /* Follow a CFG edge from the entry point of the program, and on entry
4333    of a loop, pretty print the loop structure on FILE.  */
4334
4335 void
4336 print_loop_ir (FILE *file)
4337 {
4338   basic_block bb;
4339
4340   bb = BASIC_BLOCK (0);
4341   if (bb && bb->loop_father)
4342     print_loop (file, bb->loop_father, 0);
4343 }
4344
4345
4346 /* Debugging loops structure at tree level.  */
4347
4348 void
4349 debug_loop_ir (void)
4350 {
4351   print_loop_ir (stderr);
4352 }
4353
4354
4355 /* Return true if BB ends with a call, possibly followed by some
4356    instructions that must stay with the call.  Return false,
4357    otherwise.  */
4358
4359 static bool
4360 tree_block_ends_with_call_p (basic_block bb)
4361 {
4362   block_stmt_iterator bsi = bsi_last (bb);
4363   tree t = tsi_stmt (bsi.tsi);
4364
4365   if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
4366     t = TREE_OPERAND (t, 0);
4367
4368   if (TREE_CODE (t) == MODIFY_EXPR)
4369     t = TREE_OPERAND (t, 1);
4370
4371   return TREE_CODE (t) == CALL_EXPR;
4372 }
4373
4374
4375 /* Return true if BB ends with a conditional branch.  Return false,
4376    otherwise.  */
4377
4378 static bool
4379 tree_block_ends_with_condjump_p (basic_block bb)
4380 {
4381   tree stmt = tsi_stmt (bsi_last (bb).tsi);
4382   return (TREE_CODE (stmt) == COND_EXPR);
4383 }
4384
4385
4386 /* Return true if we need to add fake edge to exit at statement T.
4387    Helper function for tree_flow_call_edges_add.  */
4388
4389 static bool
4390 need_fake_edge_p (tree t)
4391 {
4392   if (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0))
4393     t = TREE_OPERAND (t, 0);
4394
4395   if (TREE_CODE (t) == MODIFY_EXPR)
4396     t = TREE_OPERAND (t, 1);
4397
4398   /* NORETURN and LONGJMP calls already have an edge to exit.
4399      CONST, PURE and ALWAYS_RETURN calls do not need one.
4400      We don't currently check for CONST and PURE here, although
4401      it would be a good idea, because those attributes are
4402      figured out from the RTL in mark_constant_function, and
4403      the counter incrementation code from -fprofile-arcs
4404      leads to different results from -fbranch-probabilities.  */
4405   if (TREE_CODE (t) == CALL_EXPR
4406       && !(call_expr_flags (t) &
4407             (ECF_NORETURN | ECF_LONGJMP | ECF_ALWAYS_RETURN)))
4408     return true;
4409
4410   if (TREE_CODE (t) == ASM_EXPR
4411        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
4412     return true;
4413
4414   return false;
4415 }
4416
4417
4418 /* Add fake edges to the function exit for any non constant and non
4419    noreturn calls, volatile inline assembly in the bitmap of blocks
4420    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
4421    the number of blocks that were split.
4422
4423    The goal is to expose cases in which entering a basic block does
4424    not imply that all subsequent instructions must be executed.  */
4425
4426 static int
4427 tree_flow_call_edges_add (sbitmap blocks)
4428 {
4429   int i;
4430   int blocks_split = 0;
4431   int last_bb = last_basic_block;
4432   bool check_last_block = false;
4433
4434   if (n_basic_blocks == 0)
4435     return 0;
4436
4437   if (! blocks)
4438     check_last_block = true;
4439   else
4440     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
4441
4442   /* In the last basic block, before epilogue generation, there will be
4443      a fallthru edge to EXIT.  Special care is required if the last insn
4444      of the last basic block is a call because make_edge folds duplicate
4445      edges, which would result in the fallthru edge also being marked
4446      fake, which would result in the fallthru edge being removed by
4447      remove_fake_edges, which would result in an invalid CFG.
4448
4449      Moreover, we can't elide the outgoing fake edge, since the block
4450      profiler needs to take this into account in order to solve the minimal
4451      spanning tree in the case that the call doesn't return.
4452
4453      Handle this by adding a dummy instruction in a new last basic block.  */
4454   if (check_last_block)
4455     {
4456       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
4457       block_stmt_iterator bsi = bsi_last (bb);
4458       tree t = NULL_TREE;
4459       if (!bsi_end_p (bsi))
4460         t = bsi_stmt (bsi);
4461
4462       if (need_fake_edge_p (t))
4463         {
4464           edge e;
4465
4466           for (e = bb->succ; e; e = e->succ_next)
4467             if (e->dest == EXIT_BLOCK_PTR)
4468               {
4469                 bsi_insert_on_edge (e, build_empty_stmt ());
4470                 bsi_commit_edge_inserts ((int *)NULL);
4471                 break;
4472               }
4473         }
4474     }
4475
4476   /* Now add fake edges to the function exit for any non constant
4477      calls since there is no way that we can determine if they will
4478      return or not...  */
4479   for (i = 0; i < last_bb; i++)
4480     {
4481       basic_block bb = BASIC_BLOCK (i);
4482       block_stmt_iterator bsi;
4483       tree stmt, last_stmt;
4484
4485       if (!bb)
4486         continue;
4487
4488       if (blocks && !TEST_BIT (blocks, i))
4489         continue;
4490
4491       bsi = bsi_last (bb);
4492       if (!bsi_end_p (bsi))
4493         {
4494           last_stmt = bsi_stmt (bsi);
4495           do
4496             {
4497               stmt = bsi_stmt (bsi);
4498               if (need_fake_edge_p (stmt))
4499                 {
4500                   edge e;
4501                   /* The handling above of the final block before the
4502                      epilogue should be enough to verify that there is
4503                      no edge to the exit block in CFG already.
4504                      Calling make_edge in such case would cause us to
4505                      mark that edge as fake and remove it later.  */
4506 #ifdef ENABLE_CHECKING
4507                   if (stmt == last_stmt)
4508                     for (e = bb->succ; e; e = e->succ_next)
4509                       if (e->dest == EXIT_BLOCK_PTR)
4510                         abort ();
4511 #endif
4512
4513                   /* Note that the following may create a new basic block
4514                      and renumber the existing basic blocks.  */
4515                   if (stmt != last_stmt)
4516                     {
4517                       e = split_block (bb, stmt);
4518                       if (e)
4519                         blocks_split++;
4520                     }
4521                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
4522                 }
4523               bsi_prev (&bsi);
4524             }
4525           while (!bsi_end_p (bsi));
4526         }
4527     }
4528
4529   if (blocks_split)
4530     verify_flow_info ();
4531
4532   return blocks_split;
4533 }
4534
4535
4536 struct cfg_hooks tree_cfg_hooks = {
4537   "tree",
4538   tree_verify_flow_info,
4539   tree_dump_bb,                 /* dump_bb  */
4540   create_bb,                    /* create_basic_block  */
4541   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
4542   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
4543   remove_bb,                    /* delete_basic_block  */
4544   tree_split_block,             /* split_block  */
4545   tree_move_block_after,        /* move_block_after  */
4546   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
4547   tree_merge_blocks,            /* merge_blocks  */
4548   tree_predict_edge,            /* predict_edge  */
4549   tree_predicted_by_p,          /* predicted_by_p  */
4550   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
4551   tree_duplicate_bb,            /* duplicate_block  */
4552   tree_split_edge,              /* split_edge  */
4553   tree_make_forwarder_block,    /* make_forward_block  */
4554   NULL,                         /* tidy_fallthru_edge  */
4555   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
4556   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
4557   tree_flow_call_edges_add      /* flow_call_edges_add */
4558 };
4559
4560
4561 /* Split all critical edges.  */
4562
4563 static void
4564 split_critical_edges (void)
4565 {
4566   basic_block bb;
4567   edge e;
4568
4569   FOR_ALL_BB (bb)
4570     {
4571       for (e = bb->succ; e ; e = e->succ_next)
4572         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
4573           {
4574             split_edge (e);
4575           }
4576     }
4577 }
4578
4579 struct tree_opt_pass pass_split_crit_edges =
4580 {
4581   NULL,                          /* name */
4582   NULL,                          /* gate */
4583   split_critical_edges,          /* execute */
4584   NULL,                          /* sub */
4585   NULL,                          /* next */
4586   0,                             /* static_pass_number */
4587   TV_TREE_SPLIT_EDGES,           /* tv_id */
4588   PROP_cfg,                      /* properties required */
4589   PROP_no_crit_edges,            /* properties_provided */
4590   0,                             /* properties_destroyed */
4591   0,                             /* todo_flags_start */
4592   0,                             /* todo_flags_finish */
4593 };
4594 \f
4595 /* Emit return warnings.  */
4596
4597 static void
4598 execute_warn_function_return (void)
4599 {
4600   location_t *locus;
4601   tree last;
4602   edge e;
4603
4604   if (warn_missing_noreturn
4605       && !TREE_THIS_VOLATILE (cfun->decl)
4606       && EXIT_BLOCK_PTR->pred == NULL
4607       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
4608     warning ("%Jfunction might be possible candidate for attribute `noreturn'",
4609              cfun->decl);
4610
4611   /* If we have a path to EXIT, then we do return.  */
4612   if (TREE_THIS_VOLATILE (cfun->decl)
4613       && EXIT_BLOCK_PTR->pred != NULL)
4614     {
4615       locus = NULL;
4616       for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
4617         {
4618           last = last_stmt (e->src);
4619           if (TREE_CODE (last) == RETURN_EXPR
4620               && (locus = EXPR_LOCUS (last)) != NULL)
4621             break;
4622         }
4623       if (!locus)
4624         locus = &cfun->function_end_locus;
4625       warning ("%H`noreturn' function does return", locus);
4626     }
4627
4628   /* If we see "return;" in some basic block, then we do reach the end
4629      without returning a value.  */
4630   else if (warn_return_type
4631            && EXIT_BLOCK_PTR->pred != NULL
4632            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
4633     {
4634       for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
4635         {
4636           tree last = last_stmt (e->src);
4637           if (TREE_CODE (last) == RETURN_EXPR
4638               && TREE_OPERAND (last, 0) == NULL)
4639             {
4640               locus = EXPR_LOCUS (last);
4641               if (!locus)
4642                 locus = &cfun->function_end_locus;
4643               warning ("%Hcontrol reaches end of non-void function", locus);
4644               break;
4645             }
4646         }
4647     }
4648 }
4649
4650
4651 /* Given a basic block B which ends with a conditional and has
4652    precisely two successors, determine which of the edges is taken if
4653    the conditional is true and which is taken if the conditional is
4654    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
4655
4656 void
4657 extract_true_false_edges_from_block (basic_block b,
4658                                      edge *true_edge,
4659                                      edge *false_edge)
4660 {
4661   edge e = b->succ;
4662
4663   if (e->flags & EDGE_TRUE_VALUE)
4664     {
4665       *true_edge = e;
4666       *false_edge = e->succ_next;
4667     }
4668   else
4669     {
4670       *false_edge = e;
4671       *true_edge = e->succ_next;
4672     }
4673 }
4674
4675 struct tree_opt_pass pass_warn_function_return =
4676 {
4677   NULL,                                 /* name */
4678   NULL,                                 /* gate */
4679   execute_warn_function_return,         /* execute */
4680   NULL,                                 /* sub */
4681   NULL,                                 /* next */
4682   0,                                    /* static_pass_number */
4683   0,                                    /* tv_id */
4684   PROP_ssa,                             /* properties_required */
4685   0,                                    /* properties_provided */
4686   0,                                    /* properties_destroyed */
4687   0,                                    /* todo_flags_start */
4688   0                                     /* todo_flags_finish */
4689 };
4690
4691 #include "gt-tree-cfg.h"