gcc/tree-cfg.c

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