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    If specified, NEW_BLOCKS returns a count of the number of new basic
3011    blocks which were created.  */
3012
3013 void
3014 bsi_commit_edge_inserts (int *new_blocks)
3015 {
3016   basic_block bb;
3017   edge e;
3018   int blocks;
3019   edge_iterator ei;
3020
3021   blocks = n_basic_blocks;
3022
3023   bsi_commit_one_edge_insert (EDGE_SUCC (ENTRY_BLOCK_PTR, 0), NULL);
3024
3025   FOR_EACH_BB (bb)
3026     FOR_EACH_EDGE (e, ei, bb->succs)
3027       bsi_commit_one_edge_insert (e, NULL);
3028
3029   if (new_blocks)
3030     *new_blocks = n_basic_blocks - blocks;
3031 }
3032
3033
3034 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
3035    to this block, otherwise set it to NULL.  */
3036
3037 void
3038 bsi_commit_one_edge_insert (edge e, basic_block *new_bb)
3039 {
3040   if (new_bb)
3041     *new_bb = NULL;
3042   if (PENDING_STMT (e))
3043     {
3044       block_stmt_iterator bsi;
3045       tree stmt = PENDING_STMT (e);
3046
3047       PENDING_STMT (e) = NULL_TREE;
3048
3049       if (tree_find_edge_insert_loc (e, &bsi, new_bb))
3050         bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3051       else
3052         bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3053     }
3054 }
3055
3056
3057 /* Add STMT to the pending list of edge E.  No actual insertion is
3058    made until a call to bsi_commit_edge_inserts () is made.  */
3059
3060 void
3061 bsi_insert_on_edge (edge e, tree stmt)
3062 {
3063   append_to_statement_list (stmt, &PENDING_STMT (e));
3064 }
3065
3066 /* Similar to bsi_insert_on_edge+bsi_commit_edge_inserts.  If new block has to
3067    be created, it is returned.  */
3068
3069 basic_block
3070 bsi_insert_on_edge_immediate (edge e, tree stmt)
3071 {
3072   block_stmt_iterator bsi;
3073   basic_block new_bb = NULL;
3074
3075   gcc_assert (!PENDING_STMT (e));
3076
3077   if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
3078     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
3079   else
3080     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
3081
3082   return new_bb;
3083 }
3084
3085 /*---------------------------------------------------------------------------
3086              Tree specific functions for CFG manipulation
3087 ---------------------------------------------------------------------------*/
3088
3089 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
3090    Abort on abnormal edges.  */
3091
3092 static basic_block
3093 tree_split_edge (edge edge_in)
3094 {
3095   basic_block new_bb, after_bb, dest, src;
3096   edge new_edge, e;
3097   tree phi;
3098   int i, num_elem;
3099   edge_iterator ei;
3100
3101   /* Abnormal edges cannot be split.  */
3102   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
3103
3104   src = edge_in->src;
3105   dest = edge_in->dest;
3106
3107   /* Place the new block in the block list.  Try to keep the new block
3108      near its "logical" location.  This is of most help to humans looking
3109      at debugging dumps.  */
3110   FOR_EACH_EDGE (e, ei, dest->preds)
3111     if (e->src->next_bb == dest)
3112       break;
3113   if (!e)
3114     after_bb = dest->prev_bb;
3115   else
3116     after_bb = edge_in->src;
3117
3118   new_bb = create_empty_bb (after_bb);
3119   new_bb->frequency = EDGE_FREQUENCY (edge_in);
3120   new_bb->count = edge_in->count;
3121   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
3122   new_edge->probability = REG_BR_PROB_BASE;
3123   new_edge->count = edge_in->count;
3124
3125   /* Find all the PHI arguments on the original edge, and change them to
3126      the new edge.  Do it before redirection, so that the argument does not
3127      get removed.  */
3128   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
3129     {
3130       num_elem = PHI_NUM_ARGS (phi);
3131       for (i = 0; i < num_elem; i++)
3132         if (PHI_ARG_EDGE (phi, i) == edge_in)
3133           {
3134             PHI_ARG_EDGE (phi, i) = new_edge;
3135             break;
3136           }
3137     }
3138
3139   e = redirect_edge_and_branch (edge_in, new_bb);
3140   gcc_assert (e);
3141   gcc_assert (!PENDING_STMT (edge_in));
3142
3143   return new_bb;
3144 }
3145
3146
3147 /* Return true when BB has label LABEL in it.  */
3148
3149 static bool
3150 has_label_p (basic_block bb, tree label)
3151 {
3152   block_stmt_iterator bsi;
3153
3154   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3155     {
3156       tree stmt = bsi_stmt (bsi);
3157
3158       if (TREE_CODE (stmt) != LABEL_EXPR)
3159         return false;
3160       if (LABEL_EXPR_LABEL (stmt) == label)
3161         return true;
3162     }
3163   return false;
3164 }
3165
3166
3167 /* Callback for walk_tree, check that all elements with address taken are
3168    properly noticed as such.  */
3169
3170 static tree
3171 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
3172 {
3173   tree t = *tp, x;
3174
3175   if (TYPE_P (t))
3176     *walk_subtrees = 0;
3177
3178   /* Check operand N for being valid GIMPLE and give error MSG if not.
3179      We check for constants explicitly since they are not considered
3180      gimple invariants if they overflowed.  */
3181 #define CHECK_OP(N, MSG) \
3182   do { if (!CONSTANT_CLASS_P (TREE_OPERAND (t, N))              \
3183          && !is_gimple_val (TREE_OPERAND (t, N)))               \
3184        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
3185
3186   switch (TREE_CODE (t))
3187     {
3188     case SSA_NAME:
3189       if (SSA_NAME_IN_FREE_LIST (t))
3190         {
3191           error ("SSA name in freelist but still referenced");
3192           return *tp;
3193         }
3194       break;
3195
3196     case MODIFY_EXPR:
3197       x = TREE_OPERAND (t, 0);
3198       if (TREE_CODE (x) == BIT_FIELD_REF
3199           && is_gimple_reg (TREE_OPERAND (x, 0)))
3200         {
3201           error ("GIMPLE register modified with BIT_FIELD_REF");
3202           return t;
3203         }
3204       break;
3205
3206     case ADDR_EXPR:
3207       /* Skip any references (they will be checked when we recurse down the
3208          tree) and ensure that any variable used as a prefix is marked
3209          addressable.  */
3210       for (x = TREE_OPERAND (t, 0);
3211            (handled_component_p (x)
3212             || TREE_CODE (x) == REALPART_EXPR
3213             || TREE_CODE (x) == IMAGPART_EXPR);
3214            x = TREE_OPERAND (x, 0))
3215         ;
3216
3217       if (TREE_CODE (x) != VAR_DECL && TREE_CODE (x) != PARM_DECL)
3218         return NULL;
3219       if (!TREE_ADDRESSABLE (x))
3220         {
3221           error ("address taken, but ADDRESSABLE bit not set");
3222           return x;
3223         }
3224       break;
3225
3226     case COND_EXPR:
3227       x = TREE_OPERAND (t, 0);
3228       if (TREE_CODE (TREE_TYPE (x)) != BOOLEAN_TYPE)
3229         {
3230           error ("non-boolean used in condition");
3231           return x;
3232         }
3233       break;
3234
3235     case NOP_EXPR:
3236     case CONVERT_EXPR:
3237     case FIX_TRUNC_EXPR:
3238     case FIX_CEIL_EXPR:
3239     case FIX_FLOOR_EXPR:
3240     case FIX_ROUND_EXPR:
3241     case FLOAT_EXPR:
3242     case NEGATE_EXPR:
3243     case ABS_EXPR:
3244     case BIT_NOT_EXPR:
3245     case NON_LVALUE_EXPR:
3246     case TRUTH_NOT_EXPR:
3247       CHECK_OP (0, "Invalid operand to unary operator");
3248       break;
3249
3250     case REALPART_EXPR:
3251     case IMAGPART_EXPR:
3252     case COMPONENT_REF:
3253     case ARRAY_REF:
3254     case ARRAY_RANGE_REF:
3255     case BIT_FIELD_REF:
3256     case VIEW_CONVERT_EXPR:
3257       /* We have a nest of references.  Verify that each of the operands
3258          that determine where to reference is either a constant or a variable,
3259          verify that the base is valid, and then show we've already checked
3260          the subtrees.  */
3261       while (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR
3262              || handled_component_p (t))
3263         {
3264           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
3265             CHECK_OP (2, "Invalid COMPONENT_REF offset operator");
3266           else if (TREE_CODE (t) == ARRAY_REF
3267                    || TREE_CODE (t) == ARRAY_RANGE_REF)
3268             {
3269               CHECK_OP (1, "Invalid array index.");
3270               if (TREE_OPERAND (t, 2))
3271                 CHECK_OP (2, "Invalid array lower bound.");
3272               if (TREE_OPERAND (t, 3))
3273                 CHECK_OP (3, "Invalid array stride.");
3274             }
3275           else if (TREE_CODE (t) == BIT_FIELD_REF)
3276             {
3277               CHECK_OP (1, "Invalid operand to BIT_FIELD_REF");
3278               CHECK_OP (2, "Invalid operand to BIT_FIELD_REF");
3279             }
3280
3281           t = TREE_OPERAND (t, 0);
3282         }
3283
3284       if (!CONSTANT_CLASS_P (t) && !is_gimple_lvalue (t))
3285         {
3286           error ("Invalid reference prefix.");
3287           return t;
3288         }
3289       *walk_subtrees = 0;
3290       break;
3291
3292     case LT_EXPR:
3293     case LE_EXPR:
3294     case GT_EXPR:
3295     case GE_EXPR:
3296     case EQ_EXPR:
3297     case NE_EXPR:
3298     case UNORDERED_EXPR:
3299     case ORDERED_EXPR:
3300     case UNLT_EXPR:
3301     case UNLE_EXPR:
3302     case UNGT_EXPR:
3303     case UNGE_EXPR:
3304     case UNEQ_EXPR:
3305     case LTGT_EXPR:
3306     case PLUS_EXPR:
3307     case MINUS_EXPR:
3308     case MULT_EXPR:
3309     case TRUNC_DIV_EXPR:
3310     case CEIL_DIV_EXPR:
3311     case FLOOR_DIV_EXPR:
3312     case ROUND_DIV_EXPR:
3313     case TRUNC_MOD_EXPR:
3314     case CEIL_MOD_EXPR:
3315     case FLOOR_MOD_EXPR:
3316     case ROUND_MOD_EXPR:
3317     case RDIV_EXPR:
3318     case EXACT_DIV_EXPR:
3319     case MIN_EXPR:
3320     case MAX_EXPR:
3321     case LSHIFT_EXPR:
3322     case RSHIFT_EXPR:
3323     case LROTATE_EXPR:
3324     case RROTATE_EXPR:
3325     case BIT_IOR_EXPR:
3326     case BIT_XOR_EXPR:
3327     case BIT_AND_EXPR:
3328       CHECK_OP (0, "Invalid operand to binary operator");
3329       CHECK_OP (1, "Invalid operand to binary operator");
3330       break;
3331
3332     default:
3333       break;
3334     }
3335   return NULL;
3336
3337 #undef CHECK_OP
3338 }
3339
3340
3341 /* Verify STMT, return true if STMT is not in GIMPLE form.
3342    TODO: Implement type checking.  */
3343
3344 static bool
3345 verify_stmt (tree stmt, bool last_in_block)
3346 {
3347   tree addr;
3348
3349   if (!is_gimple_stmt (stmt))
3350     {
3351       error ("Is not a valid GIMPLE statement.");
3352       goto fail;
3353     }
3354
3355   addr = walk_tree (&stmt, verify_expr, NULL, NULL);
3356   if (addr)
3357     {
3358       debug_generic_stmt (addr);
3359       return true;
3360     }
3361
3362   /* If the statement is marked as part of an EH region, then it is
3363      expected that the statement could throw.  Verify that when we
3364      have optimizations that simplify statements such that we prove
3365      that they cannot throw, that we update other data structures
3366      to match.  */
3367   if (lookup_stmt_eh_region (stmt) >= 0)
3368     {
3369       if (!tree_could_throw_p (stmt))
3370         {
3371           error ("Statement marked for throw, but doesn%'t.");
3372           goto fail;
3373         }
3374       if (!last_in_block && tree_can_throw_internal (stmt))
3375         {
3376           error ("Statement marked for throw in middle of block.");
3377           goto fail;
3378         }
3379     }
3380
3381   return false;
3382
3383  fail:
3384   debug_generic_stmt (stmt);
3385   return true;
3386 }
3387
3388
3389 /* Return true when the T can be shared.  */
3390
3391 static bool
3392 tree_node_can_be_shared (tree t)
3393 {
3394   if (IS_TYPE_OR_DECL_P (t)
3395       /* We check for constants explicitly since they are not considered
3396          gimple invariants if they overflowed.  */
3397       || CONSTANT_CLASS_P (t)
3398       || is_gimple_min_invariant (t)
3399       || TREE_CODE (t) == SSA_NAME)
3400     return true;
3401
3402   if (TREE_CODE (t) == CASE_LABEL_EXPR)
3403     return true;
3404
3405   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
3406           /* We check for constants explicitly since they are not considered
3407              gimple invariants if they overflowed.  */
3408           && (CONSTANT_CLASS_P (TREE_OPERAND (t, 1))
3409               || is_gimple_min_invariant (TREE_OPERAND (t, 1))))
3410          || (TREE_CODE (t) == COMPONENT_REF
3411              || TREE_CODE (t) == REALPART_EXPR
3412              || TREE_CODE (t) == IMAGPART_EXPR))
3413     t = TREE_OPERAND (t, 0);
3414
3415   if (DECL_P (t))
3416     return true;
3417
3418   return false;
3419 }
3420
3421
3422 /* Called via walk_trees.  Verify tree sharing.  */
3423
3424 static tree
3425 verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
3426 {
3427   htab_t htab = (htab_t) data;
3428   void **slot;
3429
3430   if (tree_node_can_be_shared (*tp))
3431     {
3432       *walk_subtrees = false;
3433       return NULL;
3434     }
3435
3436   slot = htab_find_slot (htab, *tp, INSERT);
3437   if (*slot)
3438     return *slot;
3439   *slot = *tp;
3440
3441   return NULL;
3442 }
3443
3444
3445 /* Verify the GIMPLE statement chain.  */
3446
3447 void
3448 verify_stmts (void)
3449 {
3450   basic_block bb;
3451   block_stmt_iterator bsi;
3452   bool err = false;
3453   htab_t htab;
3454   tree addr;
3455
3456   timevar_push (TV_TREE_STMT_VERIFY);
3457   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
3458
3459   FOR_EACH_BB (bb)
3460     {
3461       tree phi;
3462       int i;
3463
3464       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3465         {
3466           int phi_num_args = PHI_NUM_ARGS (phi);
3467
3468           for (i = 0; i < phi_num_args; i++)
3469             {
3470               tree t = PHI_ARG_DEF (phi, i);
3471               tree addr;
3472
3473               /* Addressable variables do have SSA_NAMEs but they
3474                  are not considered gimple values.  */
3475               if (TREE_CODE (t) != SSA_NAME
3476                   && TREE_CODE (t) != FUNCTION_DECL
3477                   && !is_gimple_val (t))
3478                 {
3479                   error ("PHI def is not a GIMPLE value");
3480                   debug_generic_stmt (phi);
3481                   debug_generic_stmt (t);
3482                   err |= true;
3483                 }
3484
3485               addr = walk_tree (&t, verify_expr, NULL, NULL);
3486               if (addr)
3487                 {
3488                   debug_generic_stmt (addr);
3489                   err |= true;
3490                 }
3491
3492               addr = walk_tree (&t, verify_node_sharing, htab, NULL);
3493               if (addr)
3494                 {
3495                   error ("Incorrect sharing of tree nodes");
3496                   debug_generic_stmt (phi);
3497                   debug_generic_stmt (addr);
3498                   err |= true;
3499                 }
3500             }
3501         }
3502
3503       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
3504         {
3505           tree stmt = bsi_stmt (bsi);
3506           bsi_next (&bsi);
3507           err |= verify_stmt (stmt, bsi_end_p (bsi));
3508           addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
3509           if (addr)
3510             {
3511               error ("Incorrect sharing of tree nodes");
3512               debug_generic_stmt (stmt);
3513               debug_generic_stmt (addr);
3514               err |= true;
3515             }
3516         }
3517     }
3518
3519   if (err)
3520     internal_error ("verify_stmts failed.");
3521
3522   htab_delete (htab);
3523   timevar_pop (TV_TREE_STMT_VERIFY);
3524 }
3525
3526
3527 /* Verifies that the flow information is OK.  */
3528
3529 static int
3530 tree_verify_flow_info (void)
3531 {
3532   int err = 0;
3533   basic_block bb;
3534   block_stmt_iterator bsi;
3535   tree stmt;
3536   edge e;
3537   edge_iterator ei;
3538
3539   if (ENTRY_BLOCK_PTR->stmt_list)
3540     {
3541       error ("ENTRY_BLOCK has a statement list associated with it\n");
3542       err = 1;
3543     }
3544
3545   if (EXIT_BLOCK_PTR->stmt_list)
3546     {
3547       error ("EXIT_BLOCK has a statement list associated with it\n");
3548       err = 1;
3549     }
3550
3551   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
3552     if (e->flags & EDGE_FALLTHRU)
3553       {
3554         error ("Fallthru to exit from bb %d\n", e->src->index);
3555         err = 1;
3556       }
3557
3558   FOR_EACH_BB (bb)
3559     {
3560       bool found_ctrl_stmt = false;
3561
3562       /* Skip labels on the start of basic block.  */
3563       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3564         {
3565           if (TREE_CODE (bsi_stmt (bsi)) != LABEL_EXPR)
3566             break;
3567
3568           if (label_to_block (LABEL_EXPR_LABEL (bsi_stmt (bsi))) != bb)
3569             {
3570               tree stmt = bsi_stmt (bsi);
3571               error ("Label %s to block does not match in bb %d\n",
3572                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3573                      bb->index);
3574               err = 1;
3575             }
3576
3577           if (decl_function_context (LABEL_EXPR_LABEL (bsi_stmt (bsi)))
3578               != current_function_decl)
3579             {
3580               tree stmt = bsi_stmt (bsi);
3581               error ("Label %s has incorrect context in bb %d\n",
3582                      IDENTIFIER_POINTER (DECL_NAME (LABEL_EXPR_LABEL (stmt))),
3583                      bb->index);
3584               err = 1;
3585             }
3586         }
3587
3588       /* Verify that body of basic block BB is free of control flow.  */
3589       for (; !bsi_end_p (bsi); bsi_next (&bsi))
3590         {
3591           tree stmt = bsi_stmt (bsi);
3592
3593           if (found_ctrl_stmt)
3594             {
3595               error ("Control flow in the middle of basic block %d\n",
3596                      bb->index);
3597               err = 1;
3598             }
3599
3600           if (stmt_ends_bb_p (stmt))
3601             found_ctrl_stmt = true;
3602
3603           if (TREE_CODE (stmt) == LABEL_EXPR)
3604             {
3605               error ("Label %s in the middle of basic block %d\n",
3606                      IDENTIFIER_POINTER (DECL_NAME (stmt)),
3607                      bb->index);
3608               err = 1;
3609             }
3610         }
3611       bsi = bsi_last (bb);
3612       if (bsi_end_p (bsi))
3613         continue;
3614
3615       stmt = bsi_stmt (bsi);
3616
3617       if (is_ctrl_stmt (stmt))
3618         {
3619           FOR_EACH_EDGE (e, ei, bb->succs)
3620             if (e->flags & EDGE_FALLTHRU)
3621               {
3622                 error ("Fallthru edge after a control statement in bb %d \n",
3623                        bb->index);
3624                 err = 1;
3625               }
3626         }
3627
3628       switch (TREE_CODE (stmt))
3629         {
3630         case COND_EXPR:
3631           {
3632             edge true_edge;
3633             edge false_edge;
3634             if (TREE_CODE (COND_EXPR_THEN (stmt)) != GOTO_EXPR
3635                 || TREE_CODE (COND_EXPR_ELSE (stmt)) != GOTO_EXPR)
3636               {
3637                 error ("Structured COND_EXPR at the end of bb %d\n", bb->index);
3638                 err = 1;
3639               }
3640
3641             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
3642
3643             if (!true_edge || !false_edge
3644                 || !(true_edge->flags & EDGE_TRUE_VALUE)
3645                 || !(false_edge->flags & EDGE_FALSE_VALUE)
3646                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3647                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
3648                 || EDGE_COUNT (bb->succs) >= 3)
3649               {
3650                 error ("Wrong outgoing edge flags at end of bb %d\n",
3651                        bb->index);
3652                 err = 1;
3653               }
3654
3655             if (!has_label_p (true_edge->dest,
3656                               GOTO_DESTINATION (COND_EXPR_THEN (stmt))))
3657               {
3658                 error ("%<then%> label does not match edge at end of bb %d\n",
3659                        bb->index);
3660                 err = 1;
3661               }
3662
3663             if (!has_label_p (false_edge->dest,
3664                               GOTO_DESTINATION (COND_EXPR_ELSE (stmt))))
3665               {
3666                 error ("%<else%> label does not match edge at end of bb %d\n",
3667                        bb->index);
3668                 err = 1;
3669               }
3670           }
3671           break;
3672
3673         case GOTO_EXPR:
3674           if (simple_goto_p (stmt))
3675             {
3676               error ("Explicit goto at end of bb %d\n", bb->index);
3677               err = 1;
3678             }
3679           else
3680             {
3681               /* FIXME.  We should double check that the labels in the
3682                  destination blocks have their address taken.  */
3683               FOR_EACH_EDGE (e, ei, bb->succs)
3684                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
3685                                  | EDGE_FALSE_VALUE))
3686                     || !(e->flags & EDGE_ABNORMAL))
3687                   {
3688                     error ("Wrong outgoing edge flags at end of bb %d\n",
3689                            bb->index);
3690                     err = 1;
3691                   }
3692             }
3693           break;
3694
3695         case RETURN_EXPR:
3696           if (EDGE_COUNT (bb->succs) != 1
3697               || (EDGE_SUCC (bb, 0)->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3698                                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3699             {
3700               error ("Wrong outgoing edge flags at end of bb %d\n", bb->index);
3701               err = 1;
3702             }
3703           if (EDGE_SUCC (bb, 0)->dest != EXIT_BLOCK_PTR)
3704             {
3705               error ("Return edge does not point to exit in bb %d\n",
3706                      bb->index);
3707               err = 1;
3708             }
3709           break;
3710
3711         case SWITCH_EXPR:
3712           {
3713             tree prev;
3714             edge e;
3715             size_t i, n;
3716             tree vec;
3717
3718             vec = SWITCH_LABELS (stmt);
3719             n = TREE_VEC_LENGTH (vec);
3720
3721             /* Mark all the destination basic blocks.  */
3722             for (i = 0; i < n; ++i)
3723               {
3724                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3725                 basic_block label_bb = label_to_block (lab);
3726
3727                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
3728                 label_bb->aux = (void *)1;
3729               }
3730
3731             /* Verify that the case labels are sorted.  */
3732             prev = TREE_VEC_ELT (vec, 0);
3733             for (i = 1; i < n - 1; ++i)
3734               {
3735                 tree c = TREE_VEC_ELT (vec, i);
3736                 if (! CASE_LOW (c))
3737                   {
3738                     error ("Found default case not at end of case vector");
3739                     err = 1;
3740                     continue;
3741                   }
3742                 if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
3743                   {
3744                     error ("Case labels not sorted:\n ");
3745                     print_generic_expr (stderr, prev, 0);
3746                     fprintf (stderr," is greater than ");
3747                     print_generic_expr (stderr, c, 0);
3748                     fprintf (stderr," but comes before it.\n");
3749                     err = 1;
3750                   }
3751                 prev = c;
3752               }
3753             if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
3754               {
3755                 error ("No default case found at end of case vector");
3756                 err = 1;
3757               }
3758
3759             FOR_EACH_EDGE (e, ei, bb->succs)
3760               {
3761                 if (!e->dest->aux)
3762                   {
3763                     error ("Extra outgoing edge %d->%d\n",
3764                            bb->index, e->dest->index);
3765                     err = 1;
3766                   }
3767                 e->dest->aux = (void *)2;
3768                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
3769                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
3770                   {
3771                     error ("Wrong outgoing edge flags at end of bb %d\n",
3772                            bb->index);
3773                     err = 1;
3774                   }
3775               }
3776
3777             /* Check that we have all of them.  */
3778             for (i = 0; i < n; ++i)
3779               {
3780                 tree lab = CASE_LABEL (TREE_VEC_ELT (vec, i));
3781                 basic_block label_bb = label_to_block (lab);
3782
3783                 if (label_bb->aux != (void *)2)
3784                   {
3785                     error ("Missing edge %i->%i\n",
3786                            bb->index, label_bb->index);
3787                     err = 1;
3788                   }
3789               }
3790
3791             FOR_EACH_EDGE (e, ei, bb->succs)
3792               e->dest->aux = (void *)0;
3793           }
3794
3795         default: ;
3796         }
3797     }
3798
3799   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
3800     verify_dominators (CDI_DOMINATORS);
3801
3802   return err;
3803 }
3804
3805
3806 /* Updates phi nodes after creating a forwarder block joined
3807    by edge FALLTHRU.  */
3808
3809 static void
3810 tree_make_forwarder_block (edge fallthru)
3811 {
3812   edge e;
3813   edge_iterator ei;
3814   basic_block dummy, bb;
3815   tree phi, new_phi, var;
3816
3817   dummy = fallthru->src;
3818   bb = fallthru->dest;
3819
3820   if (EDGE_COUNT (bb->preds) == 1)
3821     return;
3822
3823   /* If we redirected a branch we must create new phi nodes at the
3824      start of BB.  */
3825   for (phi = phi_nodes (dummy); phi; phi = PHI_CHAIN (phi))
3826     {
3827       var = PHI_RESULT (phi);
3828       new_phi = create_phi_node (var, bb);
3829       SSA_NAME_DEF_STMT (var) = new_phi;
3830       SET_PHI_RESULT (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
3831       add_phi_arg (&new_phi, PHI_RESULT (phi), fallthru);
3832     }
3833
3834   /* Ensure that the PHI node chain is in the same order.  */
3835   set_phi_nodes (bb, phi_reverse (phi_nodes (bb)));
3836
3837   /* Add the arguments we have stored on edges.  */
3838   FOR_EACH_EDGE (e, ei, bb->preds)
3839     {
3840       if (e == fallthru)
3841         continue;
3842
3843       flush_pending_stmts (e);
3844     }
3845 }
3846
3847
3848 /* Return true if basic block BB does nothing except pass control
3849    flow to another block and that we can safely insert a label at
3850    the start of the successor block.
3851
3852    As a precondition, we require that BB be not equal to
3853    ENTRY_BLOCK_PTR.  */
3854
3855 static bool
3856 tree_forwarder_block_p (basic_block bb)
3857 {
3858   block_stmt_iterator bsi;
3859   edge e;
3860   edge_iterator ei;
3861
3862   /* BB must have a single outgoing edge.  */
3863   if (EDGE_COUNT (bb->succs) != 1
3864       /* BB can not have any PHI nodes.  This could potentially be
3865          relaxed early in compilation if we re-rewrote the variables
3866          appearing in any PHI nodes in forwarder blocks.  */
3867       || phi_nodes (bb)
3868       /* BB may not be a predecessor of EXIT_BLOCK_PTR.  */
3869       || EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR
3870       /* BB may not have an abnormal outgoing edge.  */
3871       || (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL))
3872     return false;
3873
3874 #if ENABLE_CHECKING
3875   gcc_assert (bb != ENTRY_BLOCK_PTR);
3876 #endif
3877
3878   /* Successors of the entry block are not forwarders.  */
3879   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
3880     if (e->dest == bb)
3881       return false;
3882
3883   /* Now walk through the statements.  We can ignore labels, anything else
3884      means this is not a forwarder block.  */
3885   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3886     {
3887       tree stmt = bsi_stmt (bsi);
3888
3889       switch (TREE_CODE (stmt))
3890         {
3891         case LABEL_EXPR:
3892           if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt)))
3893             return false;
3894           break;
3895
3896         default:
3897           return false;
3898         }
3899     }
3900
3901   return true;
3902 }
3903
3904 /* Thread jumps from BB.  */
3905
3906 static bool
3907 thread_jumps_from_bb (basic_block bb)
3908 {
3909   edge_iterator ei;
3910   edge e;
3911   bool retval = false;
3912
3913   /* Examine each of our block's successors to see if it is
3914      forwardable.  */
3915   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3916     {
3917       int freq;
3918       gcov_type count;
3919       edge last, old;
3920       basic_block dest, tmp, curr, old_dest;
3921       tree phi;
3922       int arg;
3923
3924       /* If the edge is abnormal or its destination is not
3925          forwardable, then there's nothing to do.  */
3926       if ((e->flags & EDGE_ABNORMAL)
3927           || !bb_ann (e->dest)->forwardable)
3928         {
3929           ei_next (&ei);
3930           continue;
3931         }
3932
3933       /* Now walk through as many forwarder blocks as possible to find
3934          the ultimate destination we want to thread our jump to.  */
3935       last = EDGE_SUCC (e->dest, 0);
3936       bb_ann (e->dest)->forwardable = 0;
3937       for (dest = EDGE_SUCC (e->dest, 0)->dest;
3938            bb_ann (dest)->forwardable;
3939            last = EDGE_SUCC (dest, 0),
3940              dest = EDGE_SUCC (dest, 0)->dest)
3941         bb_ann (dest)->forwardable = 0;
3942
3943       /* Reset the forwardable marks to 1.  */
3944       for (tmp = e->dest;
3945            tmp != dest;
3946            tmp = EDGE_SUCC (tmp, 0)->dest)
3947         bb_ann (tmp)->forwardable = 1;
3948
3949       if (dest == e->dest)
3950         {
3951           ei_next (&ei);
3952           continue;
3953         }
3954
3955       old = find_edge (bb, dest);
3956       if (old)
3957         {
3958           /* If there already is an edge, check whether the values in
3959              phi nodes differ.  */
3960           if (!phi_alternatives_equal (dest, last, old))
3961             {
3962               /* The previous block is forwarder.  Redirect our jump
3963                  to that target instead since we know it has no PHI
3964                  nodes that will need updating.  */
3965               dest = last->src;
3966
3967               /* That might mean that no forwarding at all is
3968                  possible.  */
3969               if (dest == e->dest)
3970                 {
3971                   ei_next (&ei);
3972                   continue;
3973                 }
3974
3975               old = find_edge (bb, dest);
3976             }
3977         }
3978
3979       /* Perform the redirection.  */
3980       retval = true;
3981       count = e->count;
3982       freq = EDGE_FREQUENCY (e);
3983       old_dest = e->dest;
3984       e = redirect_edge_and_branch (e, dest);
3985
3986       /* Update the profile.  */
3987       if (profile_status != PROFILE_ABSENT)
3988         for (curr = old_dest;
3989              curr != dest;
3990              curr = EDGE_SUCC (curr, 0)->dest)
3991           {
3992             curr->frequency -= freq;
3993             if (curr->frequency < 0)
3994               curr->frequency = 0;
3995             curr->count -= count;
3996             if (curr->count < 0)
3997               curr->count = 0;
3998             EDGE_SUCC (curr, 0)->count -= count;
3999             if (EDGE_SUCC (curr, 0)->count < 0)
4000               EDGE_SUCC (curr, 0)->count = 0;
4001           }
4002
4003       if (!old)
4004         {
4005           /* Update PHI nodes.  We know that the new argument should
4006              have the same value as the argument associated with LAST.
4007              Otherwise we would have changed our target block
4008              above.  */
4009           for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
4010             {
4011               arg = phi_arg_from_edge (phi, last);
4012               gcc_assert (arg >= 0);
4013               add_phi_arg (&phi, PHI_ARG_DEF (phi, arg), e);
4014             }
4015         }
4016
4017       /* Remove the unreachable blocks (observe that if all blocks
4018          were reachable before, only those in the path we threaded
4019          over and did not have any predecessor outside of the path
4020          become unreachable).  */
4021       for (; old_dest != dest; old_dest = tmp)
4022         {
4023           tmp = EDGE_SUCC (old_dest, 0)->dest;
4024
4025           if (EDGE_COUNT (old_dest->preds) > 0)
4026             break;
4027
4028           delete_basic_block (old_dest);
4029         }
4030
4031       /* Update the dominators.  */
4032       if (dom_info_available_p (CDI_DOMINATORS))
4033         {
4034           /* If the dominator of the destination was in the
4035              path, set its dominator to the start of the
4036              redirected edge.  */
4037           if (get_immediate_dominator (CDI_DOMINATORS, old_dest) == NULL)
4038             set_immediate_dominator (CDI_DOMINATORS, old_dest, bb);
4039
4040           /* Now proceed like if we forwarded just over one edge at a
4041              time.  Algorithm for forwarding edge S --> A over
4042              edge A --> B then is
4043
4044              if (idom (B) == A
4045                  && !dominated_by (S, B))
4046                idom (B) = idom (A);
4047              recount_idom (A);  */
4048
4049           for (; old_dest != dest; old_dest = tmp)
4050             {
4051               basic_block dom;
4052
4053               tmp = EDGE_SUCC (old_dest, 0)->dest;
4054
4055               if (get_immediate_dominator (CDI_DOMINATORS, tmp) == old_dest
4056                   && !dominated_by_p (CDI_DOMINATORS, bb, tmp))
4057                 {
4058                   dom = get_immediate_dominator (CDI_DOMINATORS, old_dest);
4059                   set_immediate_dominator (CDI_DOMINATORS, tmp, dom);
4060                 }
4061
4062               dom = recount_dominator (CDI_DOMINATORS, old_dest);
4063               set_immediate_dominator (CDI_DOMINATORS, old_dest, dom);
4064             }
4065         }
4066     }
4067
4068   return retval;
4069 }
4070
4071
4072 /* Thread jumps over empty statements.
4073
4074    This code should _not_ thread over obviously equivalent conditions
4075    as that requires nontrivial updates to the SSA graph.
4076
4077    As a precondition, we require that all basic blocks be reachable.
4078    That is, there should be no opportunities left for
4079    delete_unreachable_blocks.  */
4080
4081 static bool
4082 thread_jumps (void)
4083 {
4084   basic_block bb;
4085   bool retval = false;
4086   basic_block *worklist = xmalloc (sizeof (basic_block) * last_basic_block);
4087   basic_block *current = worklist;
4088
4089   FOR_EACH_BB (bb)
4090     {
4091       bb_ann (bb)->forwardable = tree_forwarder_block_p (bb);
4092       bb->flags &= ~BB_VISITED;
4093     }
4094
4095   /* We pretend to have ENTRY_BLOCK_PTR in WORKLIST.  This way,
4096      ENTRY_BLOCK_PTR will never be entered into WORKLIST.  */
4097   ENTRY_BLOCK_PTR->flags |= BB_VISITED;
4098
4099   /* Initialize WORKLIST by putting non-forwarder blocks that
4100      immediately precede forwarder blocks because those are the ones
4101      that we know we can thread jumps from.  We use BB_VISITED to
4102      indicate whether a given basic block is in WORKLIST or not,
4103      thereby avoiding duplicates in WORKLIST.  */
4104   FOR_EACH_BB (bb)
4105     {
4106       edge_iterator ei;
4107       edge e;
4108
4109       /* We are not interested in finding non-forwarder blocks
4110          directly.  We want to find non-forwarder blocks as
4111          predecessors of a forwarder block.  */
4112       if (!bb_ann (bb)->forwardable)
4113         continue;
4114
4115       /* Now we know BB is a forwarder block.  Visit each of its
4116          incoming edges and add to WORKLIST all non-forwarder blocks
4117          among BB's predecessors.  */
4118       FOR_EACH_EDGE (e, ei, bb->preds)
4119         {
4120           /* We don't want to put a duplicate into WORKLIST.  */
4121           if ((e->src->flags & BB_VISITED) == 0
4122               /* We are not interested in threading jumps from a forwarder
4123                  block.  */
4124               && !bb_ann (e->src)->forwardable)
4125             {
4126               e->src->flags |= BB_VISITED;
4127               *current++ = e->src;
4128             }
4129         }
4130     }
4131
4132   /* Now let's drain WORKLIST.  */
4133   while (worklist != current)
4134     {
4135       bb = *--current;
4136
4137       /* BB is no longer in WORKLIST, so clear BB_VISITED.  */
4138       bb->flags &= ~BB_VISITED;
4139
4140       if (thread_jumps_from_bb (bb))
4141         {
4142           retval = true;
4143
4144           if (tree_forwarder_block_p (bb))
4145             {
4146               edge_iterator ej;
4147               edge f;
4148
4149               bb_ann (bb)->forwardable = true;
4150
4151               /* Attempts to thread through BB may have been blocked
4152                  because BB was not a forwarder block before.  Now
4153                  that BB is a forwarder block, we should revisit BB's
4154                  predecessors.  */
4155               FOR_EACH_EDGE (f, ej, bb->preds)
4156                 {
4157                   /* We don't want to put a duplicate into WORKLIST.  */
4158                   if ((f->src->flags & BB_VISITED) == 0
4159                       /* We are not interested in threading jumps from a
4160                          forwarder block.  */
4161                       && !bb_ann (f->src)->forwardable)
4162                     {
4163                       f->src->flags |= BB_VISITED;
4164                       *current++ = f->src;
4165                     }
4166                 }
4167             }
4168         }
4169     }
4170
4171   ENTRY_BLOCK_PTR->flags &= ~BB_VISITED;
4172
4173   free (worklist);
4174
4175   return retval;
4176 }
4177
4178
4179 /* Return a non-special label in the head of basic block BLOCK.
4180    Create one if it doesn't exist.  */
4181
4182 tree
4183 tree_block_label (basic_block bb)
4184 {
4185   block_stmt_iterator i, s = bsi_start (bb);
4186   bool first = true;
4187   tree label, stmt;
4188
4189   for (i = s; !bsi_end_p (i); first = false, bsi_next (&i))
4190     {
4191       stmt = bsi_stmt (i);
4192       if (TREE_CODE (stmt) != LABEL_EXPR)
4193         break;
4194       label = LABEL_EXPR_LABEL (stmt);
4195       if (!DECL_NONLOCAL (label))
4196         {
4197           if (!first)
4198             bsi_move_before (&i, &s);
4199           return label;
4200         }
4201     }
4202
4203   label = create_artificial_label ();
4204   stmt = build1 (LABEL_EXPR, void_type_node, label);
4205   bsi_insert_before (&s, stmt, BSI_NEW_STMT);
4206   return label;
4207 }
4208
4209
4210 /* Attempt to perform edge redirection by replacing a possibly complex
4211    jump instruction by a goto or by removing the jump completely.
4212    This can apply only if all edges now point to the same block.  The
4213    parameters and return values are equivalent to
4214    redirect_edge_and_branch.  */
4215
4216 static edge
4217 tree_try_redirect_by_replacing_jump (edge e, basic_block target)
4218 {
4219   basic_block src = e->src;
4220   edge tmp;
4221   block_stmt_iterator b;
4222   tree stmt;
4223   edge_iterator ei;
4224
4225   /* Verify that all targets will be TARGET.  */
4226   FOR_EACH_EDGE (tmp, ei, src->succs)
4227     if (tmp->dest != target && tmp != e)
4228       break;
4229
4230   if (tmp)
4231     return NULL;
4232
4233   b = bsi_last (src);
4234   if (bsi_end_p (b))
4235     return NULL;
4236   stmt = bsi_stmt (b);
4237
4238   if (TREE_CODE (stmt) == COND_EXPR
4239       || TREE_CODE (stmt) == SWITCH_EXPR)
4240     {
4241       bsi_remove (&b);
4242       e = ssa_redirect_edge (e, target);
4243       e->flags = EDGE_FALLTHRU;
4244       return e;
4245     }
4246
4247   return NULL;
4248 }
4249
4250
4251 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4252    edge representing the redirected branch.  */
4253
4254 static edge
4255 tree_redirect_edge_and_branch (edge e, basic_block dest)
4256 {
4257   basic_block bb = e->src;
4258   block_stmt_iterator bsi;
4259   edge ret;
4260   tree label, stmt;
4261
4262   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4263     return NULL;
4264
4265   if (e->src != ENTRY_BLOCK_PTR
4266       && (ret = tree_try_redirect_by_replacing_jump (e, dest)))
4267     return ret;
4268
4269   if (e->dest == dest)
4270     return NULL;
4271
4272   label = tree_block_label (dest);
4273
4274   bsi = bsi_last (bb);
4275   stmt = bsi_end_p (bsi) ? NULL : bsi_stmt (bsi);
4276
4277   switch (stmt ? TREE_CODE (stmt) : ERROR_MARK)
4278     {
4279     case COND_EXPR:
4280       stmt = (e->flags & EDGE_TRUE_VALUE
4281               ? COND_EXPR_THEN (stmt)
4282               : COND_EXPR_ELSE (stmt));
4283       GOTO_DESTINATION (stmt) = label;
4284       break;
4285
4286     case GOTO_EXPR:
4287       /* No non-abnormal edges should lead from a non-simple goto, and
4288          simple ones should be represented implicitly.  */
4289       gcc_unreachable ();
4290
4291     case SWITCH_EXPR:
4292       {
4293         edge e2;
4294
4295         /* We need to update the LABEL_DECL in the switch vector to
4296            reflect the edge redirection.
4297
4298            There is precisely one CASE_LABEL_EXPR in the switch vector
4299            which needs updating.  Either its label needs to be updated
4300            or it needs to be directed to a new case leader.   */
4301         e2 = find_edge (e->src, dest);
4302         if (e2)
4303           {
4304             /* In this case we need to change the case leader for the
4305                current leader of E to be the case leader for E2.   */
4306             tree e_leader = get_case_leader_for_edge (e);
4307             tree e2_leader = get_case_leader_for_edge (e2);
4308             CASE_LEADER_OR_LABEL (e_leader) = e2_leader;
4309           }
4310         else
4311           {
4312             /* No edge exists from E->src to DEST, so we will simply
4313                change E->dest.  The case leader does not change, but
4314                the LABEL_DECL for the leader does change.  */
4315             CASE_LEADER_OR_LABEL (get_case_leader_for_edge (e)) = label;
4316           }
4317         break;
4318       }
4319
4320     case RETURN_EXPR:
4321       bsi_remove (&bsi);
4322       e->flags |= EDGE_FALLTHRU;
4323       break;
4324
4325     default:
4326       /* Otherwise it must be a fallthru edge, and we don't need to
4327          do anything besides redirecting it.  */
4328       gcc_assert (e->flags & EDGE_FALLTHRU);
4329       break;
4330     }
4331
4332   /* Update/insert PHI nodes as necessary.  */
4333
4334   /* Now update the edges in the CFG.  */
4335   e = ssa_redirect_edge (e, dest);
4336
4337   return e;
4338 }
4339
4340
4341 /* Simple wrapper, as we can always redirect fallthru edges.  */
4342
4343 static basic_block
4344 tree_redirect_edge_and_branch_force (edge e, basic_block dest)
4345 {
4346   e = tree_redirect_edge_and_branch (e, dest);
4347   gcc_assert (e);
4348
4349   return NULL;
4350 }
4351
4352
4353 /* Splits basic block BB after statement STMT (but at least after the
4354    labels).  If STMT is NULL, BB is split just after the labels.  */
4355
4356 static basic_block
4357 tree_split_block (basic_block bb, void *stmt)
4358 {
4359   block_stmt_iterator bsi, bsi_tgt;
4360   tree act;
4361   basic_block new_bb;
4362   edge e;
4363   edge_iterator ei;
4364
4365   new_bb = create_empty_bb (bb);
4366
4367   /* Redirect the outgoing edges.  */
4368   new_bb->succs = bb->succs;
4369   bb->succs = NULL;
4370   FOR_EACH_EDGE (e, ei, new_bb->succs)
4371     e->src = new_bb;
4372
4373   if (stmt && TREE_CODE ((tree) stmt) == LABEL_EXPR)
4374     stmt = NULL;
4375
4376   /* Move everything from BSI to the new basic block.  */
4377   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4378     {
4379       act = bsi_stmt (bsi);
4380       if (TREE_CODE (act) == LABEL_EXPR)
4381         continue;
4382
4383       if (!stmt)
4384         break;
4385
4386       if (stmt == act)
4387         {
4388           bsi_next (&bsi);
4389           break;
4390         }
4391     }
4392
4393   bsi_tgt = bsi_start (new_bb);
4394   while (!bsi_end_p (bsi))
4395     {
4396       act = bsi_stmt (bsi);
4397       bsi_remove (&bsi);
4398       bsi_insert_after (&bsi_tgt, act, BSI_NEW_STMT);
4399     }
4400
4401   return new_bb;
4402 }
4403
4404
4405 /* Moves basic block BB after block AFTER.  */
4406
4407 static bool
4408 tree_move_block_after (basic_block bb, basic_block after)
4409 {
4410   if (bb->prev_bb == after)
4411     return true;
4412
4413   unlink_block (bb);
4414   link_block (bb, after);
4415
4416   return true;
4417 }
4418
4419
4420 /* Return true if basic_block can be duplicated.  */
4421
4422 static bool
4423 tree_can_duplicate_bb_p (basic_block bb ATTRIBUTE_UNUSED)
4424 {
4425   return true;
4426 }
4427
4428 /* Create a duplicate of the basic block BB.  NOTE: This does not
4429    preserve SSA form.  */
4430
4431 static basic_block
4432 tree_duplicate_bb (basic_block bb)
4433 {
4434   basic_block new_bb;
4435   block_stmt_iterator bsi, bsi_tgt;
4436   tree phi, val;
4437   ssa_op_iter op_iter;
4438
4439   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
4440
4441   /* First copy the phi nodes.  We do not copy phi node arguments here,
4442      since the edges are not ready yet.  Keep the chain of phi nodes in
4443      the same order, so that we can add them later.  */
4444   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4445     {
4446       mark_for_rewrite (PHI_RESULT (phi));
4447       create_phi_node (PHI_RESULT (phi), new_bb);
4448     }
4449   set_phi_nodes (new_bb, phi_reverse (phi_nodes (new_bb)));
4450
4451   bsi_tgt = bsi_start (new_bb);
4452   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4453     {
4454       tree stmt = bsi_stmt (bsi);
4455       tree copy;
4456
4457       if (TREE_CODE (stmt) == LABEL_EXPR)
4458         continue;
4459
4460       /* Record the definitions.  */
4461       get_stmt_operands (stmt);
4462
4463       FOR_EACH_SSA_TREE_OPERAND (val, stmt, op_iter, SSA_OP_ALL_DEFS)
4464         mark_for_rewrite (val);
4465
4466       copy = unshare_expr (stmt);
4467
4468       /* Copy also the virtual operands.  */
4469       get_stmt_ann (copy);
4470       copy_virtual_operands (copy, stmt);
4471
4472       bsi_insert_after (&bsi_tgt, copy, BSI_NEW_STMT);
4473     }
4474
4475   return new_bb;
4476 }
4477
4478 /* Basic block BB_COPY was created by code duplication.  Add phi node
4479    arguments for edges going out of BB_COPY.  The blocks that were
4480    duplicated have rbi->duplicated set to one.  */
4481
4482 void
4483 add_phi_args_after_copy_bb (basic_block bb_copy)
4484 {
4485   basic_block bb, dest;
4486   edge e, e_copy;
4487   edge_iterator ei;
4488   tree phi, phi_copy, phi_next, def;
4489
4490   bb = bb_copy->rbi->original;
4491
4492   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
4493     {
4494       if (!phi_nodes (e_copy->dest))
4495         continue;
4496
4497       if (e_copy->dest->rbi->duplicated)
4498         dest = e_copy->dest->rbi->original;
4499       else
4500         dest = e_copy->dest;
4501
4502       e = find_edge (bb, dest);
4503       if (!e)
4504         {
4505           /* During loop unrolling the target of the latch edge is copied.
4506              In this case we are not looking for edge to dest, but to
4507              duplicated block whose original was dest.  */
4508           FOR_EACH_EDGE (e, ei, bb->succs)
4509             if (e->dest->rbi->duplicated
4510                 && e->dest->rbi->original == dest)
4511               break;
4512
4513           gcc_assert (e != NULL);
4514         }
4515
4516       for (phi = phi_nodes (e->dest), phi_copy = phi_nodes (e_copy->dest);
4517            phi;
4518            phi = phi_next, phi_copy = TREE_CHAIN (phi_copy))
4519         {
4520           phi_next = TREE_CHAIN (phi);
4521
4522           gcc_assert (PHI_RESULT (phi) == PHI_RESULT (phi_copy));
4523           def = PHI_ARG_DEF_FROM_EDGE (phi, e);
4524           add_phi_arg (&phi_copy, def, e_copy);
4525         }
4526     }
4527 }
4528
4529 /* Blocks in REGION_COPY array of length N_REGION were created by
4530    duplication of basic blocks.  Add phi node arguments for edges
4531    going from these blocks.  */
4532
4533 void
4534 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region)
4535 {
4536   unsigned i;
4537
4538   for (i = 0; i < n_region; i++)
4539     region_copy[i]->rbi->duplicated = 1;
4540
4541   for (i = 0; i < n_region; i++)
4542     add_phi_args_after_copy_bb (region_copy[i]);
4543
4544   for (i = 0; i < n_region; i++)
4545     region_copy[i]->rbi->duplicated = 0;
4546 }
4547
4548 /* Maps the old ssa name FROM_NAME to TO_NAME.  */
4549
4550 struct ssa_name_map_entry
4551 {
4552   tree from_name;
4553   tree to_name;
4554 };
4555
4556 /* Hash function for ssa_name_map_entry.  */
4557
4558 static hashval_t
4559 ssa_name_map_entry_hash (const void *entry)
4560 {
4561   const struct ssa_name_map_entry *en = entry;
4562   return SSA_NAME_VERSION (en->from_name);
4563 }
4564
4565 /* Equality function for ssa_name_map_entry.  */
4566
4567 static int
4568 ssa_name_map_entry_eq (const void *in_table, const void *ssa_name)
4569 {
4570   const struct ssa_name_map_entry *en = in_table;
4571
4572   return en->from_name == ssa_name;
4573 }
4574
4575 /* Allocate duplicates of ssa names in list DEFINITIONS and store the mapping
4576    to MAP.  */
4577
4578 void
4579 allocate_ssa_names (bitmap definitions, htab_t *map)
4580 {
4581   tree name;
4582   struct ssa_name_map_entry *entry;
4583   PTR *slot;
4584   unsigned ver;
4585   bitmap_iterator bi;
4586
4587   if (!*map)
4588     *map = htab_create (10, ssa_name_map_entry_hash,
4589                         ssa_name_map_entry_eq, free);
4590   EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
4591     {
4592       name = ssa_name (ver);
4593       slot = htab_find_slot_with_hash (*map, name, SSA_NAME_VERSION (name),
4594                                        INSERT);
4595       if (*slot)
4596         entry = *slot;
4597       else
4598         {
4599           entry = xmalloc (sizeof (struct ssa_name_map_entry));
4600           entry->from_name = name;
4601           *slot = entry;
4602         }
4603       entry->to_name = duplicate_ssa_name (name, SSA_NAME_DEF_STMT (name));
4604     }
4605 }
4606
4607 /* Rewrite the definition DEF in statement STMT to new ssa name as specified
4608    by the mapping MAP.  */
4609
4610 static void
4611 rewrite_to_new_ssa_names_def (def_operand_p def, tree stmt, htab_t map)
4612 {
4613   tree name = DEF_FROM_PTR (def);
4614   struct ssa_name_map_entry *entry;
4615
4616   gcc_assert (TREE_CODE (name) == SSA_NAME);
4617
4618   entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
4619   if (!entry)
4620     return;
4621
4622   SET_DEF (def, entry->to_name);
4623   SSA_NAME_DEF_STMT (entry->to_name) = stmt;
4624 }
4625
4626 /* Rewrite the USE to new ssa name as specified by the mapping MAP.  */
4627
4628 static void
4629 rewrite_to_new_ssa_names_use (use_operand_p use, htab_t map)
4630 {
4631   tree name = USE_FROM_PTR (use);
4632   struct ssa_name_map_entry *entry;
4633
4634   if (TREE_CODE (name) != SSA_NAME)
4635     return;
4636
4637   entry = htab_find_with_hash (map, name, SSA_NAME_VERSION (name));
4638   if (!entry)
4639     return;
4640
4641   SET_USE (use, entry->to_name);
4642 }
4643
4644 /* Rewrite the ssa names in basic block BB to new ones as specified by the
4645    mapping MAP.  */
4646
4647 void
4648 rewrite_to_new_ssa_names_bb (basic_block bb, htab_t map)
4649 {
4650   unsigned i;
4651   edge e;
4652   edge_iterator ei;
4653   tree phi, stmt;
4654   block_stmt_iterator bsi;
4655   use_optype uses;
4656   vuse_optype vuses;
4657   def_optype defs;
4658   v_may_def_optype v_may_defs;
4659   v_must_def_optype v_must_defs;
4660   stmt_ann_t ann;
4661
4662   FOR_EACH_EDGE (e, ei, bb->preds)
4663     if (e->flags & EDGE_ABNORMAL)
4664       break;
4665
4666   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4667     {
4668       rewrite_to_new_ssa_names_def (PHI_RESULT_PTR (phi), phi, map);
4669       if (e)
4670         SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
4671     }
4672
4673   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4674     {
4675       stmt = bsi_stmt (bsi);
4676       get_stmt_operands (stmt);
4677       ann = stmt_ann (stmt);
4678
4679       uses = USE_OPS (ann);
4680       for (i = 0; i < NUM_USES (uses); i++)
4681         rewrite_to_new_ssa_names_use (USE_OP_PTR (uses, i), map);
4682
4683       defs = DEF_OPS (ann);
4684       for (i = 0; i < NUM_DEFS (defs); i++)
4685         rewrite_to_new_ssa_names_def (DEF_OP_PTR (defs, i), stmt, map);
4686
4687       vuses = VUSE_OPS (ann);
4688       for (i = 0; i < NUM_VUSES (vuses); i++)
4689         rewrite_to_new_ssa_names_use (VUSE_OP_PTR (vuses, i), map);
4690
4691       v_may_defs = V_MAY_DEF_OPS (ann);
4692       for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
4693         {
4694           rewrite_to_new_ssa_names_use
4695                   (V_MAY_DEF_OP_PTR (v_may_defs, i), map);
4696           rewrite_to_new_ssa_names_def
4697                   (V_MAY_DEF_RESULT_PTR (v_may_defs, i), stmt, map);
4698         }
4699
4700       v_must_defs = V_MUST_DEF_OPS (ann);
4701       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
4702         {
4703           rewrite_to_new_ssa_names_def
4704             (V_MUST_DEF_RESULT_PTR (v_must_defs, i), stmt, map);
4705           rewrite_to_new_ssa_names_use
4706             (V_MUST_DEF_KILL_PTR (v_must_defs, i),  map);
4707         }
4708     }
4709
4710   FOR_EACH_EDGE (e, ei, bb->succs)
4711     for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
4712       {
4713         rewrite_to_new_ssa_names_use
4714                 (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e), map);
4715
4716         if (e->flags & EDGE_ABNORMAL)
4717           {
4718             tree op = PHI_ARG_DEF_FROM_EDGE (phi, e);
4719             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op) = 1;
4720           }
4721       }
4722 }
4723
4724 /* Rewrite the ssa names in N_REGION blocks REGION to the new ones as specified
4725    by the mapping MAP.  */
4726
4727 void
4728 rewrite_to_new_ssa_names (basic_block *region, unsigned n_region, htab_t map)
4729 {
4730   unsigned r;
4731
4732   for (r = 0; r < n_region; r++)
4733     rewrite_to_new_ssa_names_bb (region[r], map);
4734 }
4735
4736 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
4737    important exit edge EXIT.  By important we mean that no SSA name defined
4738    inside region is live over the other exit edges of the region.  All entry
4739    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
4740    to the duplicate of the region.  SSA form, dominance and loop information
4741    is updated.  The new basic blocks are stored to REGION_COPY in the same
4742    order as they had in REGION, provided that REGION_COPY is not NULL.
4743    The function returns false if it is unable to copy the region,
4744    true otherwise.  */
4745
4746 bool
4747 tree_duplicate_sese_region (edge entry, edge exit,
4748                             basic_block *region, unsigned n_region,
4749                             basic_block *region_copy)
4750 {
4751   unsigned i, n_doms, ver;
4752   bool free_region_copy = false, copying_header = false;
4753   struct loop *loop = entry->dest->loop_father;
4754   edge exit_copy;
4755   bitmap definitions;
4756   tree phi;
4757   basic_block *doms;
4758   htab_t ssa_name_map = NULL;
4759   edge redirected;
4760   bitmap_iterator bi;
4761
4762   if (!can_copy_bbs_p (region, n_region))
4763     return false;
4764
4765   /* Some sanity checking.  Note that we do not check for all possible
4766      missuses of the functions.  I.e. if you ask to copy something weird,
4767      it will work, but the state of structures probably will not be
4768      correct.  */
4769
4770   for (i = 0; i < n_region; i++)
4771     {
4772       /* We do not handle subloops, i.e. all the blocks must belong to the
4773          same loop.  */
4774       if (region[i]->loop_father != loop)
4775         return false;
4776
4777       if (region[i] != entry->dest
4778           && region[i] == loop->header)
4779         return false;
4780     }
4781
4782   loop->copy = loop;
4783
4784   /* In case the function is used for loop header copying (which is the primary
4785      use), ensure that EXIT and its copy will be new latch and entry edges.  */
4786   if (loop->header == entry->dest)
4787     {
4788       copying_header = true;
4789       loop->copy = loop->outer;
4790
4791       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
4792         return false;
4793
4794       for (i = 0; i < n_region; i++)
4795         if (region[i] != exit->src
4796             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
4797           return false;
4798     }
4799
4800   if (!region_copy)
4801     {
4802       region_copy = xmalloc (sizeof (basic_block) * n_region);
4803       free_region_copy = true;
4804     }
4805
4806   gcc_assert (!any_marked_for_rewrite_p ());
4807
4808   /* Record blocks outside the region that are duplicated by something
4809      inside.  */
4810   doms = xmalloc (sizeof (basic_block) * n_basic_blocks);
4811   n_doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region, doms);
4812
4813   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop);
4814   definitions = marked_ssa_names ();
4815
4816   if (copying_header)
4817     {
4818       loop->header = exit->dest;
4819       loop->latch = exit->src;
4820     }
4821
4822   /* Redirect the entry and add the phi node arguments.  */
4823   redirected = redirect_edge_and_branch (entry, entry->dest->rbi->copy);
4824   gcc_assert (redirected != NULL);
4825   flush_pending_stmts (entry);
4826
4827   /* Concerning updating of dominators:  We must recount dominators
4828      for entry block and its copy.  Anything that is outside of the region, but
4829      was dominated by something inside needs recounting as well.  */
4830   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
4831   doms[n_doms++] = entry->dest->rbi->original;
4832   iterate_fix_dominators (CDI_DOMINATORS, doms, n_doms);
4833   free (doms);
4834
4835   /* Add the other phi node arguments.  */
4836   add_phi_args_after_copy (region_copy, n_region);
4837
4838   /* Add phi nodes for definitions at exit.  TODO -- once we have immediate
4839      uses, it should be possible to emit phi nodes just for definitions that
4840      are used outside region.  */
4841   EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
4842     {
4843       tree name = ssa_name (ver);
4844
4845       phi = create_phi_node (name, exit->dest);
4846       add_phi_arg (&phi, name, exit);
4847       add_phi_arg (&phi, name, exit_copy);
4848
4849       SSA_NAME_DEF_STMT (name) = phi;
4850     }
4851
4852   /* And create new definitions inside region and its copy.  TODO -- once we
4853      have immediate uses, it might be better to leave definitions in region
4854      unchanged, create new ssa names for phi nodes on exit, and rewrite
4855      the uses, to avoid changing the copied region.  */
4856   allocate_ssa_names (definitions, &ssa_name_map);
4857   rewrite_to_new_ssa_names (region, n_region, ssa_name_map);
4858   allocate_ssa_names (definitions, &ssa_name_map);
4859   rewrite_to_new_ssa_names (region_copy, n_region, ssa_name_map);
4860   htab_delete (ssa_name_map);
4861
4862   if (free_region_copy)
4863     free (region_copy);
4864
4865   unmark_all_for_rewrite ();
4866   BITMAP_XFREE (definitions);
4867
4868   return true;
4869 }
4870
4871 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree.h)  */
4872
4873 void
4874 dump_function_to_file (tree fn, FILE *file, int flags)
4875 {
4876   tree arg, vars, var;
4877   bool ignore_topmost_bind = false, any_var = false;
4878   basic_block bb;
4879   tree chain;
4880
4881   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
4882
4883   arg = DECL_ARGUMENTS (fn);
4884   while (arg)
4885     {
4886       print_generic_expr (file, arg, dump_flags);
4887       if (TREE_CHAIN (arg))
4888         fprintf (file, ", ");
4889       arg = TREE_CHAIN (arg);
4890     }
4891   fprintf (file, ")\n");
4892
4893   if (flags & TDF_RAW)
4894     {
4895       dump_node (fn, TDF_SLIM | flags, file);
4896       return;
4897     }
4898
4899   /* When GIMPLE is lowered, the variables are no longer available in
4900      BIND_EXPRs, so display them separately.  */
4901   if (cfun && cfun->unexpanded_var_list)
4902     {
4903       ignore_topmost_bind = true;
4904
4905       fprintf (file, "{\n");
4906       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
4907         {
4908           var = TREE_VALUE (vars);
4909
4910           print_generic_decl (file, var, flags);
4911           fprintf (file, "\n");
4912
4913           any_var = true;
4914         }
4915     }
4916
4917   if (basic_block_info)
4918     {
4919       /* Make a CFG based dump.  */
4920       check_bb_profile (ENTRY_BLOCK_PTR, file);
4921       if (!ignore_topmost_bind)
4922         fprintf (file, "{\n");
4923
4924       if (any_var && n_basic_blocks)
4925         fprintf (file, "\n");
4926
4927       FOR_EACH_BB (bb)
4928         dump_generic_bb (file, bb, 2, flags);
4929
4930       fprintf (file, "}\n");
4931       check_bb_profile (EXIT_BLOCK_PTR, file);
4932     }
4933   else
4934     {
4935       int indent;
4936
4937       /* Make a tree based dump.  */
4938       chain = DECL_SAVED_TREE (fn);
4939
4940       if (TREE_CODE (chain) == BIND_EXPR)
4941         {
4942           if (ignore_topmost_bind)
4943             {
4944               chain = BIND_EXPR_BODY (chain);
4945               indent = 2;
4946             }
4947           else
4948             indent = 0;
4949         }
4950       else
4951         {
4952           if (!ignore_topmost_bind)
4953             fprintf (file, "{\n");
4954           indent = 2;
4955         }
4956
4957       if (any_var)
4958         fprintf (file, "\n");
4959
4960       print_generic_stmt_indented (file, chain, flags, indent);
4961       if (ignore_topmost_bind)
4962         fprintf (file, "}\n");
4963     }
4964
4965   fprintf (file, "\n\n");
4966 }
4967
4968
4969 /* Pretty print of the loops intermediate representation.  */
4970 static void print_loop (FILE *, struct loop *, int);
4971 static void print_pred_bbs (FILE *, basic_block bb);
4972 static void print_succ_bbs (FILE *, basic_block bb);
4973
4974
4975 /* Print the predecessors indexes of edge E on FILE.  */
4976
4977 static void
4978 print_pred_bbs (FILE *file, basic_block bb)
4979 {
4980   edge e;
4981   edge_iterator ei;
4982
4983   FOR_EACH_EDGE (e, ei, bb->preds)
4984     fprintf (file, "bb_%d", e->src->index);
4985 }
4986
4987
4988 /* Print the successors indexes of edge E on FILE.  */
4989
4990 static void
4991 print_succ_bbs (FILE *file, basic_block bb)
4992 {
4993   edge e;
4994   edge_iterator ei;
4995
4996   FOR_EACH_EDGE (e, ei, bb->succs)
4997     fprintf (file, "bb_%d", e->src->index);
4998 }
4999
5000
5001 /* Pretty print LOOP on FILE, indented INDENT spaces.  */
5002
5003 static void
5004 print_loop (FILE *file, struct loop *loop, int indent)
5005 {
5006   char *s_indent;
5007   basic_block bb;
5008
5009   if (loop == NULL)
5010     return;
5011
5012   s_indent = (char *) alloca ((size_t) indent + 1);
5013   memset ((void *) s_indent, ' ', (size_t) indent);
5014   s_indent[indent] = '\0';
5015
5016   /* Print the loop's header.  */
5017   fprintf (file, "%sloop_%d\n", s_indent, loop->num);
5018
5019   /* Print the loop's body.  */
5020   fprintf (file, "%s{\n", s_indent);
5021   FOR_EACH_BB (bb)
5022     if (bb->loop_father == loop)
5023       {
5024         /* Print the basic_block's header.  */
5025         fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
5026         print_pred_bbs (file, bb);
5027         fprintf (file, "}, succs = {");
5028         print_succ_bbs (file, bb);
5029         fprintf (file, "})\n");
5030
5031         /* Print the basic_block's body.  */
5032         fprintf (file, "%s  {\n", s_indent);
5033         tree_dump_bb (bb, file, indent + 4);
5034         fprintf (file, "%s  }\n", s_indent);
5035       }
5036
5037   print_loop (file, loop->inner, indent + 2);
5038   fprintf (file, "%s}\n", s_indent);
5039   print_loop (file, loop->next, indent);
5040 }
5041
5042
5043 /* Follow a CFG edge from the entry point of the program, and on entry
5044    of a loop, pretty print the loop structure on FILE.  */
5045
5046 void
5047 print_loop_ir (FILE *file)
5048 {
5049   basic_block bb;
5050
5051   bb = BASIC_BLOCK (0);
5052   if (bb && bb->loop_father)
5053     print_loop (file, bb->loop_father, 0);
5054 }
5055
5056
5057 /* Debugging loops structure at tree level.  */
5058
5059 void
5060 debug_loop_ir (void)
5061 {
5062   print_loop_ir (stderr);
5063 }
5064
5065
5066 /* Return true if BB ends with a call, possibly followed by some
5067    instructions that must stay with the call.  Return false,
5068    otherwise.  */
5069
5070 static bool
5071 tree_block_ends_with_call_p (basic_block bb)
5072 {
5073   block_stmt_iterator bsi = bsi_last (bb);
5074   return get_call_expr_in (bsi_stmt (bsi)) != NULL;
5075 }
5076
5077
5078 /* Return true if BB ends with a conditional branch.  Return false,
5079    otherwise.  */
5080
5081 static bool
5082 tree_block_ends_with_condjump_p (basic_block bb)
5083 {
5084   tree stmt = tsi_stmt (bsi_last (bb).tsi);
5085   return (TREE_CODE (stmt) == COND_EXPR);
5086 }
5087
5088
5089 /* Return true if we need to add fake edge to exit at statement T.
5090    Helper function for tree_flow_call_edges_add.  */
5091
5092 static bool
5093 need_fake_edge_p (tree t)
5094 {
5095   tree call;
5096
5097   /* NORETURN and LONGJMP calls already have an edge to exit.
5098      CONST, PURE and ALWAYS_RETURN calls do not need one.
5099      We don't currently check for CONST and PURE here, although
5100      it would be a good idea, because those attributes are
5101      figured out from the RTL in mark_constant_function, and
5102      the counter incrementation code from -fprofile-arcs
5103      leads to different results from -fbranch-probabilities.  */
5104   call = get_call_expr_in (t);
5105   if (call
5106       && !(call_expr_flags (call) &
5107            (ECF_NORETURN | ECF_LONGJMP | ECF_ALWAYS_RETURN)))
5108     return true;
5109
5110   if (TREE_CODE (t) == ASM_EXPR
5111        && (ASM_VOLATILE_P (t) || ASM_INPUT_P (t)))
5112     return true;
5113
5114   return false;
5115 }
5116
5117
5118 /* Add fake edges to the function exit for any non constant and non
5119    noreturn calls, volatile inline assembly in the bitmap of blocks
5120    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
5121    the number of blocks that were split.
5122
5123    The goal is to expose cases in which entering a basic block does
5124    not imply that all subsequent instructions must be executed.  */
5125
5126 static int
5127 tree_flow_call_edges_add (sbitmap blocks)
5128 {
5129   int i;
5130   int blocks_split = 0;
5131   int last_bb = last_basic_block;
5132   bool check_last_block = false;
5133
5134   if (n_basic_blocks == 0)
5135     return 0;
5136
5137   if (! blocks)
5138     check_last_block = true;
5139   else
5140     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
5141
5142   /* In the last basic block, before epilogue generation, there will be
5143      a fallthru edge to EXIT.  Special care is required if the last insn
5144      of the last basic block is a call because make_edge folds duplicate
5145      edges, which would result in the fallthru edge also being marked
5146      fake, which would result in the fallthru edge being removed by
5147      remove_fake_edges, which would result in an invalid CFG.
5148
5149      Moreover, we can't elide the outgoing fake edge, since the block
5150      profiler needs to take this into account in order to solve the minimal
5151      spanning tree in the case that the call doesn't return.
5152
5153      Handle this by adding a dummy instruction in a new last basic block.  */
5154   if (check_last_block)
5155     {
5156       edge_iterator ei;
5157       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
5158       block_stmt_iterator bsi = bsi_last (bb);
5159       tree t = NULL_TREE;
5160       if (!bsi_end_p (bsi))
5161         t = bsi_stmt (bsi);
5162
5163       if (need_fake_edge_p (t))
5164         {
5165           edge e;
5166
5167           FOR_EACH_EDGE (e, ei, bb->succs)
5168             if (e->dest == EXIT_BLOCK_PTR)
5169               {
5170                 bsi_insert_on_edge (e, build_empty_stmt ());
5171                 bsi_commit_edge_inserts ((int *)NULL);
5172                 break;
5173               }
5174         }
5175     }
5176
5177   /* Now add fake edges to the function exit for any non constant
5178      calls since there is no way that we can determine if they will
5179      return or not...  */
5180   for (i = 0; i < last_bb; i++)
5181     {
5182       basic_block bb = BASIC_BLOCK (i);
5183       block_stmt_iterator bsi;
5184       tree stmt, last_stmt;
5185
5186       if (!bb)
5187         continue;
5188
5189       if (blocks && !TEST_BIT (blocks, i))
5190         continue;
5191
5192       bsi = bsi_last (bb);
5193       if (!bsi_end_p (bsi))
5194         {
5195           last_stmt = bsi_stmt (bsi);
5196           do
5197             {
5198               stmt = bsi_stmt (bsi);
5199               if (need_fake_edge_p (stmt))
5200                 {
5201                   edge e;
5202                   /* The handling above of the final block before the
5203                      epilogue should be enough to verify that there is
5204                      no edge to the exit block in CFG already.
5205                      Calling make_edge in such case would cause us to
5206                      mark that edge as fake and remove it later.  */
5207 #ifdef ENABLE_CHECKING
5208                   if (stmt == last_stmt)
5209                     {
5210                       edge_iterator ei;
5211                       FOR_EACH_EDGE (e, ei, bb->succs)
5212                         gcc_assert (e->dest != EXIT_BLOCK_PTR);
5213                     }
5214 #endif
5215
5216                   /* Note that the following may create a new basic block
5217                      and renumber the existing basic blocks.  */
5218                   if (stmt != last_stmt)
5219                     {
5220                       e = split_block (bb, stmt);
5221                       if (e)
5222                         blocks_split++;
5223                     }
5224                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
5225                 }
5226               bsi_prev (&bsi);
5227             }
5228           while (!bsi_end_p (bsi));
5229         }
5230     }
5231
5232   if (blocks_split)
5233     verify_flow_info ();
5234
5235   return blocks_split;
5236 }
5237
5238 bool
5239 tree_purge_dead_eh_edges (basic_block bb)
5240 {
5241   bool changed = false;
5242   edge e;
5243   edge_iterator ei;
5244   tree stmt = last_stmt (bb);
5245
5246   if (stmt && tree_can_throw_internal (stmt))
5247     return false;
5248
5249   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
5250     {
5251       if (e->flags & EDGE_EH)
5252         {
5253           ssa_remove_edge (e);
5254           changed = true;
5255         }
5256       else
5257         ei_next (&ei);
5258     }
5259
5260   /* Removal of dead EH edges might change dominators of not
5261      just immediate successors.  E.g. when bb1 is changed so that
5262      it no longer can throw and bb1->bb3 and bb1->bb4 are dead
5263      eh edges purged by this function in:
5264            0
5265           / \
5266          v   v
5267          1-->2
5268         / \  |
5269        v   v |
5270        3-->4 |
5271         \    v
5272          --->5
5273              |
5274              -
5275      idom(bb5) must be recomputed.  For now just free the dominance
5276      info.  */
5277   if (changed)
5278     free_dominance_info (CDI_DOMINATORS);
5279
5280   return changed;
5281 }
5282
5283 bool
5284 tree_purge_all_dead_eh_edges (bitmap blocks)
5285 {
5286   bool changed = false;
5287   unsigned i;
5288   bitmap_iterator bi;
5289
5290   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
5291     {
5292       changed |= tree_purge_dead_eh_edges (BASIC_BLOCK (i));
5293     }
5294
5295   return changed;
5296 }
5297
5298 struct cfg_hooks tree_cfg_hooks = {
5299   "tree",
5300   tree_verify_flow_info,
5301   tree_dump_bb,                 /* dump_bb  */
5302   create_bb,                    /* create_basic_block  */
5303   tree_redirect_edge_and_branch,/* redirect_edge_and_branch  */
5304   tree_redirect_edge_and_branch_force,/* redirect_edge_and_branch_force  */
5305   remove_bb,                    /* delete_basic_block  */
5306   tree_split_block,             /* split_block  */
5307   tree_move_block_after,        /* move_block_after  */
5308   tree_can_merge_blocks_p,      /* can_merge_blocks_p  */
5309   tree_merge_blocks,            /* merge_blocks  */
5310   tree_predict_edge,            /* predict_edge  */
5311   tree_predicted_by_p,          /* predicted_by_p  */
5312   tree_can_duplicate_bb_p,      /* can_duplicate_block_p  */
5313   tree_duplicate_bb,            /* duplicate_block  */
5314   tree_split_edge,              /* split_edge  */
5315   tree_make_forwarder_block,    /* make_forward_block  */
5316   NULL,                         /* tidy_fallthru_edge  */
5317   tree_block_ends_with_call_p,  /* block_ends_with_call_p */
5318   tree_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
5319   tree_flow_call_edges_add      /* flow_call_edges_add */
5320 };
5321
5322
5323 /* Split all critical edges.  */
5324
5325 static void
5326 split_critical_edges (void)
5327 {
5328   basic_block bb;
5329   edge e;
5330   edge_iterator ei;
5331
5332   FOR_ALL_BB (bb)
5333     {
5334       FOR_EACH_EDGE (e, ei, bb->succs)
5335         if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
5336           {
5337             split_edge (e);
5338           }
5339     }
5340 }
5341
5342 struct tree_opt_pass pass_split_crit_edges =
5343 {
5344   "crited",                          /* name */
5345   NULL,                          /* gate */
5346   split_critical_edges,          /* execute */
5347   NULL,                          /* sub */
5348   NULL,                          /* next */
5349   0,                             /* static_pass_number */
5350   TV_TREE_SPLIT_EDGES,           /* tv_id */
5351   PROP_cfg,                      /* properties required */
5352   PROP_no_crit_edges,            /* properties_provided */
5353   0,                             /* properties_destroyed */
5354   0,                             /* todo_flags_start */
5355   TODO_dump_func,                /* todo_flags_finish */
5356   0                              /* letter */
5357 };
5358
5359 \f
5360 /* Return EXP if it is a valid GIMPLE rvalue, else gimplify it into
5361    a temporary, make sure and register it to be renamed if necessary,
5362    and finally return the temporary.  Put the statements to compute
5363    EXP before the current statement in BSI.  */
5364
5365 tree
5366 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
5367 {
5368   tree t, new_stmt, orig_stmt;
5369
5370   if (is_gimple_val (exp))
5371     return exp;
5372
5373   t = make_rename_temp (type, NULL);
5374   new_stmt = build (MODIFY_EXPR, type, t, exp);
5375
5376   orig_stmt = bsi_stmt (*bsi);
5377   SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
5378   TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
5379
5380   bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
5381
5382   return t;
5383 }
5384
5385 /* Build a ternary operation and gimplify it.  Emit code before BSI.
5386    Return the gimple_val holding the result.  */
5387
5388 tree
5389 gimplify_build3 (block_stmt_iterator *bsi, enum tree_code code,
5390                  tree type, tree a, tree b, tree c)
5391 {
5392   tree ret;
5393
5394   ret = fold (build3 (code, type, a, b, c));
5395   STRIP_NOPS (ret);
5396
5397   return gimplify_val (bsi, type, ret);
5398 }
5399
5400 /* Build a binary operation and gimplify it.  Emit code before BSI.
5401    Return the gimple_val holding the result.  */
5402
5403 tree
5404 gimplify_build2 (block_stmt_iterator *bsi, enum tree_code code,
5405                  tree type, tree a, tree b)
5406 {
5407   tree ret;
5408
5409   ret = fold (build2 (code, type, a, b));
5410   STRIP_NOPS (ret);
5411
5412   return gimplify_val (bsi, type, ret);
5413 }
5414
5415 /* Build a unary operation and gimplify it.  Emit code before BSI.
5416    Return the gimple_val holding the result.  */
5417
5418 tree
5419 gimplify_build1 (block_stmt_iterator *bsi, enum tree_code code, tree type,
5420                  tree a)
5421 {
5422   tree ret;
5423
5424   ret = fold (build1 (code, type, a));
5425   STRIP_NOPS (ret);
5426
5427   return gimplify_val (bsi, type, ret);
5428 }
5429
5430
5431 \f
5432 /* Emit return warnings.  */
5433
5434 static void
5435 execute_warn_function_return (void)
5436 {
5437 #ifdef USE_MAPPED_LOCATION
5438   source_location location;
5439 #else
5440   location_t *locus;
5441 #endif
5442   tree last;
5443   edge e;
5444   edge_iterator ei;
5445
5446   if (warn_missing_noreturn
5447       && !TREE_THIS_VOLATILE (cfun->decl)
5448       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0
5449       && !lang_hooks.function.missing_noreturn_ok_p (cfun->decl))
5450     warning ("%Jfunction might be possible candidate for "
5451              "attribute %<noreturn%>",
5452              cfun->decl);
5453
5454   /* If we have a path to EXIT, then we do return.  */
5455   if (TREE_THIS_VOLATILE (cfun->decl)
5456       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
5457     {
5458 #ifdef USE_MAPPED_LOCATION
5459       location = UNKNOWN_LOCATION;
5460 #else
5461       locus = NULL;
5462 #endif
5463       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5464         {
5465           last = last_stmt (e->src);
5466           if (TREE_CODE (last) == RETURN_EXPR
5467 #ifdef USE_MAPPED_LOCATION
5468               && (location = EXPR_LOCATION (last)) != UNKNOWN_LOCATION)
5469 #else
5470               && (locus = EXPR_LOCUS (last)) != NULL)
5471 #endif
5472             break;
5473         }
5474 #ifdef USE_MAPPED_LOCATION
5475       if (location == UNKNOWN_LOCATION)
5476         location = cfun->function_end_locus;
5477       warning ("%H%<noreturn%> function does return", &location);
5478 #else
5479       if (!locus)
5480         locus = &cfun->function_end_locus;
5481       warning ("%H%<noreturn%> function does return", locus);
5482 #endif
5483     }
5484
5485   /* If we see "return;" in some basic block, then we do reach the end
5486      without returning a value.  */
5487   else if (warn_return_type
5488            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
5489            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
5490     {
5491       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
5492         {
5493           tree last = last_stmt (e->src);
5494           if (TREE_CODE (last) == RETURN_EXPR
5495               && TREE_OPERAND (last, 0) == NULL)
5496             {
5497 #ifdef USE_MAPPED_LOCATION
5498               location = EXPR_LOCATION (last);
5499               if (location == UNKNOWN_LOCATION)
5500                   location = cfun->function_end_locus;
5501               warning ("%Hcontrol reaches end of non-void function", &location);
5502 #else
5503               locus = EXPR_LOCUS (last);
5504               if (!locus)
5505                 locus = &cfun->function_end_locus;
5506               warning ("%Hcontrol reaches end of non-void function", locus);
5507 #endif
5508               break;
5509             }
5510         }
5511     }
5512 }
5513
5514
5515 /* Given a basic block B which ends with a conditional and has
5516    precisely two successors, determine which of the edges is taken if
5517    the conditional is true and which is taken if the conditional is
5518    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
5519
5520 void
5521 extract_true_false_edges_from_block (basic_block b,
5522                                      edge *true_edge,
5523                                      edge *false_edge)
5524 {
5525   edge e = EDGE_SUCC (b, 0);
5526
5527   if (e->flags & EDGE_TRUE_VALUE)
5528     {
5529       *true_edge = e;
5530       *false_edge = EDGE_SUCC (b, 1);
5531     }
5532   else
5533     {
5534       *false_edge = e;
5535       *true_edge = EDGE_SUCC (b, 1);
5536     }
5537 }
5538
5539 struct tree_opt_pass pass_warn_function_return =
5540 {
5541   NULL,                                 /* name */
5542   NULL,                                 /* gate */
5543   execute_warn_function_return,         /* execute */
5544   NULL,                                 /* sub */
5545   NULL,                                 /* next */
5546   0,                                    /* static_pass_number */
5547   0,                                    /* tv_id */
5548   PROP_cfg,                             /* properties_required */
5549   0,                                    /* properties_provided */
5550   0,                                    /* properties_destroyed */
5551   0,                                    /* todo_flags_start */
5552   0,                                    /* todo_flags_finish */
5553   0                                     /* letter */
5554 };
5555
5556 #include "gt-tree-cfg.h"