gcc/tree-cfg.c

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