gcc/tree-cfg.c

   1 /* Control flow functions for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
   3    2010, 2011  Free Software Foundation, Inc.
   4    Contributed by Diego Novillo <dnovillo@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "tm_p.h"
  28 #include "basic-block.h"
  29 #include "output.h"
  30 #include "flags.h"
  31 #include "function.h"
  32 #include "ggc.h"
  33 #include "langhooks.h"
  34 #include "tree-pretty-print.h"
  35 #include "gimple-pretty-print.h"
  36 #include "tree-flow.h"
  37 #include "timevar.h"
  38 #include "tree-dump.h"
  39 #include "tree-pass.h"
  40 #include "diagnostic-core.h"
  41 #include "except.h"
  42 #include "cfgloop.h"
  43 #include "cfglayout.h"
  44 #include "tree-ssa-propagate.h"
  45 #include "value-prof.h"
  46 #include "pointer-set.h"
  47 #include "tree-inline.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 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs
  58    which use a particular edge.  The CASE_LABEL_EXPRs are chained together
  59    via their TREE_CHAIN field, which we clear after we're done with the
  60    hash table to prevent problems with duplication of GIMPLE_SWITCHes.
  61
  62    Access to this list of CASE_LABEL_EXPRs allows us to efficiently
  63    update the case vector in response to edge redirections.
  64
  65    Right now this table is set up and torn down at key points in the
  66    compilation process.  It would be nice if we could make the table
  67    more persistent.  The key is getting notification of changes to
  68    the CFG (particularly edge removal, creation and redirection).  */
  69
  70 static struct pointer_map_t *edge_to_cases;
  71
  72 /* If we record edge_to_cases, this bitmap will hold indexes
  73    of basic blocks that end in a GIMPLE_SWITCH which we touched
  74    due to edge manipulations.  */
  75
  76 static bitmap touched_switch_bbs;
  77
  78 /* CFG statistics.  */
  79 struct cfg_stats_d
  80 {
  81   long num_merged_labels;
  82 };
  83
  84 static struct cfg_stats_d cfg_stats;
  85
  86 /* Nonzero if we found a computed goto while building basic blocks.  */
  87 static bool found_computed_goto;
  88
  89 /* Hash table to store last discriminator assigned for each locus.  */
  90 struct locus_discrim_map
  91 {
  92   location_t locus;
  93   int discriminator;
  94 };
  95 static htab_t discriminator_per_locus;
  96
  97 /* Basic blocks and flowgraphs.  */
  98 static void make_blocks (gimple_seq);
  99 static void factor_computed_gotos (void);
 100
 101 /* Edges.  */
 102 static void make_edges (void);
 103 static void make_cond_expr_edges (basic_block);
 104 static void make_gimple_switch_edges (basic_block);
 105 static void make_goto_expr_edges (basic_block);
 106 static void make_gimple_asm_edges (basic_block);
 107 static unsigned int locus_map_hash (const void *);
 108 static int locus_map_eq (const void *, const void *);
 109 static void assign_discriminator (location_t, basic_block);
 110 static edge gimple_redirect_edge_and_branch (edge, basic_block);
 111 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block);
 112 static unsigned int split_critical_edges (void);
 113
 114 /* Various helpers.  */
 115 static inline bool stmt_starts_bb_p (gimple, gimple);
 116 static int gimple_verify_flow_info (void);
 117 static void gimple_make_forwarder_block (edge);
 118 static void gimple_cfg2vcg (FILE *);
 119 static gimple first_non_label_stmt (basic_block);
 120
 121 /* Flowgraph optimization and cleanup.  */
 122 static void gimple_merge_blocks (basic_block, basic_block);
 123 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
 124 static void remove_bb (basic_block);
 125 static edge find_taken_edge_computed_goto (basic_block, tree);
 126 static edge find_taken_edge_cond_expr (basic_block, tree);
 127 static edge find_taken_edge_switch_expr (basic_block, tree);
 128 static tree find_case_label_for_value (gimple, tree);
 129 static void group_case_labels_stmt (gimple);
 130
 131 void
 132 init_empty_tree_cfg_for_function (struct function *fn)
 133 {
 134   /* Initialize the basic block array.  */
 135   init_flow (fn);
 136   profile_status_for_function (fn) = PROFILE_ABSENT;
 137   n_basic_blocks_for_function (fn) = NUM_FIXED_BLOCKS;
 138   last_basic_block_for_function (fn) = NUM_FIXED_BLOCKS;
 139   basic_block_info_for_function (fn)
 140     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 141   VEC_safe_grow_cleared (basic_block, gc,
 142                          basic_block_info_for_function (fn),
 143                          initial_cfg_capacity);
 144
 145   /* Build a mapping of labels to their associated blocks.  */
 146   label_to_block_map_for_function (fn)
 147     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 148   VEC_safe_grow_cleared (basic_block, gc,
 149                          label_to_block_map_for_function (fn),
 150                          initial_cfg_capacity);
 151
 152   SET_BASIC_BLOCK_FOR_FUNCTION (fn, ENTRY_BLOCK,
 153                                 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn));
 154   SET_BASIC_BLOCK_FOR_FUNCTION (fn, EXIT_BLOCK,
 155                    EXIT_BLOCK_PTR_FOR_FUNCTION (fn));
 156
 157   ENTRY_BLOCK_PTR_FOR_FUNCTION (fn)->next_bb
 158     = EXIT_BLOCK_PTR_FOR_FUNCTION (fn);
 159   EXIT_BLOCK_PTR_FOR_FUNCTION (fn)->prev_bb
 160     = ENTRY_BLOCK_PTR_FOR_FUNCTION (fn);
 161 }
 162
 163 void
 164 init_empty_tree_cfg (void)
 165 {
 166   init_empty_tree_cfg_for_function (cfun);
 167 }
 168
 169 /*---------------------------------------------------------------------------
 170                               Create basic blocks
 171 ---------------------------------------------------------------------------*/
 172
 173 /* Entry point to the CFG builder for trees.  SEQ is the sequence of
 174    statements to be added to the flowgraph.  */
 175
 176 static void
 177 build_gimple_cfg (gimple_seq seq)
 178 {
 179   /* Register specific gimple functions.  */
 180   gimple_register_cfg_hooks ();
 181
 182   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
 183
 184   init_empty_tree_cfg ();
 185
 186   found_computed_goto = 0;
 187   make_blocks (seq);
 188
 189   /* Computed gotos are hell to deal with, especially if there are
 190      lots of them with a large number of destinations.  So we factor
 191      them to a common computed goto location before we build the
 192      edge list.  After we convert back to normal form, we will un-factor
 193      the computed gotos since factoring introduces an unwanted jump.  */
 194   if (found_computed_goto)
 195     factor_computed_gotos ();
 196
 197   /* Make sure there is always at least one block, even if it's empty.  */
 198   if (n_basic_blocks == NUM_FIXED_BLOCKS)
 199     create_empty_bb (ENTRY_BLOCK_PTR);
 200
 201   /* Adjust the size of the array.  */
 202   if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
 203     VEC_safe_grow_cleared (basic_block, gc, basic_block_info, n_basic_blocks);
 204
 205   /* To speed up statement iterator walks, we first purge dead labels.  */
 206   cleanup_dead_labels ();
 207
 208   /* Group case nodes to reduce the number of edges.
 209      We do this after cleaning up dead labels because otherwise we miss
 210      a lot of obvious case merging opportunities.  */
 211   group_case_labels ();
 212
 213   /* Create the edges of the flowgraph.  */
 214   discriminator_per_locus = htab_create (13, locus_map_hash, locus_map_eq,
 215                                          free);
 216   make_edges ();
 217   cleanup_dead_labels ();
 218   htab_delete (discriminator_per_locus);
 219
 220   /* Debugging dumps.  */
 221
 222   /* Write the flowgraph to a VCG file.  */
 223   {
 224     int local_dump_flags;
 225     FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
 226     if (vcg_file)
 227       {
 228         gimple_cfg2vcg (vcg_file);
 229         dump_end (TDI_vcg, vcg_file);
 230       }
 231   }
 232 }
 233
 234 static unsigned int
 235 execute_build_cfg (void)
 236 {
 237   gimple_seq body = gimple_body (current_function_decl);
 238
 239   build_gimple_cfg (body);
 240   gimple_set_body (current_function_decl, NULL);
 241   if (dump_file && (dump_flags & TDF_DETAILS))
 242     {
 243       fprintf (dump_file, "Scope blocks:\n");
 244       dump_scope_blocks (dump_file, dump_flags);
 245     }
 246   return 0;
 247 }
 248
 249 struct gimple_opt_pass pass_build_cfg =
 250 {
 251  {
 252   GIMPLE_PASS,
 253   "cfg",                                /* name */
 254   NULL,                                 /* gate */
 255   execute_build_cfg,                    /* execute */
 256   NULL,                                 /* sub */
 257   NULL,                                 /* next */
 258   0,                                    /* static_pass_number */
 259   TV_TREE_CFG,                          /* tv_id */
 260   PROP_gimple_leh,                      /* properties_required */
 261   PROP_cfg,                             /* properties_provided */
 262   0,                                    /* properties_destroyed */
 263   0,                                    /* todo_flags_start */
 264   TODO_verify_stmts | TODO_cleanup_cfg  /* todo_flags_finish */
 265  }
 266 };
 267
 268
 269 /* Return true if T is a computed goto.  */
 270
 271 static bool
 272 computed_goto_p (gimple t)
 273 {
 274   return (gimple_code (t) == GIMPLE_GOTO
 275           && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
 276 }
 277
 278
 279 /* Search the CFG for any computed gotos.  If found, factor them to a
 280    common computed goto site.  Also record the location of that site so
 281    that we can un-factor the gotos after we have converted back to
 282    normal form.  */
 283
 284 static void
 285 factor_computed_gotos (void)
 286 {
 287   basic_block bb;
 288   tree factored_label_decl = NULL;
 289   tree var = NULL;
 290   gimple factored_computed_goto_label = NULL;
 291   gimple factored_computed_goto = NULL;
 292
 293   /* We know there are one or more computed gotos in this function.
 294      Examine the last statement in each basic block to see if the block
 295      ends with a computed goto.  */
 296
 297   FOR_EACH_BB (bb)
 298     {
 299       gimple_stmt_iterator gsi = gsi_last_bb (bb);
 300       gimple last;
 301
 302       if (gsi_end_p (gsi))
 303         continue;
 304
 305       last = gsi_stmt (gsi);
 306
 307       /* Ignore the computed goto we create when we factor the original
 308          computed gotos.  */
 309       if (last == factored_computed_goto)
 310         continue;
 311
 312       /* If the last statement is a computed goto, factor it.  */
 313       if (computed_goto_p (last))
 314         {
 315           gimple assignment;
 316
 317           /* The first time we find a computed goto we need to create
 318              the factored goto block and the variable each original
 319              computed goto will use for their goto destination.  */
 320           if (!factored_computed_goto)
 321             {
 322               basic_block new_bb = create_empty_bb (bb);
 323               gimple_stmt_iterator new_gsi = gsi_start_bb (new_bb);
 324
 325               /* Create the destination of the factored goto.  Each original
 326                  computed goto will put its desired destination into this
 327                  variable and jump to the label we create immediately
 328                  below.  */
 329               var = create_tmp_var (ptr_type_node, "gotovar");
 330
 331               /* Build a label for the new block which will contain the
 332                  factored computed goto.  */
 333               factored_label_decl = create_artificial_label (UNKNOWN_LOCATION);
 334               factored_computed_goto_label
 335                 = gimple_build_label (factored_label_decl);
 336               gsi_insert_after (&new_gsi, factored_computed_goto_label,
 337                                 GSI_NEW_STMT);
 338
 339               /* Build our new computed goto.  */
 340               factored_computed_goto = gimple_build_goto (var);
 341               gsi_insert_after (&new_gsi, factored_computed_goto, GSI_NEW_STMT);
 342             }
 343
 344           /* Copy the original computed goto's destination into VAR.  */
 345           assignment = gimple_build_assign (var, gimple_goto_dest (last));
 346           gsi_insert_before (&gsi, assignment, GSI_SAME_STMT);
 347
 348           /* And re-vector the computed goto to the new destination.  */
 349           gimple_goto_set_dest (last, factored_label_decl);
 350         }
 351     }
 352 }
 353
 354
 355 /* Build a flowgraph for the sequence of stmts SEQ.  */
 356
 357 static void
 358 make_blocks (gimple_seq seq)
 359 {
 360   gimple_stmt_iterator i = gsi_start (seq);
 361   gimple stmt = NULL;
 362   bool start_new_block = true;
 363   bool first_stmt_of_seq = true;
 364   basic_block bb = ENTRY_BLOCK_PTR;
 365
 366   while (!gsi_end_p (i))
 367     {
 368       gimple prev_stmt;
 369
 370       prev_stmt = stmt;
 371       stmt = gsi_stmt (i);
 372
 373       /* If the statement starts a new basic block or if we have determined
 374          in a previous pass that we need to create a new block for STMT, do
 375          so now.  */
 376       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
 377         {
 378           if (!first_stmt_of_seq)
 379             seq = gsi_split_seq_before (&i);
 380           bb = create_basic_block (seq, NULL, bb);
 381           start_new_block = false;
 382         }
 383
 384       /* Now add STMT to BB and create the subgraphs for special statement
 385          codes.  */
 386       gimple_set_bb (stmt, bb);
 387
 388       if (computed_goto_p (stmt))
 389         found_computed_goto = true;
 390
 391       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
 392          next iteration.  */
 393       if (stmt_ends_bb_p (stmt))
 394         {
 395           /* If the stmt can make abnormal goto use a new temporary
 396              for the assignment to the LHS.  This makes sure the old value
 397              of the LHS is available on the abnormal edge.  Otherwise
 398              we will end up with overlapping life-ranges for abnormal
 399              SSA names.  */
 400           if (gimple_has_lhs (stmt)
 401               && stmt_can_make_abnormal_goto (stmt)
 402               && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt))))
 403             {
 404               tree lhs = gimple_get_lhs (stmt);
 405               tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
 406               gimple s = gimple_build_assign (lhs, tmp);
 407               gimple_set_location (s, gimple_location (stmt));
 408               gimple_set_block (s, gimple_block (stmt));
 409               gimple_set_lhs (stmt, tmp);
 410               if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE
 411                   || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE)
 412                 DECL_GIMPLE_REG_P (tmp) = 1;
 413               gsi_insert_after (&i, s, GSI_SAME_STMT);
 414             }
 415           start_new_block = true;
 416         }
 417
 418       gsi_next (&i);
 419       first_stmt_of_seq = false;
 420     }
 421 }
 422
 423
 424 /* Create and return a new empty basic block after bb AFTER.  */
 425
 426 static basic_block
 427 create_bb (void *h, void *e, basic_block after)
 428 {
 429   basic_block bb;
 430
 431   gcc_assert (!e);
 432
 433   /* Create and initialize a new basic block.  Since alloc_block uses
 434      GC allocation that clears memory to allocate a basic block, we do
 435      not have to clear the newly allocated basic block here.  */
 436   bb = alloc_block ();
 437
 438   bb->index = last_basic_block;
 439   bb->flags = BB_NEW;
 440   bb->il.gimple = ggc_alloc_cleared_gimple_bb_info ();
 441   set_bb_seq (bb, h ? (gimple_seq) h : gimple_seq_alloc ());
 442
 443   /* Add the new block to the linked list of blocks.  */
 444   link_block (bb, after);
 445
 446   /* Grow the basic block array if needed.  */
 447   if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
 448     {
 449       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
 450       VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
 451     }
 452
 453   /* Add the newly created block to the array.  */
 454   SET_BASIC_BLOCK (last_basic_block, bb);
 455
 456   n_basic_blocks++;
 457   last_basic_block++;
 458
 459   return bb;
 460 }
 461
 462
 463 /*---------------------------------------------------------------------------
 464                                  Edge creation
 465 ---------------------------------------------------------------------------*/
 466
 467 /* Fold COND_EXPR_COND of each COND_EXPR.  */
 468
 469 void
 470 fold_cond_expr_cond (void)
 471 {
 472   basic_block bb;
 473
 474   FOR_EACH_BB (bb)
 475     {
 476       gimple stmt = last_stmt (bb);
 477
 478       if (stmt && gimple_code (stmt) == GIMPLE_COND)
 479         {
 480           location_t loc = gimple_location (stmt);
 481           tree cond;
 482           bool zerop, onep;
 483
 484           fold_defer_overflow_warnings ();
 485           cond = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node,
 486                               gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 487           if (cond)
 488             {
 489               zerop = integer_zerop (cond);
 490               onep = integer_onep (cond);
 491             }
 492           else
 493             zerop = onep = false;
 494
 495           fold_undefer_overflow_warnings (zerop || onep,
 496                                           stmt,
 497                                           WARN_STRICT_OVERFLOW_CONDITIONAL);
 498           if (zerop)
 499             gimple_cond_make_false (stmt);
 500           else if (onep)
 501             gimple_cond_make_true (stmt);
 502         }
 503     }
 504 }
 505
 506 /* Join all the blocks in the flowgraph.  */
 507
 508 static void
 509 make_edges (void)
 510 {
 511   basic_block bb;
 512   struct omp_region *cur_region = NULL;
 513
 514   /* Create an edge from entry to the first block with executable
 515      statements in it.  */
 516   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
 517
 518   /* Traverse the basic block array placing edges.  */
 519   FOR_EACH_BB (bb)
 520     {
 521       gimple last = last_stmt (bb);
 522       bool fallthru;
 523
 524       if (last)
 525         {
 526           enum gimple_code code = gimple_code (last);
 527           switch (code)
 528             {
 529             case GIMPLE_GOTO:
 530               make_goto_expr_edges (bb);
 531               fallthru = false;
 532               break;
 533             case GIMPLE_RETURN:
 534               make_edge (bb, EXIT_BLOCK_PTR, 0);
 535               fallthru = false;
 536               break;
 537             case GIMPLE_COND:
 538               make_cond_expr_edges (bb);
 539               fallthru = false;
 540               break;
 541             case GIMPLE_SWITCH:
 542               make_gimple_switch_edges (bb);
 543               fallthru = false;
 544               break;
 545             case GIMPLE_RESX:
 546               make_eh_edges (last);
 547               fallthru = false;
 548               break;
 549             case GIMPLE_EH_DISPATCH:
 550               fallthru = make_eh_dispatch_edges (last);
 551               break;
 552
 553             case GIMPLE_CALL:
 554               /* If this function receives a nonlocal goto, then we need to
 555                  make edges from this call site to all the nonlocal goto
 556                  handlers.  */
 557               if (stmt_can_make_abnormal_goto (last))
 558                 make_abnormal_goto_edges (bb, true);
 559
 560               /* If this statement has reachable exception handlers, then
 561                  create abnormal edges to them.  */
 562               make_eh_edges (last);
 563
 564               /* BUILTIN_RETURN is really a return statement.  */
 565               if (gimple_call_builtin_p (last, BUILT_IN_RETURN))
 566                 make_edge (bb, EXIT_BLOCK_PTR, 0), fallthru = false;
 567               /* Some calls are known not to return.  */
 568               else
 569                 fallthru = !(gimple_call_flags (last) & ECF_NORETURN);
 570               break;
 571
 572             case GIMPLE_ASSIGN:
 573                /* A GIMPLE_ASSIGN may throw internally and thus be considered
 574                   control-altering. */
 575               if (is_ctrl_altering_stmt (last))
 576                 make_eh_edges (last);
 577               fallthru = true;
 578               break;
 579
 580             case GIMPLE_ASM:
 581               make_gimple_asm_edges (bb);
 582               fallthru = true;
 583               break;
 584
 585             case GIMPLE_OMP_PARALLEL:
 586             case GIMPLE_OMP_TASK:
 587             case GIMPLE_OMP_FOR:
 588             case GIMPLE_OMP_SINGLE:
 589             case GIMPLE_OMP_MASTER:
 590             case GIMPLE_OMP_ORDERED:
 591             case GIMPLE_OMP_CRITICAL:
 592             case GIMPLE_OMP_SECTION:
 593               cur_region = new_omp_region (bb, code, cur_region);
 594               fallthru = true;
 595               break;
 596
 597             case GIMPLE_OMP_SECTIONS:
 598               cur_region = new_omp_region (bb, code, cur_region);
 599               fallthru = true;
 600               break;
 601
 602             case GIMPLE_OMP_SECTIONS_SWITCH:
 603               fallthru = false;
 604               break;
 605
 606             case GIMPLE_OMP_ATOMIC_LOAD:
 607             case GIMPLE_OMP_ATOMIC_STORE:
 608                fallthru = true;
 609                break;
 610
 611             case GIMPLE_OMP_RETURN:
 612               /* In the case of a GIMPLE_OMP_SECTION, the edge will go
 613                  somewhere other than the next block.  This will be
 614                  created later.  */
 615               cur_region->exit = bb;
 616               fallthru = cur_region->type != GIMPLE_OMP_SECTION;
 617               cur_region = cur_region->outer;
 618               break;
 619
 620             case GIMPLE_OMP_CONTINUE:
 621               cur_region->cont = bb;
 622               switch (cur_region->type)
 623                 {
 624                 case GIMPLE_OMP_FOR:
 625                   /* Mark all GIMPLE_OMP_FOR and GIMPLE_OMP_CONTINUE
 626                      succs edges as abnormal to prevent splitting
 627                      them.  */
 628                   single_succ_edge (cur_region->entry)->flags |= EDGE_ABNORMAL;
 629                   /* Make the loopback edge.  */
 630                   make_edge (bb, single_succ (cur_region->entry),
 631                              EDGE_ABNORMAL);
 632
 633                   /* Create an edge from GIMPLE_OMP_FOR to exit, which
 634                      corresponds to the case that the body of the loop
 635                      is not executed at all.  */
 636                   make_edge (cur_region->entry, bb->next_bb, EDGE_ABNORMAL);
 637                   make_edge (bb, bb->next_bb, EDGE_FALLTHRU | EDGE_ABNORMAL);
 638                   fallthru = false;
 639                   break;
 640
 641                 case GIMPLE_OMP_SECTIONS:
 642                   /* Wire up the edges into and out of the nested sections.  */
 643                   {
 644                     basic_block switch_bb = single_succ (cur_region->entry);
 645
 646                     struct omp_region *i;
 647                     for (i = cur_region->inner; i ; i = i->next)
 648                       {
 649                         gcc_assert (i->type == GIMPLE_OMP_SECTION);
 650                         make_edge (switch_bb, i->entry, 0);
 651                         make_edge (i->exit, bb, EDGE_FALLTHRU);
 652                       }
 653
 654                     /* Make the loopback edge to the block with
 655                        GIMPLE_OMP_SECTIONS_SWITCH.  */
 656                     make_edge (bb, switch_bb, 0);
 657
 658                     /* Make the edge from the switch to exit.  */
 659                     make_edge (switch_bb, bb->next_bb, 0);
 660                     fallthru = false;
 661                   }
 662                   break;
 663
 664                 default:
 665                   gcc_unreachable ();
 666                 }
 667               break;
 668
 669             default:
 670               gcc_assert (!stmt_ends_bb_p (last));
 671               fallthru = true;
 672             }
 673         }
 674       else
 675         fallthru = true;
 676
 677       if (fallthru)
 678         {
 679           make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 680           if (last)
 681             assign_discriminator (gimple_location (last), bb->next_bb);
 682         }
 683     }
 684
 685   if (root_omp_region)
 686     free_omp_regions ();
 687
 688   /* Fold COND_EXPR_COND of each COND_EXPR.  */
 689   fold_cond_expr_cond ();
 690 }
 691
 692 /* Trivial hash function for a location_t.  ITEM is a pointer to
 693    a hash table entry that maps a location_t to a discriminator.  */
 694
 695 static unsigned int
 696 locus_map_hash (const void *item)
 697 {
 698   return ((const struct locus_discrim_map *) item)->locus;
 699 }
 700
 701 /* Equality function for the locus-to-discriminator map.  VA and VB
 702    point to the two hash table entries to compare.  */
 703
 704 static int
 705 locus_map_eq (const void *va, const void *vb)
 706 {
 707   const struct locus_discrim_map *a = (const struct locus_discrim_map *) va;
 708   const struct locus_discrim_map *b = (const struct locus_discrim_map *) vb;
 709   return a->locus == b->locus;
 710 }
 711
 712 /* Find the next available discriminator value for LOCUS.  The
 713    discriminator distinguishes among several basic blocks that
 714    share a common locus, allowing for more accurate sample-based
 715    profiling.  */
 716
 717 static int
 718 next_discriminator_for_locus (location_t locus)
 719 {
 720   struct locus_discrim_map item;
 721   struct locus_discrim_map **slot;
 722
 723   item.locus = locus;
 724   item.discriminator = 0;
 725   slot = (struct locus_discrim_map **)
 726       htab_find_slot_with_hash (discriminator_per_locus, (void *) &item,
 727                                 (hashval_t) locus, INSERT);
 728   gcc_assert (slot);
 729   if (*slot == HTAB_EMPTY_ENTRY)
 730     {
 731       *slot = XNEW (struct locus_discrim_map);
 732       gcc_assert (*slot);
 733       (*slot)->locus = locus;
 734       (*slot)->discriminator = 0;
 735     }
 736   (*slot)->discriminator++;
 737   return (*slot)->discriminator;
 738 }
 739
 740 /* Return TRUE if LOCUS1 and LOCUS2 refer to the same source line.  */
 741
 742 static bool
 743 same_line_p (location_t locus1, location_t locus2)
 744 {
 745   expanded_location from, to;
 746
 747   if (locus1 == locus2)
 748     return true;
 749
 750   from = expand_location (locus1);
 751   to = expand_location (locus2);
 752
 753   if (from.line != to.line)
 754     return false;
 755   if (from.file == to.file)
 756     return true;
 757   return (from.file != NULL
 758           && to.file != NULL
 759           && filename_cmp (from.file, to.file) == 0);
 760 }
 761
 762 /* Assign a unique discriminator value to block BB if it begins at the same
 763    LOCUS as its predecessor block.  */
 764
 765 static void
 766 assign_discriminator (location_t locus, basic_block bb)
 767 {
 768   gimple first_in_to_bb, last_in_to_bb;
 769
 770   if (locus == 0 || bb->discriminator != 0)
 771     return;
 772
 773   first_in_to_bb = first_non_label_stmt (bb);
 774   last_in_to_bb = last_stmt (bb);
 775   if ((first_in_to_bb && same_line_p (locus, gimple_location (first_in_to_bb)))
 776       || (last_in_to_bb && same_line_p (locus, gimple_location (last_in_to_bb))))
 777     bb->discriminator = next_discriminator_for_locus (locus);
 778 }
 779
 780 /* Create the edges for a GIMPLE_COND starting at block BB.  */
 781
 782 static void
 783 make_cond_expr_edges (basic_block bb)
 784 {
 785   gimple entry = last_stmt (bb);
 786   gimple then_stmt, else_stmt;
 787   basic_block then_bb, else_bb;
 788   tree then_label, else_label;
 789   edge e;
 790   location_t entry_locus;
 791
 792   gcc_assert (entry);
 793   gcc_assert (gimple_code (entry) == GIMPLE_COND);
 794
 795   entry_locus = gimple_location (entry);
 796
 797   /* Entry basic blocks for each component.  */
 798   then_label = gimple_cond_true_label (entry);
 799   else_label = gimple_cond_false_label (entry);
 800   then_bb = label_to_block (then_label);
 801   else_bb = label_to_block (else_label);
 802   then_stmt = first_stmt (then_bb);
 803   else_stmt = first_stmt (else_bb);
 804
 805   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
 806   assign_discriminator (entry_locus, then_bb);
 807   e->goto_locus = gimple_location (then_stmt);
 808   if (e->goto_locus)
 809     e->goto_block = gimple_block (then_stmt);
 810   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
 811   if (e)
 812     {
 813       assign_discriminator (entry_locus, else_bb);
 814       e->goto_locus = gimple_location (else_stmt);
 815       if (e->goto_locus)
 816         e->goto_block = gimple_block (else_stmt);
 817     }
 818
 819   /* We do not need the labels anymore.  */
 820   gimple_cond_set_true_label (entry, NULL_TREE);
 821   gimple_cond_set_false_label (entry, NULL_TREE);
 822 }
 823
 824
 825 /* Called for each element in the hash table (P) as we delete the
 826    edge to cases hash table.
 827
 828    Clear all the TREE_CHAINs to prevent problems with copying of
 829    SWITCH_EXPRs and structure sharing rules, then free the hash table
 830    element.  */
 831
 832 static bool
 833 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
 834                        void *data ATTRIBUTE_UNUSED)
 835 {
 836   tree t, next;
 837
 838   for (t = (tree) *value; t; t = next)
 839     {
 840       next = CASE_CHAIN (t);
 841       CASE_CHAIN (t) = NULL;
 842     }
 843
 844   *value = NULL;
 845   return true;
 846 }
 847
 848 /* Start recording information mapping edges to case labels.  */
 849
 850 void
 851 start_recording_case_labels (void)
 852 {
 853   gcc_assert (edge_to_cases == NULL);
 854   edge_to_cases = pointer_map_create ();
 855   touched_switch_bbs = BITMAP_ALLOC (NULL);
 856 }
 857
 858 /* Return nonzero if we are recording information for case labels.  */
 859
 860 static bool
 861 recording_case_labels_p (void)
 862 {
 863   return (edge_to_cases != NULL);
 864 }
 865
 866 /* Stop recording information mapping edges to case labels and
 867    remove any information we have recorded.  */
 868 void
 869 end_recording_case_labels (void)
 870 {
 871   bitmap_iterator bi;
 872   unsigned i;
 873   pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
 874   pointer_map_destroy (edge_to_cases);
 875   edge_to_cases = NULL;
 876   EXECUTE_IF_SET_IN_BITMAP (touched_switch_bbs, 0, i, bi)
 877     {
 878       basic_block bb = BASIC_BLOCK (i);
 879       if (bb)
 880         {
 881           gimple stmt = last_stmt (bb);
 882           if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
 883             group_case_labels_stmt (stmt);
 884         }
 885     }
 886   BITMAP_FREE (touched_switch_bbs);
 887 }
 888
 889 /* If we are inside a {start,end}_recording_cases block, then return
 890    a chain of CASE_LABEL_EXPRs from T which reference E.
 891
 892    Otherwise return NULL.  */
 893
 894 static tree
 895 get_cases_for_edge (edge e, gimple t)
 896 {
 897   void **slot;
 898   size_t i, n;
 899
 900   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
 901      chains available.  Return NULL so the caller can detect this case.  */
 902   if (!recording_case_labels_p ())
 903     return NULL;
 904
 905   slot = pointer_map_contains (edge_to_cases, e);
 906   if (slot)
 907     return (tree) *slot;
 908
 909   /* If we did not find E in the hash table, then this must be the first
 910      time we have been queried for information about E & T.  Add all the
 911      elements from T to the hash table then perform the query again.  */
 912
 913   n = gimple_switch_num_labels (t);
 914   for (i = 0; i < n; i++)
 915     {
 916       tree elt = gimple_switch_label (t, i);
 917       tree lab = CASE_LABEL (elt);
 918       basic_block label_bb = label_to_block (lab);
 919       edge this_edge = find_edge (e->src, label_bb);
 920
 921       /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
 922          a new chain.  */
 923       slot = pointer_map_insert (edge_to_cases, this_edge);
 924       CASE_CHAIN (elt) = (tree) *slot;
 925       *slot = elt;
 926     }
 927
 928   return (tree) *pointer_map_contains (edge_to_cases, e);
 929 }
 930
 931 /* Create the edges for a GIMPLE_SWITCH starting at block BB.  */
 932
 933 static void
 934 make_gimple_switch_edges (basic_block bb)
 935 {
 936   gimple entry = last_stmt (bb);
 937   location_t entry_locus;
 938   size_t i, n;
 939
 940   entry_locus = gimple_location (entry);
 941
 942   n = gimple_switch_num_labels (entry);
 943
 944   for (i = 0; i < n; ++i)
 945     {
 946       tree lab = CASE_LABEL (gimple_switch_label (entry, i));
 947       basic_block label_bb = label_to_block (lab);
 948       make_edge (bb, label_bb, 0);
 949       assign_discriminator (entry_locus, label_bb);
 950     }
 951 }
 952
 953
 954 /* Return the basic block holding label DEST.  */
 955
 956 basic_block
 957 label_to_block_fn (struct function *ifun, tree dest)
 958 {
 959   int uid = LABEL_DECL_UID (dest);
 960
 961   /* We would die hard when faced by an undefined label.  Emit a label to
 962      the very first basic block.  This will hopefully make even the dataflow
 963      and undefined variable warnings quite right.  */
 964   if (seen_error () && uid < 0)
 965     {
 966       gimple_stmt_iterator gsi = gsi_start_bb (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 967       gimple stmt;
 968
 969       stmt = gimple_build_label (dest);
 970       gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 971       uid = LABEL_DECL_UID (dest);
 972     }
 973   if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
 974       <= (unsigned int) uid)
 975     return NULL;
 976   return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
 977 }
 978
 979 /* Create edges for an abnormal goto statement at block BB.  If FOR_CALL
 980    is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR.  */
 981
 982 void
 983 make_abnormal_goto_edges (basic_block bb, bool for_call)
 984 {
 985   basic_block target_bb;
 986   gimple_stmt_iterator gsi;
 987
 988   FOR_EACH_BB (target_bb)
 989     for (gsi = gsi_start_bb (target_bb); !gsi_end_p (gsi); gsi_next (&gsi))
 990       {
 991         gimple label_stmt = gsi_stmt (gsi);
 992         tree target;
 993
 994         if (gimple_code (label_stmt) != GIMPLE_LABEL)
 995           break;
 996
 997         target = gimple_label_label (label_stmt);
 998
 999         /* Make an edge to every label block that has been marked as a
1000            potential target for a computed goto or a non-local goto.  */
1001         if ((FORCED_LABEL (target) && !for_call)
1002             || (DECL_NONLOCAL (target) && for_call))
1003           {
1004             make_edge (bb, target_bb, EDGE_ABNORMAL);
1005             break;
1006           }
1007       }
1008 }
1009
1010 /* Create edges for a goto statement at block BB.  */
1011
1012 static void
1013 make_goto_expr_edges (basic_block bb)
1014 {
1015   gimple_stmt_iterator last = gsi_last_bb (bb);
1016   gimple goto_t = gsi_stmt (last);
1017
1018   /* A simple GOTO creates normal edges.  */
1019   if (simple_goto_p (goto_t))
1020     {
1021       tree dest = gimple_goto_dest (goto_t);
1022       basic_block label_bb = label_to_block (dest);
1023       edge e = make_edge (bb, label_bb, EDGE_FALLTHRU);
1024       e->goto_locus = gimple_location (goto_t);
1025       assign_discriminator (e->goto_locus, label_bb);
1026       if (e->goto_locus)
1027         e->goto_block = gimple_block (goto_t);
1028       gsi_remove (&last, true);
1029       return;
1030     }
1031
1032   /* A computed GOTO creates abnormal edges.  */
1033   make_abnormal_goto_edges (bb, false);
1034 }
1035
1036 /* Create edges for an asm statement with labels at block BB.  */
1037
1038 static void
1039 make_gimple_asm_edges (basic_block bb)
1040 {
1041   gimple stmt = last_stmt (bb);
1042   location_t stmt_loc = gimple_location (stmt);
1043   int i, n = gimple_asm_nlabels (stmt);
1044
1045   for (i = 0; i < n; ++i)
1046     {
1047       tree label = TREE_VALUE (gimple_asm_label_op (stmt, i));
1048       basic_block label_bb = label_to_block (label);
1049       make_edge (bb, label_bb, 0);
1050       assign_discriminator (stmt_loc, label_bb);
1051     }
1052 }
1053
1054 /*---------------------------------------------------------------------------
1055                                Flowgraph analysis
1056 ---------------------------------------------------------------------------*/
1057
1058 /* Cleanup useless labels in basic blocks.  This is something we wish
1059    to do early because it allows us to group case labels before creating
1060    the edges for the CFG, and it speeds up block statement iterators in
1061    all passes later on.
1062    We rerun this pass after CFG is created, to get rid of the labels that
1063    are no longer referenced.  After then we do not run it any more, since
1064    (almost) no new labels should be created.  */
1065
1066 /* A map from basic block index to the leading label of that block.  */
1067 static struct label_record
1068 {
1069   /* The label.  */
1070   tree label;
1071
1072   /* True if the label is referenced from somewhere.  */
1073   bool used;
1074 } *label_for_bb;
1075
1076 /* Given LABEL return the first label in the same basic block.  */
1077
1078 static tree
1079 main_block_label (tree label)
1080 {
1081   basic_block bb = label_to_block (label);
1082   tree main_label = label_for_bb[bb->index].label;
1083
1084   /* label_to_block possibly inserted undefined label into the chain.  */
1085   if (!main_label)
1086     {
1087       label_for_bb[bb->index].label = label;
1088       main_label = label;
1089     }
1090
1091   label_for_bb[bb->index].used = true;
1092   return main_label;
1093 }
1094
1095 /* Clean up redundant labels within the exception tree.  */
1096
1097 static void
1098 cleanup_dead_labels_eh (void)
1099 {
1100   eh_landing_pad lp;
1101   eh_region r;
1102   tree lab;
1103   int i;
1104
1105   if (cfun->eh == NULL)
1106     return;
1107
1108   for (i = 1; VEC_iterate (eh_landing_pad, cfun->eh->lp_array, i, lp); ++i)
1109     if (lp && lp->post_landing_pad)
1110       {
1111         lab = main_block_label (lp->post_landing_pad);
1112         if (lab != lp->post_landing_pad)
1113           {
1114             EH_LANDING_PAD_NR (lp->post_landing_pad) = 0;
1115             EH_LANDING_PAD_NR (lab) = lp->index;
1116           }
1117       }
1118
1119   FOR_ALL_EH_REGION (r)
1120     switch (r->type)
1121       {
1122       case ERT_CLEANUP:
1123       case ERT_MUST_NOT_THROW:
1124         break;
1125
1126       case ERT_TRY:
1127         {
1128           eh_catch c;
1129           for (c = r->u.eh_try.first_catch; c ; c = c->next_catch)
1130             {
1131               lab = c->label;
1132               if (lab)
1133                 c->label = main_block_label (lab);
1134             }
1135         }
1136         break;
1137
1138       case ERT_ALLOWED_EXCEPTIONS:
1139         lab = r->u.allowed.label;
1140         if (lab)
1141           r->u.allowed.label = main_block_label (lab);
1142         break;
1143       }
1144 }
1145
1146
1147 /* Cleanup redundant labels.  This is a three-step process:
1148      1) Find the leading label for each block.
1149      2) Redirect all references to labels to the leading labels.
1150      3) Cleanup all useless labels.  */
1151
1152 void
1153 cleanup_dead_labels (void)
1154 {
1155   basic_block bb;
1156   label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
1157
1158   /* Find a suitable label for each block.  We use the first user-defined
1159      label if there is one, or otherwise just the first label we see.  */
1160   FOR_EACH_BB (bb)
1161     {
1162       gimple_stmt_iterator i;
1163
1164       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
1165         {
1166           tree label;
1167           gimple stmt = gsi_stmt (i);
1168
1169           if (gimple_code (stmt) != GIMPLE_LABEL)
1170             break;
1171
1172           label = gimple_label_label (stmt);
1173
1174           /* If we have not yet seen a label for the current block,
1175              remember this one and see if there are more labels.  */
1176           if (!label_for_bb[bb->index].label)
1177             {
1178               label_for_bb[bb->index].label = label;
1179               continue;
1180             }
1181
1182           /* If we did see a label for the current block already, but it
1183              is an artificially created label, replace it if the current
1184              label is a user defined label.  */
1185           if (!DECL_ARTIFICIAL (label)
1186               && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
1187             {
1188               label_for_bb[bb->index].label = label;
1189               break;
1190             }
1191         }
1192     }
1193
1194   /* Now redirect all jumps/branches to the selected label.
1195      First do so for each block ending in a control statement.  */
1196   FOR_EACH_BB (bb)
1197     {
1198       gimple stmt = last_stmt (bb);
1199       if (!stmt)
1200         continue;
1201
1202       switch (gimple_code (stmt))
1203         {
1204         case GIMPLE_COND:
1205           {
1206             tree true_label = gimple_cond_true_label (stmt);
1207             tree false_label = gimple_cond_false_label (stmt);
1208
1209             if (true_label)
1210               gimple_cond_set_true_label (stmt, main_block_label (true_label));
1211             if (false_label)
1212               gimple_cond_set_false_label (stmt, main_block_label (false_label));
1213             break;
1214           }
1215
1216         case GIMPLE_SWITCH:
1217           {
1218             size_t i, n = gimple_switch_num_labels (stmt);
1219
1220             /* Replace all destination labels.  */
1221             for (i = 0; i < n; ++i)
1222               {
1223                 tree case_label = gimple_switch_label (stmt, i);
1224                 tree label = main_block_label (CASE_LABEL (case_label));
1225                 CASE_LABEL (case_label) = label;
1226               }
1227             break;
1228           }
1229
1230         case GIMPLE_ASM:
1231           {
1232             int i, n = gimple_asm_nlabels (stmt);
1233
1234             for (i = 0; i < n; ++i)
1235               {
1236                 tree cons = gimple_asm_label_op (stmt, i);
1237                 tree label = main_block_label (TREE_VALUE (cons));
1238                 TREE_VALUE (cons) = label;
1239               }
1240             break;
1241           }
1242
1243         /* We have to handle gotos until they're removed, and we don't
1244            remove them until after we've created the CFG edges.  */
1245         case GIMPLE_GOTO:
1246           if (!computed_goto_p (stmt))
1247             {
1248               tree new_dest = main_block_label (gimple_goto_dest (stmt));
1249               gimple_goto_set_dest (stmt, new_dest);
1250             }
1251           break;
1252
1253         default:
1254           break;
1255       }
1256     }
1257
1258   /* Do the same for the exception region tree labels.  */
1259   cleanup_dead_labels_eh ();
1260
1261   /* Finally, purge dead labels.  All user-defined labels and labels that
1262      can be the target of non-local gotos and labels which have their
1263      address taken are preserved.  */
1264   FOR_EACH_BB (bb)
1265     {
1266       gimple_stmt_iterator i;
1267       tree label_for_this_bb = label_for_bb[bb->index].label;
1268
1269       if (!label_for_this_bb)
1270         continue;
1271
1272       /* If the main label of the block is unused, we may still remove it.  */
1273       if (!label_for_bb[bb->index].used)
1274         label_for_this_bb = NULL;
1275
1276       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1277         {
1278           tree label;
1279           gimple stmt = gsi_stmt (i);
1280
1281           if (gimple_code (stmt) != GIMPLE_LABEL)
1282             break;
1283
1284           label = gimple_label_label (stmt);
1285
1286           if (label == label_for_this_bb
1287               || !DECL_ARTIFICIAL (label)
1288               || DECL_NONLOCAL (label)
1289               || FORCED_LABEL (label))
1290             gsi_next (&i);
1291           else
1292             gsi_remove (&i, true);
1293         }
1294     }
1295
1296   free (label_for_bb);
1297 }
1298
1299 /* Scan the sorted vector of cases in STMT (a GIMPLE_SWITCH) and combine
1300    the ones jumping to the same label.
1301    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1302
1303 static void
1304 group_case_labels_stmt (gimple stmt)
1305 {
1306   int old_size = gimple_switch_num_labels (stmt);
1307   int i, j, new_size = old_size;
1308   tree default_case = NULL_TREE;
1309   tree default_label = NULL_TREE;
1310   bool has_default;
1311
1312   /* The default label is always the first case in a switch
1313      statement after gimplification if it was not optimized
1314      away */
1315   if (!CASE_LOW (gimple_switch_default_label (stmt))
1316       && !CASE_HIGH (gimple_switch_default_label (stmt)))
1317     {
1318       default_case = gimple_switch_default_label (stmt);
1319       default_label = CASE_LABEL (default_case);
1320       has_default = true;
1321     }
1322   else
1323     has_default = false;
1324
1325   /* Look for possible opportunities to merge cases.  */
1326   if (has_default)
1327     i = 1;
1328   else
1329     i = 0;
1330   while (i < old_size)
1331     {
1332       tree base_case, base_label, base_high;
1333       base_case = gimple_switch_label (stmt, i);
1334
1335       gcc_assert (base_case);
1336       base_label = CASE_LABEL (base_case);
1337
1338       /* Discard cases that have the same destination as the
1339          default case.  */
1340       if (base_label == default_label)
1341         {
1342           gimple_switch_set_label (stmt, i, NULL_TREE);
1343           i++;
1344           new_size--;
1345           continue;
1346         }
1347
1348       base_high = CASE_HIGH (base_case)
1349           ? CASE_HIGH (base_case)
1350           : CASE_LOW (base_case);
1351       i++;
1352
1353       /* Try to merge case labels.  Break out when we reach the end
1354          of the label vector or when we cannot merge the next case
1355          label with the current one.  */
1356       while (i < old_size)
1357         {
1358           tree merge_case = gimple_switch_label (stmt, i);
1359           tree merge_label = CASE_LABEL (merge_case);
1360           double_int bhp1 = double_int_add (tree_to_double_int (base_high),
1361                                             double_int_one);
1362
1363           /* Merge the cases if they jump to the same place,
1364              and their ranges are consecutive.  */
1365           if (merge_label == base_label
1366               && double_int_equal_p (tree_to_double_int (CASE_LOW (merge_case)),
1367                                      bhp1))
1368             {
1369               base_high = CASE_HIGH (merge_case) ?
1370                   CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1371               CASE_HIGH (base_case) = base_high;
1372               gimple_switch_set_label (stmt, i, NULL_TREE);
1373               new_size--;
1374               i++;
1375             }
1376           else
1377             break;
1378         }
1379     }
1380
1381   /* Compress the case labels in the label vector, and adjust the
1382      length of the vector.  */
1383   for (i = 0, j = 0; i < new_size; i++)
1384     {
1385       while (! gimple_switch_label (stmt, j))
1386         j++;
1387       gimple_switch_set_label (stmt, i,
1388                                gimple_switch_label (stmt, j++));
1389     }
1390
1391   gcc_assert (new_size <= old_size);
1392   gimple_switch_set_num_labels (stmt, new_size);
1393 }
1394
1395 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
1396    and scan the sorted vector of cases.  Combine the ones jumping to the
1397    same label.  */
1398
1399 void
1400 group_case_labels (void)
1401 {
1402   basic_block bb;
1403
1404   FOR_EACH_BB (bb)
1405     {
1406       gimple stmt = last_stmt (bb);
1407       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1408         group_case_labels_stmt (stmt);
1409     }
1410 }
1411
1412 /* Checks whether we can merge block B into block A.  */
1413
1414 static bool
1415 gimple_can_merge_blocks_p (basic_block a, basic_block b)
1416 {
1417   gimple stmt;
1418   gimple_stmt_iterator gsi;
1419   gimple_seq phis;
1420
1421   if (!single_succ_p (a))
1422     return false;
1423
1424   if (single_succ_edge (a)->flags & (EDGE_ABNORMAL | EDGE_EH | EDGE_PRESERVE))
1425     return false;
1426
1427   if (single_succ (a) != b)
1428     return false;
1429
1430   if (!single_pred_p (b))
1431     return false;
1432
1433   if (b == EXIT_BLOCK_PTR)
1434     return false;
1435
1436   /* If A ends by a statement causing exceptions or something similar, we
1437      cannot merge the blocks.  */
1438   stmt = last_stmt (a);
1439   if (stmt && stmt_ends_bb_p (stmt))
1440     return false;
1441
1442   /* Do not allow a block with only a non-local label to be merged.  */
1443   if (stmt
1444       && gimple_code (stmt) == GIMPLE_LABEL
1445       && DECL_NONLOCAL (gimple_label_label (stmt)))
1446     return false;
1447
1448   /* Examine the labels at the beginning of B.  */
1449   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
1450     {
1451       tree lab;
1452       stmt = gsi_stmt (gsi);
1453       if (gimple_code (stmt) != GIMPLE_LABEL)
1454         break;
1455       lab = gimple_label_label (stmt);
1456
1457       /* Do not remove user forced labels.  */
1458       if (!DECL_ARTIFICIAL (lab) && FORCED_LABEL (lab))
1459         return false;
1460     }
1461
1462   /* Protect the loop latches.  */
1463   if (current_loops && b->loop_father->latch == b)
1464     return false;
1465
1466   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1467      is not up-to-date and a name-mapping is registered, we cannot eliminate
1468      any phis.  Symbols marked for renaming are never a problem though.  */
1469   phis = phi_nodes (b);
1470   if (!gimple_seq_empty_p (phis)
1471       && name_mappings_registered_p ())
1472     return false;
1473
1474   /* When not optimizing, don't merge if we'd lose goto_locus.  */
1475   if (!optimize
1476       && single_succ_edge (a)->goto_locus != UNKNOWN_LOCATION)
1477     {
1478       location_t goto_locus = single_succ_edge (a)->goto_locus;
1479       gimple_stmt_iterator prev, next;
1480       prev = gsi_last_nondebug_bb (a);
1481       next = gsi_after_labels (b);
1482       if (!gsi_end_p (next) && is_gimple_debug (gsi_stmt (next)))
1483         gsi_next_nondebug (&next);
1484       if ((gsi_end_p (prev)
1485            || gimple_location (gsi_stmt (prev)) != goto_locus)
1486           && (gsi_end_p (next)
1487               || gimple_location (gsi_stmt (next)) != goto_locus))
1488         return false;
1489     }
1490
1491   return true;
1492 }
1493
1494 /* Return true if the var whose chain of uses starts at PTR has no
1495    nondebug uses.  */
1496 bool
1497 has_zero_uses_1 (const ssa_use_operand_t *head)
1498 {
1499   const ssa_use_operand_t *ptr;
1500
1501   for (ptr = head->next; ptr != head; ptr = ptr->next)
1502     if (!is_gimple_debug (USE_STMT (ptr)))
1503       return false;
1504
1505   return true;
1506 }
1507
1508 /* Return true if the var whose chain of uses starts at PTR has a
1509    single nondebug use.  Set USE_P and STMT to that single nondebug
1510    use, if so, or to NULL otherwise.  */
1511 bool
1512 single_imm_use_1 (const ssa_use_operand_t *head,
1513                   use_operand_p *use_p, gimple *stmt)
1514 {
1515   ssa_use_operand_t *ptr, *single_use = 0;
1516
1517   for (ptr = head->next; ptr != head; ptr = ptr->next)
1518     if (!is_gimple_debug (USE_STMT (ptr)))
1519       {
1520         if (single_use)
1521           {
1522             single_use = NULL;
1523             break;
1524           }
1525         single_use = ptr;
1526       }
1527
1528   if (use_p)
1529     *use_p = single_use;
1530
1531   if (stmt)
1532     *stmt = single_use ? single_use->loc.stmt : NULL;
1533
1534   return !!single_use;
1535 }
1536
1537 /* Replaces all uses of NAME by VAL.  */
1538
1539 void
1540 replace_uses_by (tree name, tree val)
1541 {
1542   imm_use_iterator imm_iter;
1543   use_operand_p use;
1544   gimple stmt;
1545   edge e;
1546
1547   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1548     {
1549       FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1550         {
1551           replace_exp (use, val);
1552
1553           if (gimple_code (stmt) == GIMPLE_PHI)
1554             {
1555               e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use));
1556               if (e->flags & EDGE_ABNORMAL)
1557                 {
1558                   /* This can only occur for virtual operands, since
1559                      for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1560                      would prevent replacement.  */
1561                   gcc_assert (!is_gimple_reg (name));
1562                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1563                 }
1564             }
1565         }
1566
1567       if (gimple_code (stmt) != GIMPLE_PHI)
1568         {
1569           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1570           size_t i;
1571
1572           fold_stmt (&gsi);
1573           stmt = gsi_stmt (gsi);
1574           if (cfgcleanup_altered_bbs && !is_gimple_debug (stmt))
1575             bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1576
1577           /* FIXME.  This should go in update_stmt.  */
1578           for (i = 0; i < gimple_num_ops (stmt); i++)
1579             {
1580               tree op = gimple_op (stmt, i);
1581               /* Operands may be empty here.  For example, the labels
1582                  of a GIMPLE_COND are nulled out following the creation
1583                  of the corresponding CFG edges.  */
1584               if (op && TREE_CODE (op) == ADDR_EXPR)
1585                 recompute_tree_invariant_for_addr_expr (op);
1586             }
1587
1588           maybe_clean_or_replace_eh_stmt (stmt, stmt);
1589           update_stmt (stmt);
1590         }
1591     }
1592
1593   gcc_assert (has_zero_uses (name));
1594
1595   /* Also update the trees stored in loop structures.  */
1596   if (current_loops)
1597     {
1598       struct loop *loop;
1599       loop_iterator li;
1600
1601       FOR_EACH_LOOP (li, loop, 0)
1602         {
1603           substitute_in_loop_info (loop, name, val);
1604         }
1605     }
1606 }
1607
1608 /* Merge block B into block A.  */
1609
1610 static void
1611 gimple_merge_blocks (basic_block a, basic_block b)
1612 {
1613   gimple_stmt_iterator last, gsi, psi;
1614   gimple_seq phis = phi_nodes (b);
1615
1616   if (dump_file)
1617     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1618
1619   /* Remove all single-valued PHI nodes from block B of the form
1620      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1621   gsi = gsi_last_bb (a);
1622   for (psi = gsi_start (phis); !gsi_end_p (psi); )
1623     {
1624       gimple phi = gsi_stmt (psi);
1625       tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1626       gimple copy;
1627       bool may_replace_uses = !is_gimple_reg (def)
1628                               || may_propagate_copy (def, use);
1629
1630       /* In case we maintain loop closed ssa form, do not propagate arguments
1631          of loop exit phi nodes.  */
1632       if (current_loops
1633           && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1634           && is_gimple_reg (def)
1635           && TREE_CODE (use) == SSA_NAME
1636           && a->loop_father != b->loop_father)
1637         may_replace_uses = false;
1638
1639       if (!may_replace_uses)
1640         {
1641           gcc_assert (is_gimple_reg (def));
1642
1643           /* Note that just emitting the copies is fine -- there is no problem
1644              with ordering of phi nodes.  This is because A is the single
1645              predecessor of B, therefore results of the phi nodes cannot
1646              appear as arguments of the phi nodes.  */
1647           copy = gimple_build_assign (def, use);
1648           gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1649           remove_phi_node (&psi, false);
1650         }
1651       else
1652         {
1653           /* If we deal with a PHI for virtual operands, we can simply
1654              propagate these without fussing with folding or updating
1655              the stmt.  */
1656           if (!is_gimple_reg (def))
1657             {
1658               imm_use_iterator iter;
1659               use_operand_p use_p;
1660               gimple stmt;
1661
1662               FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1663                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1664                   SET_USE (use_p, use);
1665
1666               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
1667                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use) = 1;
1668             }
1669           else
1670             replace_uses_by (def, use);
1671
1672           remove_phi_node (&psi, true);
1673         }
1674     }
1675
1676   /* Ensure that B follows A.  */
1677   move_block_after (b, a);
1678
1679   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1680   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1681
1682   /* Remove labels from B and set gimple_bb to A for other statements.  */
1683   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1684     {
1685       gimple stmt = gsi_stmt (gsi);
1686       if (gimple_code (stmt) == GIMPLE_LABEL)
1687         {
1688           tree label = gimple_label_label (stmt);
1689           int lp_nr;
1690
1691           gsi_remove (&gsi, false);
1692
1693           /* Now that we can thread computed gotos, we might have
1694              a situation where we have a forced label in block B
1695              However, the label at the start of block B might still be
1696              used in other ways (think about the runtime checking for
1697              Fortran assigned gotos).  So we can not just delete the
1698              label.  Instead we move the label to the start of block A.  */
1699           if (FORCED_LABEL (label))
1700             {
1701               gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1702               gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT);
1703             }
1704           /* Other user labels keep around in a form of a debug stmt.  */
1705           else if (!DECL_ARTIFICIAL (label) && MAY_HAVE_DEBUG_STMTS)
1706             {
1707               gimple dbg = gimple_build_debug_bind (label,
1708                                                     integer_zero_node,
1709                                                     stmt);
1710               gimple_debug_bind_reset_value (dbg);
1711               gsi_insert_before (&gsi, dbg, GSI_SAME_STMT);
1712             }
1713
1714           lp_nr = EH_LANDING_PAD_NR (label);
1715           if (lp_nr)
1716             {
1717               eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1718               lp->post_landing_pad = NULL;
1719             }
1720         }
1721       else
1722         {
1723           gimple_set_bb (stmt, a);
1724           gsi_next (&gsi);
1725         }
1726     }
1727
1728   /* Merge the sequences.  */
1729   last = gsi_last_bb (a);
1730   gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1731   set_bb_seq (b, NULL);
1732
1733   if (cfgcleanup_altered_bbs)
1734     bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1735 }
1736
1737
1738 /* Return the one of two successors of BB that is not reachable by a
1739    complex edge, if there is one.  Else, return BB.  We use
1740    this in optimizations that use post-dominators for their heuristics,
1741    to catch the cases in C++ where function calls are involved.  */
1742
1743 basic_block
1744 single_noncomplex_succ (basic_block bb)
1745 {
1746   edge e0, e1;
1747   if (EDGE_COUNT (bb->succs) != 2)
1748     return bb;
1749
1750   e0 = EDGE_SUCC (bb, 0);
1751   e1 = EDGE_SUCC (bb, 1);
1752   if (e0->flags & EDGE_COMPLEX)
1753     return e1->dest;
1754   if (e1->flags & EDGE_COMPLEX)
1755     return e0->dest;
1756
1757   return bb;
1758 }
1759
1760 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1761
1762 void
1763 notice_special_calls (gimple call)
1764 {
1765   int flags = gimple_call_flags (call);
1766
1767   if (flags & ECF_MAY_BE_ALLOCA)
1768     cfun->calls_alloca = true;
1769   if (flags & ECF_RETURNS_TWICE)
1770     cfun->calls_setjmp = true;
1771 }
1772
1773
1774 /* Clear flags set by notice_special_calls.  Used by dead code removal
1775    to update the flags.  */
1776
1777 void
1778 clear_special_calls (void)
1779 {
1780   cfun->calls_alloca = false;
1781   cfun->calls_setjmp = false;
1782 }
1783
1784 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1785
1786 static void
1787 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1788 {
1789   /* Since this block is no longer reachable, we can just delete all
1790      of its PHI nodes.  */
1791   remove_phi_nodes (bb);
1792
1793   /* Remove edges to BB's successors.  */
1794   while (EDGE_COUNT (bb->succs) > 0)
1795     remove_edge (EDGE_SUCC (bb, 0));
1796 }
1797
1798
1799 /* Remove statements of basic block BB.  */
1800
1801 static void
1802 remove_bb (basic_block bb)
1803 {
1804   gimple_stmt_iterator i;
1805
1806   if (dump_file)
1807     {
1808       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1809       if (dump_flags & TDF_DETAILS)
1810         {
1811           dump_bb (bb, dump_file, 0);
1812           fprintf (dump_file, "\n");
1813         }
1814     }
1815
1816   if (current_loops)
1817     {
1818       struct loop *loop = bb->loop_father;
1819
1820       /* If a loop gets removed, clean up the information associated
1821          with it.  */
1822       if (loop->latch == bb
1823           || loop->header == bb)
1824         free_numbers_of_iterations_estimates_loop (loop);
1825     }
1826
1827   /* Remove all the instructions in the block.  */
1828   if (bb_seq (bb) != NULL)
1829     {
1830       /* Walk backwards so as to get a chance to substitute all
1831          released DEFs into debug stmts.  See
1832          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
1833          details.  */
1834       for (i = gsi_last_bb (bb); !gsi_end_p (i);)
1835         {
1836           gimple stmt = gsi_stmt (i);
1837           if (gimple_code (stmt) == GIMPLE_LABEL
1838               && (FORCED_LABEL (gimple_label_label (stmt))
1839                   || DECL_NONLOCAL (gimple_label_label (stmt))))
1840             {
1841               basic_block new_bb;
1842               gimple_stmt_iterator new_gsi;
1843
1844               /* A non-reachable non-local label may still be referenced.
1845                  But it no longer needs to carry the extra semantics of
1846                  non-locality.  */
1847               if (DECL_NONLOCAL (gimple_label_label (stmt)))
1848                 {
1849                   DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
1850                   FORCED_LABEL (gimple_label_label (stmt)) = 1;
1851                 }
1852
1853               new_bb = bb->prev_bb;
1854               new_gsi = gsi_start_bb (new_bb);
1855               gsi_remove (&i, false);
1856               gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
1857             }
1858           else
1859             {
1860               /* Release SSA definitions if we are in SSA.  Note that we
1861                  may be called when not in SSA.  For example,
1862                  final_cleanup calls this function via
1863                  cleanup_tree_cfg.  */
1864               if (gimple_in_ssa_p (cfun))
1865                 release_defs (stmt);
1866
1867               gsi_remove (&i, true);
1868             }
1869
1870           if (gsi_end_p (i))
1871             i = gsi_last_bb (bb);
1872           else
1873             gsi_prev (&i);
1874         }
1875     }
1876
1877   remove_phi_nodes_and_edges_for_unreachable_block (bb);
1878   bb->il.gimple = NULL;
1879 }
1880
1881
1882 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
1883    predicate VAL, return the edge that will be taken out of the block.
1884    If VAL does not match a unique edge, NULL is returned.  */
1885
1886 edge
1887 find_taken_edge (basic_block bb, tree val)
1888 {
1889   gimple stmt;
1890
1891   stmt = last_stmt (bb);
1892
1893   gcc_assert (stmt);
1894   gcc_assert (is_ctrl_stmt (stmt));
1895
1896   if (val == NULL)
1897     return NULL;
1898
1899   if (!is_gimple_min_invariant (val))
1900     return NULL;
1901
1902   if (gimple_code (stmt) == GIMPLE_COND)
1903     return find_taken_edge_cond_expr (bb, val);
1904
1905   if (gimple_code (stmt) == GIMPLE_SWITCH)
1906     return find_taken_edge_switch_expr (bb, val);
1907
1908   if (computed_goto_p (stmt))
1909     {
1910       /* Only optimize if the argument is a label, if the argument is
1911          not a label then we can not construct a proper CFG.
1912
1913          It may be the case that we only need to allow the LABEL_REF to
1914          appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
1915          appear inside a LABEL_EXPR just to be safe.  */
1916       if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
1917           && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
1918         return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
1919       return NULL;
1920     }
1921
1922   gcc_unreachable ();
1923 }
1924
1925 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
1926    statement, determine which of the outgoing edges will be taken out of the
1927    block.  Return NULL if either edge may be taken.  */
1928
1929 static edge
1930 find_taken_edge_computed_goto (basic_block bb, tree val)
1931 {
1932   basic_block dest;
1933   edge e = NULL;
1934
1935   dest = label_to_block (val);
1936   if (dest)
1937     {
1938       e = find_edge (bb, dest);
1939       gcc_assert (e != NULL);
1940     }
1941
1942   return e;
1943 }
1944
1945 /* Given a constant value VAL and the entry block BB to a COND_EXPR
1946    statement, determine which of the two edges will be taken out of the
1947    block.  Return NULL if either edge may be taken.  */
1948
1949 static edge
1950 find_taken_edge_cond_expr (basic_block bb, tree val)
1951 {
1952   edge true_edge, false_edge;
1953
1954   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1955
1956   gcc_assert (TREE_CODE (val) == INTEGER_CST);
1957   return (integer_zerop (val) ? false_edge : true_edge);
1958 }
1959
1960 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
1961    statement, determine which edge will be taken out of the block.  Return
1962    NULL if any edge may be taken.  */
1963
1964 static edge
1965 find_taken_edge_switch_expr (basic_block bb, tree val)
1966 {
1967   basic_block dest_bb;
1968   edge e;
1969   gimple switch_stmt;
1970   tree taken_case;
1971
1972   switch_stmt = last_stmt (bb);
1973   taken_case = find_case_label_for_value (switch_stmt, val);
1974   dest_bb = label_to_block (CASE_LABEL (taken_case));
1975
1976   e = find_edge (bb, dest_bb);
1977   gcc_assert (e);
1978   return e;
1979 }
1980
1981
1982 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
1983    We can make optimal use here of the fact that the case labels are
1984    sorted: We can do a binary search for a case matching VAL.  */
1985
1986 static tree
1987 find_case_label_for_value (gimple switch_stmt, tree val)
1988 {
1989   size_t low, high, n = gimple_switch_num_labels (switch_stmt);
1990   tree default_case = gimple_switch_default_label (switch_stmt);
1991
1992   for (low = 0, high = n; high - low > 1; )
1993     {
1994       size_t i = (high + low) / 2;
1995       tree t = gimple_switch_label (switch_stmt, i);
1996       int cmp;
1997
1998       /* Cache the result of comparing CASE_LOW and val.  */
1999       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2000
2001       if (cmp > 0)
2002         high = i;
2003       else
2004         low = i;
2005
2006       if (CASE_HIGH (t) == NULL)
2007         {
2008           /* A singe-valued case label.  */
2009           if (cmp == 0)
2010             return t;
2011         }
2012       else
2013         {
2014           /* A case range.  We can only handle integer ranges.  */
2015           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2016             return t;
2017         }
2018     }
2019
2020   return default_case;
2021 }
2022
2023
2024 /* Dump a basic block on stderr.  */
2025
2026 void
2027 gimple_debug_bb (basic_block bb)
2028 {
2029   gimple_dump_bb (bb, stderr, 0, TDF_VOPS|TDF_MEMSYMS);
2030 }
2031
2032
2033 /* Dump basic block with index N on stderr.  */
2034
2035 basic_block
2036 gimple_debug_bb_n (int n)
2037 {
2038   gimple_debug_bb (BASIC_BLOCK (n));
2039   return BASIC_BLOCK (n);
2040 }
2041
2042
2043 /* Dump the CFG on stderr.
2044
2045    FLAGS are the same used by the tree dumping functions
2046    (see TDF_* in tree-pass.h).  */
2047
2048 void
2049 gimple_debug_cfg (int flags)
2050 {
2051   gimple_dump_cfg (stderr, flags);
2052 }
2053
2054
2055 /* Dump the program showing basic block boundaries on the given FILE.
2056
2057    FLAGS are the same used by the tree dumping functions (see TDF_* in
2058    tree.h).  */
2059
2060 void
2061 gimple_dump_cfg (FILE *file, int flags)
2062 {
2063   if (flags & TDF_DETAILS)
2064     {
2065       dump_function_header (file, current_function_decl, flags);
2066       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2067                n_basic_blocks, n_edges, last_basic_block);
2068
2069       brief_dump_cfg (file);
2070       fprintf (file, "\n");
2071     }
2072
2073   if (flags & TDF_STATS)
2074     dump_cfg_stats (file);
2075
2076   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2077 }
2078
2079
2080 /* Dump CFG statistics on FILE.  */
2081
2082 void
2083 dump_cfg_stats (FILE *file)
2084 {
2085   static long max_num_merged_labels = 0;
2086   unsigned long size, total = 0;
2087   long num_edges;
2088   basic_block bb;
2089   const char * const fmt_str   = "%-30s%-13s%12s\n";
2090   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2091   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2092   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2093   const char *funcname
2094     = lang_hooks.decl_printable_name (current_function_decl, 2);
2095
2096
2097   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2098
2099   fprintf (file, "---------------------------------------------------------\n");
2100   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2101   fprintf (file, fmt_str, "", "  instances  ", "used ");
2102   fprintf (file, "---------------------------------------------------------\n");
2103
2104   size = n_basic_blocks * sizeof (struct basic_block_def);
2105   total += size;
2106   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2107            SCALE (size), LABEL (size));
2108
2109   num_edges = 0;
2110   FOR_EACH_BB (bb)
2111     num_edges += EDGE_COUNT (bb->succs);
2112   size = num_edges * sizeof (struct edge_def);
2113   total += size;
2114   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2115
2116   fprintf (file, "---------------------------------------------------------\n");
2117   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2118            LABEL (total));
2119   fprintf (file, "---------------------------------------------------------\n");
2120   fprintf (file, "\n");
2121
2122   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2123     max_num_merged_labels = cfg_stats.num_merged_labels;
2124
2125   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2126            cfg_stats.num_merged_labels, max_num_merged_labels);
2127
2128   fprintf (file, "\n");
2129 }
2130
2131
2132 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2133    linked in the final executable.  */
2134
2135 DEBUG_FUNCTION void
2136 debug_cfg_stats (void)
2137 {
2138   dump_cfg_stats (stderr);
2139 }
2140
2141
2142 /* Dump the flowgraph to a .vcg FILE.  */
2143
2144 static void
2145 gimple_cfg2vcg (FILE *file)
2146 {
2147   edge e;
2148   edge_iterator ei;
2149   basic_block bb;
2150   const char *funcname
2151     = lang_hooks.decl_printable_name (current_function_decl, 2);
2152
2153   /* Write the file header.  */
2154   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2155   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2156   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2157
2158   /* Write blocks and edges.  */
2159   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2160     {
2161       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2162                e->dest->index);
2163
2164       if (e->flags & EDGE_FAKE)
2165         fprintf (file, " linestyle: dotted priority: 10");
2166       else
2167         fprintf (file, " linestyle: solid priority: 100");
2168
2169       fprintf (file, " }\n");
2170     }
2171   fputc ('\n', file);
2172
2173   FOR_EACH_BB (bb)
2174     {
2175       enum gimple_code head_code, end_code;
2176       const char *head_name, *end_name;
2177       int head_line = 0;
2178       int end_line = 0;
2179       gimple first = first_stmt (bb);
2180       gimple last = last_stmt (bb);
2181
2182       if (first)
2183         {
2184           head_code = gimple_code (first);
2185           head_name = gimple_code_name[head_code];
2186           head_line = get_lineno (first);
2187         }
2188       else
2189         head_name = "no-statement";
2190
2191       if (last)
2192         {
2193           end_code = gimple_code (last);
2194           end_name = gimple_code_name[end_code];
2195           end_line = get_lineno (last);
2196         }
2197       else
2198         end_name = "no-statement";
2199
2200       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2201                bb->index, bb->index, head_name, head_line, end_name,
2202                end_line);
2203
2204       FOR_EACH_EDGE (e, ei, bb->succs)
2205         {
2206           if (e->dest == EXIT_BLOCK_PTR)
2207             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2208           else
2209             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2210
2211           if (e->flags & EDGE_FAKE)
2212             fprintf (file, " priority: 10 linestyle: dotted");
2213           else
2214             fprintf (file, " priority: 100 linestyle: solid");
2215
2216           fprintf (file, " }\n");
2217         }
2218
2219       if (bb->next_bb != EXIT_BLOCK_PTR)
2220         fputc ('\n', file);
2221     }
2222
2223   fputs ("}\n\n", file);
2224 }
2225
2226
2227
2228 /*---------------------------------------------------------------------------
2229                              Miscellaneous helpers
2230 ---------------------------------------------------------------------------*/
2231
2232 /* Return true if T represents a stmt that always transfers control.  */
2233
2234 bool
2235 is_ctrl_stmt (gimple t)
2236 {
2237   switch (gimple_code (t))
2238     {
2239     case GIMPLE_COND:
2240     case GIMPLE_SWITCH:
2241     case GIMPLE_GOTO:
2242     case GIMPLE_RETURN:
2243     case GIMPLE_RESX:
2244       return true;
2245     default:
2246       return false;
2247     }
2248 }
2249
2250
2251 /* Return true if T is a statement that may alter the flow of control
2252    (e.g., a call to a non-returning function).  */
2253
2254 bool
2255 is_ctrl_altering_stmt (gimple t)
2256 {
2257   gcc_assert (t);
2258
2259   switch (gimple_code (t))
2260     {
2261     case GIMPLE_CALL:
2262       {
2263         int flags = gimple_call_flags (t);
2264
2265         /* A non-pure/const call alters flow control if the current
2266            function has nonlocal labels.  */
2267         if (!(flags & (ECF_CONST | ECF_PURE | ECF_LEAF))
2268             && cfun->has_nonlocal_label)
2269           return true;
2270
2271         /* A call also alters control flow if it does not return.  */
2272         if (flags & ECF_NORETURN)
2273           return true;
2274
2275         /* BUILT_IN_RETURN call is same as return statement.  */
2276         if (gimple_call_builtin_p (t, BUILT_IN_RETURN))
2277           return true;
2278       }
2279       break;
2280
2281     case GIMPLE_EH_DISPATCH:
2282       /* EH_DISPATCH branches to the individual catch handlers at
2283          this level of a try or allowed-exceptions region.  It can
2284          fallthru to the next statement as well.  */
2285       return true;
2286
2287     case GIMPLE_ASM:
2288       if (gimple_asm_nlabels (t) > 0)
2289         return true;
2290       break;
2291
2292     CASE_GIMPLE_OMP:
2293       /* OpenMP directives alter control flow.  */
2294       return true;
2295
2296     default:
2297       break;
2298     }
2299
2300   /* If a statement can throw, it alters control flow.  */
2301   return stmt_can_throw_internal (t);
2302 }
2303
2304
2305 /* Return true if T is a simple local goto.  */
2306
2307 bool
2308 simple_goto_p (gimple t)
2309 {
2310   return (gimple_code (t) == GIMPLE_GOTO
2311           && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2312 }
2313
2314
2315 /* Return true if T can make an abnormal transfer of control flow.
2316    Transfers of control flow associated with EH are excluded.  */
2317
2318 bool
2319 stmt_can_make_abnormal_goto (gimple t)
2320 {
2321   if (computed_goto_p (t))
2322     return true;
2323   if (is_gimple_call (t))
2324     return (gimple_has_side_effects (t) && cfun->has_nonlocal_label
2325             && !(gimple_call_flags (t) & ECF_LEAF));
2326   return false;
2327 }
2328
2329
2330 /* Return true if STMT should start a new basic block.  PREV_STMT is
2331    the statement preceding STMT.  It is used when STMT is a label or a
2332    case label.  Labels should only start a new basic block if their
2333    previous statement wasn't a label.  Otherwise, sequence of labels
2334    would generate unnecessary basic blocks that only contain a single
2335    label.  */
2336
2337 static inline bool
2338 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2339 {
2340   if (stmt == NULL)
2341     return false;
2342
2343   /* Labels start a new basic block only if the preceding statement
2344      wasn't a label of the same type.  This prevents the creation of
2345      consecutive blocks that have nothing but a single label.  */
2346   if (gimple_code (stmt) == GIMPLE_LABEL)
2347     {
2348       /* Nonlocal and computed GOTO targets always start a new block.  */
2349       if (DECL_NONLOCAL (gimple_label_label (stmt))
2350           || FORCED_LABEL (gimple_label_label (stmt)))
2351         return true;
2352
2353       if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2354         {
2355           if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2356             return true;
2357
2358           cfg_stats.num_merged_labels++;
2359           return false;
2360         }
2361       else
2362         return true;
2363     }
2364
2365   return false;
2366 }
2367
2368
2369 /* Return true if T should end a basic block.  */
2370
2371 bool
2372 stmt_ends_bb_p (gimple t)
2373 {
2374   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2375 }
2376
2377 /* Remove block annotations and other data structures.  */
2378
2379 void
2380 delete_tree_cfg_annotations (void)
2381 {
2382   label_to_block_map = NULL;
2383 }
2384
2385
2386 /* Return the first statement in basic block BB.  */
2387
2388 gimple
2389 first_stmt (basic_block bb)
2390 {
2391   gimple_stmt_iterator i = gsi_start_bb (bb);
2392   gimple stmt = NULL;
2393
2394   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2395     {
2396       gsi_next (&i);
2397       stmt = NULL;
2398     }
2399   return stmt;
2400 }
2401
2402 /* Return the first non-label statement in basic block BB.  */
2403
2404 static gimple
2405 first_non_label_stmt (basic_block bb)
2406 {
2407   gimple_stmt_iterator i = gsi_start_bb (bb);
2408   while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2409     gsi_next (&i);
2410   return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2411 }
2412
2413 /* Return the last statement in basic block BB.  */
2414
2415 gimple
2416 last_stmt (basic_block bb)
2417 {
2418   gimple_stmt_iterator i = gsi_last_bb (bb);
2419   gimple stmt = NULL;
2420
2421   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2422     {
2423       gsi_prev (&i);
2424       stmt = NULL;
2425     }
2426   return stmt;
2427 }
2428
2429 /* Return the last statement of an otherwise empty block.  Return NULL
2430    if the block is totally empty, or if it contains more than one
2431    statement.  */
2432
2433 gimple
2434 last_and_only_stmt (basic_block bb)
2435 {
2436   gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
2437   gimple last, prev;
2438
2439   if (gsi_end_p (i))
2440     return NULL;
2441
2442   last = gsi_stmt (i);
2443   gsi_prev_nondebug (&i);
2444   if (gsi_end_p (i))
2445     return last;
2446
2447   /* Empty statements should no longer appear in the instruction stream.
2448      Everything that might have appeared before should be deleted by
2449      remove_useless_stmts, and the optimizers should just gsi_remove
2450      instead of smashing with build_empty_stmt.
2451
2452      Thus the only thing that should appear here in a block containing
2453      one executable statement is a label.  */
2454   prev = gsi_stmt (i);
2455   if (gimple_code (prev) == GIMPLE_LABEL)
2456     return last;
2457   else
2458     return NULL;
2459 }
2460
2461 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
2462
2463 static void
2464 reinstall_phi_args (edge new_edge, edge old_edge)
2465 {
2466   edge_var_map_vector v;
2467   edge_var_map *vm;
2468   int i;
2469   gimple_stmt_iterator phis;
2470
2471   v = redirect_edge_var_map_vector (old_edge);
2472   if (!v)
2473     return;
2474
2475   for (i = 0, phis = gsi_start_phis (new_edge->dest);
2476        VEC_iterate (edge_var_map, v, i, vm) && !gsi_end_p (phis);
2477        i++, gsi_next (&phis))
2478     {
2479       gimple phi = gsi_stmt (phis);
2480       tree result = redirect_edge_var_map_result (vm);
2481       tree arg = redirect_edge_var_map_def (vm);
2482
2483       gcc_assert (result == gimple_phi_result (phi));
2484
2485       add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
2486     }
2487
2488   redirect_edge_var_map_clear (old_edge);
2489 }
2490
2491 /* Returns the basic block after which the new basic block created
2492    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
2493    near its "logical" location.  This is of most help to humans looking
2494    at debugging dumps.  */
2495
2496 static basic_block
2497 split_edge_bb_loc (edge edge_in)
2498 {
2499   basic_block dest = edge_in->dest;
2500   basic_block dest_prev = dest->prev_bb;
2501
2502   if (dest_prev)
2503     {
2504       edge e = find_edge (dest_prev, dest);
2505       if (e && !(e->flags & EDGE_COMPLEX))
2506         return edge_in->src;
2507     }
2508   return dest_prev;
2509 }
2510
2511 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
2512    Abort on abnormal edges.  */
2513
2514 static basic_block
2515 gimple_split_edge (edge edge_in)
2516 {
2517   basic_block new_bb, after_bb, dest;
2518   edge new_edge, e;
2519
2520   /* Abnormal edges cannot be split.  */
2521   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2522
2523   dest = edge_in->dest;
2524
2525   after_bb = split_edge_bb_loc (edge_in);
2526
2527   new_bb = create_empty_bb (after_bb);
2528   new_bb->frequency = EDGE_FREQUENCY (edge_in);
2529   new_bb->count = edge_in->count;
2530   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2531   new_edge->probability = REG_BR_PROB_BASE;
2532   new_edge->count = edge_in->count;
2533
2534   e = redirect_edge_and_branch (edge_in, new_bb);
2535   gcc_assert (e == edge_in);
2536   reinstall_phi_args (new_edge, e);
2537
2538   return new_bb;
2539 }
2540
2541
2542 /* Verify properties of the address expression T with base object BASE.  */
2543
2544 static tree
2545 verify_address (tree t, tree base)
2546 {
2547   bool old_constant;
2548   bool old_side_effects;
2549   bool new_constant;
2550   bool new_side_effects;
2551
2552   old_constant = TREE_CONSTANT (t);
2553   old_side_effects = TREE_SIDE_EFFECTS (t);
2554
2555   recompute_tree_invariant_for_addr_expr (t);
2556   new_side_effects = TREE_SIDE_EFFECTS (t);
2557   new_constant = TREE_CONSTANT (t);
2558
2559   if (old_constant != new_constant)
2560     {
2561       error ("constant not recomputed when ADDR_EXPR changed");
2562       return t;
2563     }
2564   if (old_side_effects != new_side_effects)
2565     {
2566       error ("side effects not recomputed when ADDR_EXPR changed");
2567       return t;
2568     }
2569
2570   if (!(TREE_CODE (base) == VAR_DECL
2571         || TREE_CODE (base) == PARM_DECL
2572         || TREE_CODE (base) == RESULT_DECL))
2573     return NULL_TREE;
2574
2575   if (DECL_GIMPLE_REG_P (base))
2576     {
2577       error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2578       return base;
2579     }
2580
2581   return NULL_TREE;
2582 }
2583
2584 /* Callback for walk_tree, check that all elements with address taken are
2585    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
2586    inside a PHI node.  */
2587
2588 static tree
2589 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2590 {
2591   tree t = *tp, x;
2592
2593   if (TYPE_P (t))
2594     *walk_subtrees = 0;
2595
2596   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
2597 #define CHECK_OP(N, MSG) \
2598   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
2599        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2600
2601   switch (TREE_CODE (t))
2602     {
2603     case SSA_NAME:
2604       if (SSA_NAME_IN_FREE_LIST (t))
2605         {
2606           error ("SSA name in freelist but still referenced");
2607           return *tp;
2608         }
2609       break;
2610
2611     case INDIRECT_REF:
2612       error ("INDIRECT_REF in gimple IL");
2613       return t;
2614
2615     case MEM_REF:
2616       x = TREE_OPERAND (t, 0);
2617       if (!POINTER_TYPE_P (TREE_TYPE (x))
2618           || !is_gimple_mem_ref_addr (x))
2619         {
2620           error ("invalid first operand of MEM_REF");
2621           return x;
2622         }
2623       if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST
2624           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1))))
2625         {
2626           error ("invalid offset operand of MEM_REF");
2627           return TREE_OPERAND (t, 1);
2628         }
2629       if (TREE_CODE (x) == ADDR_EXPR
2630           && (x = verify_address (x, TREE_OPERAND (x, 0))))
2631         return x;
2632       *walk_subtrees = 0;
2633       break;
2634
2635     case ASSERT_EXPR:
2636       x = fold (ASSERT_EXPR_COND (t));
2637       if (x == boolean_false_node)
2638         {
2639           error ("ASSERT_EXPR with an always-false condition");
2640           return *tp;
2641         }
2642       break;
2643
2644     case MODIFY_EXPR:
2645       error ("MODIFY_EXPR not expected while having tuples");
2646       return *tp;
2647
2648     case ADDR_EXPR:
2649       {
2650         tree tem;
2651
2652         gcc_assert (is_gimple_address (t));
2653
2654         /* Skip any references (they will be checked when we recurse down the
2655            tree) and ensure that any variable used as a prefix is marked
2656            addressable.  */
2657         for (x = TREE_OPERAND (t, 0);
2658              handled_component_p (x);
2659              x = TREE_OPERAND (x, 0))
2660           ;
2661
2662         if ((tem = verify_address (t, x)))
2663           return tem;
2664
2665         if (!(TREE_CODE (x) == VAR_DECL
2666               || TREE_CODE (x) == PARM_DECL
2667               || TREE_CODE (x) == RESULT_DECL))
2668           return NULL;
2669
2670         if (!TREE_ADDRESSABLE (x))
2671           {
2672             error ("address taken, but ADDRESSABLE bit not set");
2673             return x;
2674           }
2675
2676         break;
2677       }
2678
2679     case COND_EXPR:
2680       x = COND_EXPR_COND (t);
2681       if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2682         {
2683           error ("non-integral used in condition");
2684           return x;
2685         }
2686       if (!is_gimple_condexpr (x))
2687         {
2688           error ("invalid conditional operand");
2689           return x;
2690         }
2691       break;
2692
2693     case NON_LVALUE_EXPR:
2694     case TRUTH_NOT_EXPR:
2695       gcc_unreachable ();
2696
2697     CASE_CONVERT:
2698     case FIX_TRUNC_EXPR:
2699     case FLOAT_EXPR:
2700     case NEGATE_EXPR:
2701     case ABS_EXPR:
2702     case BIT_NOT_EXPR:
2703       CHECK_OP (0, "invalid operand to unary operator");
2704       break;
2705
2706     case REALPART_EXPR:
2707     case IMAGPART_EXPR:
2708     case COMPONENT_REF:
2709     case ARRAY_REF:
2710     case ARRAY_RANGE_REF:
2711     case BIT_FIELD_REF:
2712     case VIEW_CONVERT_EXPR:
2713       /* We have a nest of references.  Verify that each of the operands
2714          that determine where to reference is either a constant or a variable,
2715          verify that the base is valid, and then show we've already checked
2716          the subtrees.  */
2717       while (handled_component_p (t))
2718         {
2719           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2720             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2721           else if (TREE_CODE (t) == ARRAY_REF
2722                    || TREE_CODE (t) == ARRAY_RANGE_REF)
2723             {
2724               CHECK_OP (1, "invalid array index");
2725               if (TREE_OPERAND (t, 2))
2726                 CHECK_OP (2, "invalid array lower bound");
2727               if (TREE_OPERAND (t, 3))
2728                 CHECK_OP (3, "invalid array stride");
2729             }
2730           else if (TREE_CODE (t) == BIT_FIELD_REF)
2731             {
2732               if (!host_integerp (TREE_OPERAND (t, 1), 1)
2733                   || !host_integerp (TREE_OPERAND (t, 2), 1))
2734                 {
2735                   error ("invalid position or size operand to BIT_FIELD_REF");
2736                   return t;
2737                 }
2738               else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2739                        && (TYPE_PRECISION (TREE_TYPE (t))
2740                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2741                 {
2742                   error ("integral result type precision does not match "
2743                          "field size of BIT_FIELD_REF");
2744                   return t;
2745                 }
2746               if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2747                   && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2748                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2749                 {
2750                   error ("mode precision of non-integral result does not "
2751                          "match field size of BIT_FIELD_REF");
2752                   return t;
2753                 }
2754             }
2755
2756           t = TREE_OPERAND (t, 0);
2757         }
2758
2759       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2760         {
2761           error ("invalid reference prefix");
2762           return t;
2763         }
2764       *walk_subtrees = 0;
2765       break;
2766     case PLUS_EXPR:
2767     case MINUS_EXPR:
2768       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2769          POINTER_PLUS_EXPR. */
2770       if (POINTER_TYPE_P (TREE_TYPE (t)))
2771         {
2772           error ("invalid operand to plus/minus, type is a pointer");
2773           return t;
2774         }
2775       CHECK_OP (0, "invalid operand to binary operator");
2776       CHECK_OP (1, "invalid operand to binary operator");
2777       break;
2778
2779     case POINTER_PLUS_EXPR:
2780       /* Check to make sure the first operand is a pointer or reference type. */
2781       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
2782         {
2783           error ("invalid operand to pointer plus, first operand is not a pointer");
2784           return t;
2785         }
2786       /* Check to make sure the second operand is a ptrofftype.  */
2787       if (!ptrofftype_p (TREE_TYPE (TREE_OPERAND (t, 1))))
2788         {
2789           error ("invalid operand to pointer plus, second operand is not an "
2790                  "integer type of appropriate width");
2791           return t;
2792         }
2793       /* FALLTHROUGH */
2794     case LT_EXPR:
2795     case LE_EXPR:
2796     case GT_EXPR:
2797     case GE_EXPR:
2798     case EQ_EXPR:
2799     case NE_EXPR:
2800     case UNORDERED_EXPR:
2801     case ORDERED_EXPR:
2802     case UNLT_EXPR:
2803     case UNLE_EXPR:
2804     case UNGT_EXPR:
2805     case UNGE_EXPR:
2806     case UNEQ_EXPR:
2807     case LTGT_EXPR:
2808     case MULT_EXPR:
2809     case TRUNC_DIV_EXPR:
2810     case CEIL_DIV_EXPR:
2811     case FLOOR_DIV_EXPR:
2812     case ROUND_DIV_EXPR:
2813     case TRUNC_MOD_EXPR:
2814     case CEIL_MOD_EXPR:
2815     case FLOOR_MOD_EXPR:
2816     case ROUND_MOD_EXPR:
2817     case RDIV_EXPR:
2818     case EXACT_DIV_EXPR:
2819     case MIN_EXPR:
2820     case MAX_EXPR:
2821     case LSHIFT_EXPR:
2822     case RSHIFT_EXPR:
2823     case LROTATE_EXPR:
2824     case RROTATE_EXPR:
2825     case BIT_IOR_EXPR:
2826     case BIT_XOR_EXPR:
2827     case BIT_AND_EXPR:
2828       CHECK_OP (0, "invalid operand to binary operator");
2829       CHECK_OP (1, "invalid operand to binary operator");
2830       break;
2831
2832     case CONSTRUCTOR:
2833       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2834         *walk_subtrees = 0;
2835       break;
2836
2837     case CASE_LABEL_EXPR:
2838       if (CASE_CHAIN (t))
2839         {
2840           error ("invalid CASE_CHAIN");
2841           return t;
2842         }
2843       break;
2844
2845     default:
2846       break;
2847     }
2848   return NULL;
2849
2850 #undef CHECK_OP
2851 }
2852
2853
2854 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
2855    Returns true if there is an error, otherwise false.  */
2856
2857 static bool
2858 verify_types_in_gimple_min_lval (tree expr)
2859 {
2860   tree op;
2861
2862   if (is_gimple_id (expr))
2863     return false;
2864
2865   if (TREE_CODE (expr) != TARGET_MEM_REF
2866       && TREE_CODE (expr) != MEM_REF)
2867     {
2868       error ("invalid expression for min lvalue");
2869       return true;
2870     }
2871
2872   /* TARGET_MEM_REFs are strange beasts.  */
2873   if (TREE_CODE (expr) == TARGET_MEM_REF)
2874     return false;
2875
2876   op = TREE_OPERAND (expr, 0);
2877   if (!is_gimple_val (op))
2878     {
2879       error ("invalid operand in indirect reference");
2880       debug_generic_stmt (op);
2881       return true;
2882     }
2883   /* Memory references now generally can involve a value conversion.  */
2884
2885   return false;
2886 }
2887
2888 /* Verify if EXPR is a valid GIMPLE reference expression.  If
2889    REQUIRE_LVALUE is true verifies it is an lvalue.  Returns true
2890    if there is an error, otherwise false.  */
2891
2892 static bool
2893 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
2894 {
2895   while (handled_component_p (expr))
2896     {
2897       tree op = TREE_OPERAND (expr, 0);
2898
2899       if (TREE_CODE (expr) == ARRAY_REF
2900           || TREE_CODE (expr) == ARRAY_RANGE_REF)
2901         {
2902           if (!is_gimple_val (TREE_OPERAND (expr, 1))
2903               || (TREE_OPERAND (expr, 2)
2904                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
2905               || (TREE_OPERAND (expr, 3)
2906                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
2907             {
2908               error ("invalid operands to array reference");
2909               debug_generic_stmt (expr);
2910               return true;
2911             }
2912         }
2913
2914       /* Verify if the reference array element types are compatible.  */
2915       if (TREE_CODE (expr) == ARRAY_REF
2916           && !useless_type_conversion_p (TREE_TYPE (expr),
2917                                          TREE_TYPE (TREE_TYPE (op))))
2918         {
2919           error ("type mismatch in array reference");
2920           debug_generic_stmt (TREE_TYPE (expr));
2921           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2922           return true;
2923         }
2924       if (TREE_CODE (expr) == ARRAY_RANGE_REF
2925           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
2926                                          TREE_TYPE (TREE_TYPE (op))))
2927         {
2928           error ("type mismatch in array range reference");
2929           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
2930           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2931           return true;
2932         }
2933
2934       if ((TREE_CODE (expr) == REALPART_EXPR
2935            || TREE_CODE (expr) == IMAGPART_EXPR)
2936           && !useless_type_conversion_p (TREE_TYPE (expr),
2937                                          TREE_TYPE (TREE_TYPE (op))))
2938         {
2939           error ("type mismatch in real/imagpart reference");
2940           debug_generic_stmt (TREE_TYPE (expr));
2941           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2942           return true;
2943         }
2944
2945       if (TREE_CODE (expr) == COMPONENT_REF
2946           && !useless_type_conversion_p (TREE_TYPE (expr),
2947                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
2948         {
2949           error ("type mismatch in component reference");
2950           debug_generic_stmt (TREE_TYPE (expr));
2951           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
2952           return true;
2953         }
2954
2955       if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2956         {
2957           /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check
2958              that their operand is not an SSA name or an invariant when
2959              requiring an lvalue (this usually means there is a SRA or IPA-SRA
2960              bug).  Otherwise there is nothing to verify, gross mismatches at
2961              most invoke undefined behavior.  */
2962           if (require_lvalue
2963               && (TREE_CODE (op) == SSA_NAME
2964                   || is_gimple_min_invariant (op)))
2965             {
2966               error ("conversion of an SSA_NAME on the left hand side");
2967               debug_generic_stmt (expr);
2968               return true;
2969             }
2970           else if (TREE_CODE (op) == SSA_NAME
2971                    && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op)))
2972             {
2973               error ("conversion of register to a different size");
2974               debug_generic_stmt (expr);
2975               return true;
2976             }
2977           else if (!handled_component_p (op))
2978             return false;
2979         }
2980
2981       expr = op;
2982     }
2983
2984   if (TREE_CODE (expr) == MEM_REF)
2985     {
2986       if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0)))
2987         {
2988           error ("invalid address operand in MEM_REF");
2989           debug_generic_stmt (expr);
2990           return true;
2991         }
2992       if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST
2993           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
2994         {
2995           error ("invalid offset operand in MEM_REF");
2996           debug_generic_stmt (expr);
2997           return true;
2998         }
2999     }
3000   else if (TREE_CODE (expr) == TARGET_MEM_REF)
3001     {
3002       if (!TMR_BASE (expr)
3003           || !is_gimple_mem_ref_addr (TMR_BASE (expr)))
3004         {
3005           error ("invalid address operand in TARGET_MEM_REF");
3006           return true;
3007         }
3008       if (!TMR_OFFSET (expr)
3009           || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST
3010           || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr))))
3011         {
3012           error ("invalid offset operand in TARGET_MEM_REF");
3013           debug_generic_stmt (expr);
3014           return true;
3015         }
3016     }
3017
3018   return ((require_lvalue || !is_gimple_min_invariant (expr))
3019           && verify_types_in_gimple_min_lval (expr));
3020 }
3021
3022 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3023    list of pointer-to types that is trivially convertible to DEST.  */
3024
3025 static bool
3026 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3027 {
3028   tree src;
3029
3030   if (!TYPE_POINTER_TO (src_obj))
3031     return true;
3032
3033   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3034     if (useless_type_conversion_p (dest, src))
3035       return true;
3036
3037   return false;
3038 }
3039
3040 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3041    from TYPE2 can be handled by FIXED_CONVERT_EXPR.  */
3042
3043 static bool
3044 valid_fixed_convert_types_p (tree type1, tree type2)
3045 {
3046   return (FIXED_POINT_TYPE_P (type1)
3047           && (INTEGRAL_TYPE_P (type2)
3048               || SCALAR_FLOAT_TYPE_P (type2)
3049               || FIXED_POINT_TYPE_P (type2)));
3050 }
3051
3052 /* Verify the contents of a GIMPLE_CALL STMT.  Returns true when there
3053    is a problem, otherwise false.  */
3054
3055 static bool
3056 verify_gimple_call (gimple stmt)
3057 {
3058   tree fn = gimple_call_fn (stmt);
3059   tree fntype, fndecl;
3060   unsigned i;
3061
3062   if (gimple_call_internal_p (stmt))
3063     {
3064       if (fn)
3065         {
3066           error ("gimple call has two targets");
3067           debug_generic_stmt (fn);
3068           return true;
3069         }
3070     }
3071   else
3072     {
3073       if (!fn)
3074         {
3075           error ("gimple call has no target");
3076           return true;
3077         }
3078     }
3079
3080   if (fn && !is_gimple_call_addr (fn))
3081     {
3082       error ("invalid function in gimple call");
3083       debug_generic_stmt (fn);
3084       return true;
3085     }
3086
3087   if (fn
3088       && (!POINTER_TYPE_P (TREE_TYPE (fn))
3089           || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3090               && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE)))
3091     {
3092       error ("non-function in gimple call");
3093       return true;
3094     }
3095
3096    fndecl = gimple_call_fndecl (stmt);
3097    if (fndecl
3098        && TREE_CODE (fndecl) == FUNCTION_DECL
3099        && DECL_LOOPING_CONST_OR_PURE_P (fndecl)
3100        && !DECL_PURE_P (fndecl)
3101        && !TREE_READONLY (fndecl))
3102      {
3103        error ("invalid pure const state for function");
3104        return true;
3105      }
3106
3107   if (gimple_call_lhs (stmt)
3108       && (!is_gimple_lvalue (gimple_call_lhs (stmt))
3109           || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true)))
3110     {
3111       error ("invalid LHS in gimple call");
3112       return true;
3113     }
3114
3115   if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt))
3116     {
3117       error ("LHS in noreturn call");
3118       return true;
3119     }
3120
3121   fntype = gimple_call_fntype (stmt);
3122   if (fntype
3123       && gimple_call_lhs (stmt)
3124       && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3125                                      TREE_TYPE (fntype))
3126       /* ???  At least C++ misses conversions at assignments from
3127          void * call results.
3128          ???  Java is completely off.  Especially with functions
3129          returning java.lang.Object.
3130          For now simply allow arbitrary pointer type conversions.  */
3131       && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3132            && POINTER_TYPE_P (TREE_TYPE (fntype))))
3133     {
3134       error ("invalid conversion in gimple call");
3135       debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3136       debug_generic_stmt (TREE_TYPE (fntype));
3137       return true;
3138     }
3139
3140   if (gimple_call_chain (stmt)
3141       && !is_gimple_val (gimple_call_chain (stmt)))
3142     {
3143       error ("invalid static chain in gimple call");
3144       debug_generic_stmt (gimple_call_chain (stmt));
3145       return true;
3146     }
3147
3148   /* If there is a static chain argument, this should not be an indirect
3149      call, and the decl should have DECL_STATIC_CHAIN set.  */
3150   if (gimple_call_chain (stmt))
3151     {
3152       if (!gimple_call_fndecl (stmt))
3153         {
3154           error ("static chain in indirect gimple call");
3155           return true;
3156         }
3157       fn = TREE_OPERAND (fn, 0);
3158
3159       if (!DECL_STATIC_CHAIN (fn))
3160         {
3161           error ("static chain with function that doesn%'t use one");
3162           return true;
3163         }
3164     }
3165
3166   /* ???  The C frontend passes unpromoted arguments in case it
3167      didn't see a function declaration before the call.  So for now
3168      leave the call arguments mostly unverified.  Once we gimplify
3169      unit-at-a-time we have a chance to fix this.  */
3170
3171   for (i = 0; i < gimple_call_num_args (stmt); ++i)
3172     {
3173       tree arg = gimple_call_arg (stmt, i);
3174       if ((is_gimple_reg_type (TREE_TYPE (arg))
3175            && !is_gimple_val (arg))
3176           || (!is_gimple_reg_type (TREE_TYPE (arg))
3177               && !is_gimple_lvalue (arg)))
3178         {
3179           error ("invalid argument to gimple call");
3180           debug_generic_expr (arg);
3181           return true;
3182         }
3183     }
3184
3185   return false;
3186 }
3187
3188 /* Verifies the gimple comparison with the result type TYPE and
3189    the operands OP0 and OP1.  */
3190
3191 static bool
3192 verify_gimple_comparison (tree type, tree op0, tree op1)
3193 {
3194   tree op0_type = TREE_TYPE (op0);
3195   tree op1_type = TREE_TYPE (op1);
3196
3197   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3198     {
3199       error ("invalid operands in gimple comparison");
3200       return true;
3201     }
3202
3203   /* For comparisons we do not have the operations type as the
3204      effective type the comparison is carried out in.  Instead
3205      we require that either the first operand is trivially
3206      convertible into the second, or the other way around.
3207      Because we special-case pointers to void we allow
3208      comparisons of pointers with the same mode as well.  */
3209   if (!useless_type_conversion_p (op0_type, op1_type)
3210       && !useless_type_conversion_p (op1_type, op0_type)
3211       && (!POINTER_TYPE_P (op0_type)
3212           || !POINTER_TYPE_P (op1_type)
3213           || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3214     {
3215       error ("mismatching comparison operand types");
3216       debug_generic_expr (op0_type);
3217       debug_generic_expr (op1_type);
3218       return true;
3219     }
3220
3221   /* The resulting type of a comparison may be an effective boolean type.  */
3222   if (INTEGRAL_TYPE_P (type)
3223       && (TREE_CODE (type) == BOOLEAN_TYPE
3224           || TYPE_PRECISION (type) == 1))
3225     ;
3226   /* Or an integer vector type with the same size and element count
3227      as the comparison operand types.  */
3228   else if (TREE_CODE (type) == VECTOR_TYPE
3229            && TREE_CODE (TREE_TYPE (type)) == INTEGER_TYPE)
3230     {
3231       if (TREE_CODE (op0_type) != VECTOR_TYPE
3232           || TREE_CODE (op1_type) != VECTOR_TYPE)
3233         {
3234           error ("non-vector operands in vector comparison");
3235           debug_generic_expr (op0_type);
3236           debug_generic_expr (op1_type);
3237           return true;
3238         }
3239
3240       if (TYPE_VECTOR_SUBPARTS (type) != TYPE_VECTOR_SUBPARTS (op0_type)
3241           || (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (type)))
3242               != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0_type)))))
3243         {
3244           error ("invalid vector comparison resulting type");
3245           debug_generic_expr (type);
3246           return true;
3247         }
3248     }
3249   else
3250     {
3251       error ("bogus comparison result type");
3252       debug_generic_expr (type);
3253       return true;
3254     }
3255
3256   return false;
3257 }
3258
3259 /* Verify a gimple assignment statement STMT with an unary rhs.
3260    Returns true if anything is wrong.  */
3261
3262 static bool
3263 verify_gimple_assign_unary (gimple stmt)
3264 {
3265   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3266   tree lhs = gimple_assign_lhs (stmt);
3267   tree lhs_type = TREE_TYPE (lhs);
3268   tree rhs1 = gimple_assign_rhs1 (stmt);
3269   tree rhs1_type = TREE_TYPE (rhs1);
3270
3271   if (!is_gimple_reg (lhs))
3272     {
3273       error ("non-register as LHS of unary operation");
3274       return true;
3275     }
3276
3277   if (!is_gimple_val (rhs1))
3278     {
3279       error ("invalid operand in unary operation");
3280       return true;
3281     }
3282
3283   /* First handle conversions.  */
3284   switch (rhs_code)
3285     {
3286     CASE_CONVERT:
3287       {
3288         /* Allow conversions between integral types and pointers only if
3289            there is no sign or zero extension involved.
3290            For targets were the precision of ptrofftype doesn't match that
3291            of pointers we need to allow arbitrary conversions from and
3292            to ptrofftype.  */
3293         if ((POINTER_TYPE_P (lhs_type)
3294              && INTEGRAL_TYPE_P (rhs1_type)
3295              && (TYPE_PRECISION (lhs_type) >= TYPE_PRECISION (rhs1_type)
3296                  || ptrofftype_p (rhs1_type)))
3297             || (POINTER_TYPE_P (rhs1_type)
3298                 && INTEGRAL_TYPE_P (lhs_type)
3299                 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3300                     || ptrofftype_p (sizetype))))
3301           return false;
3302
3303         /* Allow conversion from integer to offset type and vice versa.  */
3304         if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3305              && TREE_CODE (rhs1_type) == INTEGER_TYPE)
3306             || (TREE_CODE (lhs_type) == INTEGER_TYPE
3307                 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3308           return false;
3309
3310         /* Otherwise assert we are converting between types of the
3311            same kind.  */
3312         if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3313           {
3314             error ("invalid types in nop conversion");
3315             debug_generic_expr (lhs_type);
3316             debug_generic_expr (rhs1_type);
3317             return true;
3318           }
3319
3320         return false;
3321       }
3322
3323     case ADDR_SPACE_CONVERT_EXPR:
3324       {
3325         if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3326             || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3327                 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3328           {
3329             error ("invalid types in address space conversion");
3330             debug_generic_expr (lhs_type);
3331             debug_generic_expr (rhs1_type);
3332             return true;
3333           }
3334
3335         return false;
3336       }
3337
3338     case FIXED_CONVERT_EXPR:
3339       {
3340         if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3341             && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3342           {
3343             error ("invalid types in fixed-point conversion");
3344             debug_generic_expr (lhs_type);
3345             debug_generic_expr (rhs1_type);
3346             return true;
3347           }
3348
3349         return false;
3350       }
3351
3352     case FLOAT_EXPR:
3353       {
3354         if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3355             && (!VECTOR_INTEGER_TYPE_P (rhs1_type)
3356                 || !VECTOR_FLOAT_TYPE_P(lhs_type)))
3357           {
3358             error ("invalid types in conversion to floating point");
3359             debug_generic_expr (lhs_type);
3360             debug_generic_expr (rhs1_type);
3361             return true;
3362           }
3363
3364         return false;
3365       }
3366
3367     case FIX_TRUNC_EXPR:
3368       {
3369         if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3370             && (!VECTOR_INTEGER_TYPE_P (lhs_type)
3371                 || !VECTOR_FLOAT_TYPE_P(rhs1_type)))
3372           {
3373             error ("invalid types in conversion to integer");
3374             debug_generic_expr (lhs_type);
3375             debug_generic_expr (rhs1_type);
3376             return true;
3377           }
3378
3379         return false;
3380       }
3381
3382     case VEC_UNPACK_HI_EXPR:
3383     case VEC_UNPACK_LO_EXPR:
3384     case REDUC_MAX_EXPR:
3385     case REDUC_MIN_EXPR:
3386     case REDUC_PLUS_EXPR:
3387     case VEC_UNPACK_FLOAT_HI_EXPR:
3388     case VEC_UNPACK_FLOAT_LO_EXPR:
3389       /* FIXME.  */
3390       return false;
3391
3392     case NEGATE_EXPR:
3393     case ABS_EXPR:
3394     case BIT_NOT_EXPR:
3395     case PAREN_EXPR:
3396     case NON_LVALUE_EXPR:
3397     case CONJ_EXPR:
3398       break;
3399
3400     default:
3401       gcc_unreachable ();
3402     }
3403
3404   /* For the remaining codes assert there is no conversion involved.  */
3405   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3406     {
3407       error ("non-trivial conversion in unary operation");
3408       debug_generic_expr (lhs_type);
3409       debug_generic_expr (rhs1_type);
3410       return true;
3411     }
3412
3413   return false;
3414 }
3415
3416 /* Verify a gimple assignment statement STMT with a binary rhs.
3417    Returns true if anything is wrong.  */
3418
3419 static bool
3420 verify_gimple_assign_binary (gimple stmt)
3421 {
3422   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3423   tree lhs = gimple_assign_lhs (stmt);
3424   tree lhs_type = TREE_TYPE (lhs);
3425   tree rhs1 = gimple_assign_rhs1 (stmt);
3426   tree rhs1_type = TREE_TYPE (rhs1);
3427   tree rhs2 = gimple_assign_rhs2 (stmt);
3428   tree rhs2_type = TREE_TYPE (rhs2);
3429
3430   if (!is_gimple_reg (lhs))
3431     {
3432       error ("non-register as LHS of binary operation");
3433       return true;
3434     }
3435
3436   if (!is_gimple_val (rhs1)
3437       || !is_gimple_val (rhs2))
3438     {
3439       error ("invalid operands in binary operation");
3440       return true;
3441     }
3442
3443   /* First handle operations that involve different types.  */
3444   switch (rhs_code)
3445     {
3446     case COMPLEX_EXPR:
3447       {
3448         if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3449             || !(INTEGRAL_TYPE_P (rhs1_type)
3450                  || SCALAR_FLOAT_TYPE_P (rhs1_type))
3451             || !(INTEGRAL_TYPE_P (rhs2_type)
3452                  || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3453           {
3454             error ("type mismatch in complex expression");
3455             debug_generic_expr (lhs_type);
3456             debug_generic_expr (rhs1_type);
3457             debug_generic_expr (rhs2_type);
3458             return true;
3459           }
3460
3461         return false;
3462       }
3463
3464     case LSHIFT_EXPR:
3465     case RSHIFT_EXPR:
3466     case LROTATE_EXPR:
3467     case RROTATE_EXPR:
3468       {
3469         /* Shifts and rotates are ok on integral types, fixed point
3470            types and integer vector types.  */
3471         if ((!INTEGRAL_TYPE_P (rhs1_type)
3472              && !FIXED_POINT_TYPE_P (rhs1_type)
3473              && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3474                   && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3475             || (!INTEGRAL_TYPE_P (rhs2_type)
3476                 /* Vector shifts of vectors are also ok.  */
3477                 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3478                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3479                      && TREE_CODE (rhs2_type) == VECTOR_TYPE
3480                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3481             || !useless_type_conversion_p (lhs_type, rhs1_type))
3482           {
3483             error ("type mismatch in shift expression");
3484             debug_generic_expr (lhs_type);
3485             debug_generic_expr (rhs1_type);
3486             debug_generic_expr (rhs2_type);
3487             return true;
3488           }
3489
3490         return false;
3491       }
3492
3493     case VEC_LSHIFT_EXPR:
3494     case VEC_RSHIFT_EXPR:
3495       {
3496         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3497             || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3498                  || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3499                  || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3500                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3501             || (!INTEGRAL_TYPE_P (rhs2_type)
3502                 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3503                     || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3504             || !useless_type_conversion_p (lhs_type, rhs1_type))
3505           {
3506             error ("type mismatch in vector shift expression");
3507             debug_generic_expr (lhs_type);
3508             debug_generic_expr (rhs1_type);
3509             debug_generic_expr (rhs2_type);
3510             return true;
3511           }
3512         /* For shifting a vector of non-integral components we
3513            only allow shifting by a constant multiple of the element size.  */
3514         if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3515             && (TREE_CODE (rhs2) != INTEGER_CST
3516                 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3517                                            TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3518           {
3519             error ("non-element sized vector shift of floating point vector");
3520             return true;
3521           }
3522
3523         return false;
3524       }
3525
3526     case WIDEN_LSHIFT_EXPR:
3527       {
3528         if (!INTEGRAL_TYPE_P (lhs_type)
3529             || !INTEGRAL_TYPE_P (rhs1_type)
3530             || TREE_CODE (rhs2) != INTEGER_CST
3531             || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)))
3532           {
3533             error ("type mismatch in widening vector shift expression");
3534             debug_generic_expr (lhs_type);
3535             debug_generic_expr (rhs1_type);
3536             debug_generic_expr (rhs2_type);
3537             return true;
3538           }
3539
3540         return false;
3541       }
3542
3543     case VEC_WIDEN_LSHIFT_HI_EXPR:
3544     case VEC_WIDEN_LSHIFT_LO_EXPR:
3545       {
3546         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3547             || TREE_CODE (lhs_type) != VECTOR_TYPE
3548             || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3549             || !INTEGRAL_TYPE_P (TREE_TYPE (lhs_type))
3550             || TREE_CODE (rhs2) != INTEGER_CST
3551             || (2 * TYPE_PRECISION (TREE_TYPE (rhs1_type))
3552                 > TYPE_PRECISION (TREE_TYPE (lhs_type))))
3553           {
3554             error ("type mismatch in widening vector shift expression");
3555             debug_generic_expr (lhs_type);
3556             debug_generic_expr (rhs1_type);
3557             debug_generic_expr (rhs2_type);
3558             return true;
3559           }
3560
3561         return false;
3562       }
3563
3564     case PLUS_EXPR:
3565     case MINUS_EXPR:
3566       {
3567         /* We use regular PLUS_EXPR and MINUS_EXPR for vectors.
3568            ???  This just makes the checker happy and may not be what is
3569            intended.  */
3570         if (TREE_CODE (lhs_type) == VECTOR_TYPE
3571             && POINTER_TYPE_P (TREE_TYPE (lhs_type)))
3572           {
3573             if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3574                 || TREE_CODE (rhs2_type) != VECTOR_TYPE)
3575               {
3576                 error ("invalid non-vector operands to vector valued plus");
3577                 return true;
3578               }
3579             lhs_type = TREE_TYPE (lhs_type);
3580             rhs1_type = TREE_TYPE (rhs1_type);
3581             rhs2_type = TREE_TYPE (rhs2_type);
3582             /* PLUS_EXPR is commutative, so we might end up canonicalizing
3583                the pointer to 2nd place.  */
3584             if (POINTER_TYPE_P (rhs2_type))
3585               {
3586                 tree tem = rhs1_type;
3587                 rhs1_type = rhs2_type;
3588                 rhs2_type = tem;
3589               }
3590             goto do_pointer_plus_expr_check;
3591           }
3592         if (POINTER_TYPE_P (lhs_type)
3593             || POINTER_TYPE_P (rhs1_type)
3594             || POINTER_TYPE_P (rhs2_type))
3595           {
3596             error ("invalid (pointer) operands to plus/minus");
3597             return true;
3598           }
3599
3600         /* Continue with generic binary expression handling.  */
3601         break;
3602       }
3603
3604     case POINTER_PLUS_EXPR:
3605       {
3606 do_pointer_plus_expr_check:
3607         if (!POINTER_TYPE_P (rhs1_type)
3608             || !useless_type_conversion_p (lhs_type, rhs1_type)
3609             || !ptrofftype_p (rhs2_type))
3610           {
3611             error ("type mismatch in pointer plus expression");
3612             debug_generic_stmt (lhs_type);
3613             debug_generic_stmt (rhs1_type);
3614             debug_generic_stmt (rhs2_type);
3615             return true;
3616           }
3617
3618         return false;
3619       }
3620
3621     case TRUTH_ANDIF_EXPR:
3622     case TRUTH_ORIF_EXPR:
3623     case TRUTH_AND_EXPR:
3624     case TRUTH_OR_EXPR:
3625     case TRUTH_XOR_EXPR:
3626
3627       gcc_unreachable ();
3628
3629     case LT_EXPR:
3630     case LE_EXPR:
3631     case GT_EXPR:
3632     case GE_EXPR:
3633     case EQ_EXPR:
3634     case NE_EXPR:
3635     case UNORDERED_EXPR:
3636     case ORDERED_EXPR:
3637     case UNLT_EXPR:
3638     case UNLE_EXPR:
3639     case UNGT_EXPR:
3640     case UNGE_EXPR:
3641     case UNEQ_EXPR:
3642     case LTGT_EXPR:
3643       /* Comparisons are also binary, but the result type is not
3644          connected to the operand types.  */
3645       return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3646
3647     case WIDEN_MULT_EXPR:
3648       if (TREE_CODE (lhs_type) != INTEGER_TYPE)
3649         return true;
3650       return ((2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type))
3651               || (TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type)));
3652
3653     case WIDEN_SUM_EXPR:
3654     case VEC_WIDEN_MULT_HI_EXPR:
3655     case VEC_WIDEN_MULT_LO_EXPR:
3656     case VEC_PACK_TRUNC_EXPR:
3657     case VEC_PACK_SAT_EXPR:
3658     case VEC_PACK_FIX_TRUNC_EXPR:
3659     case VEC_EXTRACT_EVEN_EXPR:
3660     case VEC_EXTRACT_ODD_EXPR:
3661     case VEC_INTERLEAVE_HIGH_EXPR:
3662     case VEC_INTERLEAVE_LOW_EXPR:
3663       /* FIXME.  */
3664       return false;
3665
3666     case MULT_EXPR:
3667     case TRUNC_DIV_EXPR:
3668     case CEIL_DIV_EXPR:
3669     case FLOOR_DIV_EXPR:
3670     case ROUND_DIV_EXPR:
3671     case TRUNC_MOD_EXPR:
3672     case CEIL_MOD_EXPR:
3673     case FLOOR_MOD_EXPR:
3674     case ROUND_MOD_EXPR:
3675     case RDIV_EXPR:
3676     case EXACT_DIV_EXPR:
3677     case MIN_EXPR:
3678     case MAX_EXPR:
3679     case BIT_IOR_EXPR:
3680     case BIT_XOR_EXPR:
3681     case BIT_AND_EXPR:
3682       /* Continue with generic binary expression handling.  */
3683       break;
3684
3685     default:
3686       gcc_unreachable ();
3687     }
3688
3689   if (!useless_type_conversion_p (lhs_type, rhs1_type)
3690       || !useless_type_conversion_p (lhs_type, rhs2_type))
3691     {
3692       error ("type mismatch in binary expression");
3693       debug_generic_stmt (lhs_type);
3694       debug_generic_stmt (rhs1_type);
3695       debug_generic_stmt (rhs2_type);
3696       return true;
3697     }
3698
3699   return false;
3700 }
3701
3702 /* Verify a gimple assignment statement STMT with a ternary rhs.
3703    Returns true if anything is wrong.  */
3704
3705 static bool
3706 verify_gimple_assign_ternary (gimple stmt)
3707 {
3708   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3709   tree lhs = gimple_assign_lhs (stmt);
3710   tree lhs_type = TREE_TYPE (lhs);
3711   tree rhs1 = gimple_assign_rhs1 (stmt);
3712   tree rhs1_type = TREE_TYPE (rhs1);
3713   tree rhs2 = gimple_assign_rhs2 (stmt);
3714   tree rhs2_type = TREE_TYPE (rhs2);
3715   tree rhs3 = gimple_assign_rhs3 (stmt);
3716   tree rhs3_type = TREE_TYPE (rhs3);
3717
3718   if (!is_gimple_reg (lhs))
3719     {
3720       error ("non-register as LHS of ternary operation");
3721       return true;
3722     }
3723
3724   if (((rhs_code == VEC_COND_EXPR || rhs_code == COND_EXPR)
3725        ? !is_gimple_condexpr (rhs1) : !is_gimple_val (rhs1))
3726       || !is_gimple_val (rhs2)
3727       || !is_gimple_val (rhs3))
3728     {
3729       error ("invalid operands in ternary operation");
3730       return true;
3731     }
3732
3733   /* First handle operations that involve different types.  */
3734   switch (rhs_code)
3735     {
3736     case WIDEN_MULT_PLUS_EXPR:
3737     case WIDEN_MULT_MINUS_EXPR:
3738       if ((!INTEGRAL_TYPE_P (rhs1_type)
3739            && !FIXED_POINT_TYPE_P (rhs1_type))
3740           || !useless_type_conversion_p (rhs1_type, rhs2_type)
3741           || !useless_type_conversion_p (lhs_type, rhs3_type)
3742           || 2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)
3743           || TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type))
3744         {
3745           error ("type mismatch in widening multiply-accumulate expression");
3746           debug_generic_expr (lhs_type);
3747           debug_generic_expr (rhs1_type);
3748           debug_generic_expr (rhs2_type);
3749           debug_generic_expr (rhs3_type);
3750           return true;
3751         }
3752       break;
3753
3754     case FMA_EXPR:
3755       if (!useless_type_conversion_p (lhs_type, rhs1_type)
3756           || !useless_type_conversion_p (lhs_type, rhs2_type)
3757           || !useless_type_conversion_p (lhs_type, rhs3_type))
3758         {
3759           error ("type mismatch in fused multiply-add expression");
3760           debug_generic_expr (lhs_type);
3761           debug_generic_expr (rhs1_type);
3762           debug_generic_expr (rhs2_type);
3763           debug_generic_expr (rhs3_type);
3764           return true;
3765         }
3766       break;
3767
3768     case COND_EXPR:
3769     case VEC_COND_EXPR:
3770       if (!useless_type_conversion_p (lhs_type, rhs2_type)
3771           || !useless_type_conversion_p (lhs_type, rhs3_type))
3772         {
3773           error ("type mismatch in conditional expression");
3774           debug_generic_expr (lhs_type);
3775           debug_generic_expr (rhs2_type);
3776           debug_generic_expr (rhs3_type);
3777           return true;
3778         }
3779       break;
3780
3781     case VEC_PERM_EXPR:
3782       if (!useless_type_conversion_p (lhs_type, rhs1_type)
3783           || !useless_type_conversion_p (lhs_type, rhs2_type))
3784         {
3785           error ("type mismatch in vector permute expression");
3786           debug_generic_expr (lhs_type);
3787           debug_generic_expr (rhs1_type);
3788           debug_generic_expr (rhs2_type);
3789           debug_generic_expr (rhs3_type);
3790           return true;
3791         }
3792
3793       if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3794           || TREE_CODE (rhs2_type) != VECTOR_TYPE
3795           || TREE_CODE (rhs3_type) != VECTOR_TYPE)
3796         {
3797           error ("vector types expected in vector permute expression");
3798           debug_generic_expr (lhs_type);
3799           debug_generic_expr (rhs1_type);
3800           debug_generic_expr (rhs2_type);
3801           debug_generic_expr (rhs3_type);
3802           return true;
3803         }
3804
3805       if (TYPE_VECTOR_SUBPARTS (rhs1_type) != TYPE_VECTOR_SUBPARTS (rhs2_type)
3806           || TYPE_VECTOR_SUBPARTS (rhs2_type)
3807              != TYPE_VECTOR_SUBPARTS (rhs3_type)
3808           || TYPE_VECTOR_SUBPARTS (rhs3_type)
3809              != TYPE_VECTOR_SUBPARTS (lhs_type))
3810         {
3811           error ("vectors with different element number found "
3812                  "in vector permute expression");
3813           debug_generic_expr (lhs_type);
3814           debug_generic_expr (rhs1_type);
3815           debug_generic_expr (rhs2_type);
3816           debug_generic_expr (rhs3_type);
3817           return true;
3818         }
3819
3820       if (TREE_CODE (TREE_TYPE (rhs3_type)) != INTEGER_TYPE
3821           || GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs3_type)))
3822              != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1_type))))
3823         {
3824           error ("invalid mask type in vector permute expression");
3825           debug_generic_expr (lhs_type);
3826           debug_generic_expr (rhs1_type);
3827           debug_generic_expr (rhs2_type);
3828           debug_generic_expr (rhs3_type);
3829           return true;
3830         }
3831
3832       return false;
3833
3834     case DOT_PROD_EXPR:
3835     case REALIGN_LOAD_EXPR:
3836       /* FIXME.  */
3837       return false;
3838
3839     default:
3840       gcc_unreachable ();
3841     }
3842   return false;
3843 }
3844
3845 /* Verify a gimple assignment statement STMT with a single rhs.
3846    Returns true if anything is wrong.  */
3847
3848 static bool
3849 verify_gimple_assign_single (gimple stmt)
3850 {
3851   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3852   tree lhs = gimple_assign_lhs (stmt);
3853   tree lhs_type = TREE_TYPE (lhs);
3854   tree rhs1 = gimple_assign_rhs1 (stmt);
3855   tree rhs1_type = TREE_TYPE (rhs1);
3856   bool res = false;
3857
3858   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3859     {
3860       error ("non-trivial conversion at assignment");
3861       debug_generic_expr (lhs_type);
3862       debug_generic_expr (rhs1_type);
3863       return true;
3864     }
3865
3866   if (handled_component_p (lhs))
3867     res |= verify_types_in_gimple_reference (lhs, true);
3868
3869   /* Special codes we cannot handle via their class.  */
3870   switch (rhs_code)
3871     {
3872     case ADDR_EXPR:
3873       {
3874         tree op = TREE_OPERAND (rhs1, 0);
3875         if (!is_gimple_addressable (op))
3876           {
3877             error ("invalid operand in unary expression");
3878             return true;
3879           }
3880
3881         /* Technically there is no longer a need for matching types, but
3882            gimple hygiene asks for this check.  In LTO we can end up
3883            combining incompatible units and thus end up with addresses
3884            of globals that change their type to a common one.  */
3885         if (!in_lto_p
3886             && !types_compatible_p (TREE_TYPE (op),
3887                                     TREE_TYPE (TREE_TYPE (rhs1)))
3888             && !one_pointer_to_useless_type_conversion_p (TREE_TYPE (rhs1),
3889                                                           TREE_TYPE (op)))
3890           {
3891             error ("type mismatch in address expression");
3892             debug_generic_stmt (TREE_TYPE (rhs1));
3893             debug_generic_stmt (TREE_TYPE (op));
3894             return true;
3895           }
3896
3897         return verify_types_in_gimple_reference (op, true);
3898       }
3899
3900     /* tcc_reference  */
3901     case INDIRECT_REF:
3902       error ("INDIRECT_REF in gimple IL");
3903       return true;
3904
3905     case COMPONENT_REF:
3906     case BIT_FIELD_REF:
3907     case ARRAY_REF:
3908     case ARRAY_RANGE_REF:
3909     case VIEW_CONVERT_EXPR:
3910     case REALPART_EXPR:
3911     case IMAGPART_EXPR:
3912     case TARGET_MEM_REF:
3913     case MEM_REF:
3914       if (!is_gimple_reg (lhs)
3915           && is_gimple_reg_type (TREE_TYPE (lhs)))
3916         {
3917           error ("invalid rhs for gimple memory store");
3918           debug_generic_stmt (lhs);
3919           debug_generic_stmt (rhs1);
3920           return true;
3921         }
3922       return res || verify_types_in_gimple_reference (rhs1, false);
3923
3924     /* tcc_constant  */
3925     case SSA_NAME:
3926     case INTEGER_CST:
3927     case REAL_CST:
3928     case FIXED_CST:
3929     case COMPLEX_CST:
3930     case VECTOR_CST:
3931     case STRING_CST:
3932       return res;
3933
3934     /* tcc_declaration  */
3935     case CONST_DECL:
3936       return res;
3937     case VAR_DECL:
3938     case PARM_DECL:
3939       if (!is_gimple_reg (lhs)
3940           && !is_gimple_reg (rhs1)
3941           && is_gimple_reg_type (TREE_TYPE (lhs)))
3942         {
3943           error ("invalid rhs for gimple memory store");
3944           debug_generic_stmt (lhs);
3945           debug_generic_stmt (rhs1);
3946           return true;
3947         }
3948       return res;
3949
3950     case CONSTRUCTOR:
3951     case OBJ_TYPE_REF:
3952     case ASSERT_EXPR:
3953     case WITH_SIZE_EXPR:
3954       /* FIXME.  */
3955       return res;
3956
3957     default:;
3958     }
3959
3960   return res;
3961 }
3962
3963 /* Verify the contents of a GIMPLE_ASSIGN STMT.  Returns true when there
3964    is a problem, otherwise false.  */
3965
3966 static bool
3967 verify_gimple_assign (gimple stmt)
3968 {
3969   switch (gimple_assign_rhs_class (stmt))
3970     {
3971     case GIMPLE_SINGLE_RHS:
3972       return verify_gimple_assign_single (stmt);
3973
3974     case GIMPLE_UNARY_RHS:
3975       return verify_gimple_assign_unary (stmt);
3976
3977     case GIMPLE_BINARY_RHS:
3978       return verify_gimple_assign_binary (stmt);
3979
3980     case GIMPLE_TERNARY_RHS:
3981       return verify_gimple_assign_ternary (stmt);
3982
3983     default:
3984       gcc_unreachable ();
3985     }
3986 }
3987
3988 /* Verify the contents of a GIMPLE_RETURN STMT.  Returns true when there
3989    is a problem, otherwise false.  */
3990
3991 static bool
3992 verify_gimple_return (gimple stmt)
3993 {
3994   tree op = gimple_return_retval (stmt);
3995   tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
3996
3997   /* We cannot test for present return values as we do not fix up missing
3998      return values from the original source.  */
3999   if (op == NULL)
4000     return false;
4001
4002   if (!is_gimple_val (op)
4003       && TREE_CODE (op) != RESULT_DECL)
4004     {
4005       error ("invalid operand in return statement");
4006       debug_generic_stmt (op);
4007       return true;
4008     }
4009
4010   if ((TREE_CODE (op) == RESULT_DECL
4011        && DECL_BY_REFERENCE (op))
4012       || (TREE_CODE (op) == SSA_NAME
4013           && TREE_CODE (SSA_NAME_VAR (op)) == RESULT_DECL
4014           && DECL_BY_REFERENCE (SSA_NAME_VAR (op))))
4015     op = TREE_TYPE (op);
4016
4017   if (!useless_type_conversion_p (restype, TREE_TYPE (op)))
4018     {
4019       error ("invalid conversion in return statement");
4020       debug_generic_stmt (restype);
4021       debug_generic_stmt (TREE_TYPE (op));
4022       return true;
4023     }
4024
4025   return false;
4026 }
4027
4028
4029 /* Verify the contents of a GIMPLE_GOTO STMT.  Returns true when there
4030    is a problem, otherwise false.  */
4031
4032 static bool
4033 verify_gimple_goto (gimple stmt)
4034 {
4035   tree dest = gimple_goto_dest (stmt);
4036
4037   /* ???  We have two canonical forms of direct goto destinations, a
4038      bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL.  */
4039   if (TREE_CODE (dest) != LABEL_DECL
4040       && (!is_gimple_val (dest)
4041           || !POINTER_TYPE_P (TREE_TYPE (dest))))
4042     {
4043       error ("goto destination is neither a label nor a pointer");
4044       return true;
4045     }
4046
4047   return false;
4048 }
4049
4050 /* Verify the contents of a GIMPLE_SWITCH STMT.  Returns true when there
4051    is a problem, otherwise false.  */
4052
4053 static bool
4054 verify_gimple_switch (gimple stmt)
4055 {
4056   if (!is_gimple_val (gimple_switch_index (stmt)))
4057     {
4058       error ("invalid operand to switch statement");
4059       debug_generic_stmt (gimple_switch_index (stmt));
4060       return true;
4061     }
4062
4063   return false;
4064 }
4065
4066
4067 /* Verify a gimple debug statement STMT.
4068    Returns true if anything is wrong.  */
4069
4070 static bool
4071 verify_gimple_debug (gimple stmt ATTRIBUTE_UNUSED)
4072 {
4073   /* There isn't much that could be wrong in a gimple debug stmt.  A
4074      gimple debug bind stmt, for example, maps a tree, that's usually
4075      a VAR_DECL or a PARM_DECL, but that could also be some scalarized
4076      component or member of an aggregate type, to another tree, that
4077      can be an arbitrary expression.  These stmts expand into debug
4078      insns, and are converted to debug notes by var-tracking.c.  */
4079   return false;
4080 }
4081
4082 /* Verify a gimple label statement STMT.
4083    Returns true if anything is wrong.  */
4084
4085 static bool
4086 verify_gimple_label (gimple stmt)
4087 {
4088   tree decl = gimple_label_label (stmt);
4089   int uid;
4090   bool err = false;
4091
4092   if (TREE_CODE (decl) != LABEL_DECL)
4093     return true;
4094
4095   uid = LABEL_DECL_UID (decl);
4096   if (cfun->cfg
4097       && (uid == -1
4098           || VEC_index (basic_block,
4099                         label_to_block_map, uid) != gimple_bb (stmt)))
4100     {
4101       error ("incorrect entry in label_to_block_map");
4102       err |= true;
4103     }
4104
4105   uid = EH_LANDING_PAD_NR (decl);
4106   if (uid)
4107     {
4108       eh_landing_pad lp = get_eh_landing_pad_from_number (uid);
4109       if (decl != lp->post_landing_pad)
4110         {
4111           error ("incorrect setting of landing pad number");
4112           err |= true;
4113         }
4114     }
4115
4116   return err;
4117 }
4118
4119 /* Verify the GIMPLE statement STMT.  Returns true if there is an
4120    error, otherwise false.  */
4121
4122 static bool
4123 verify_gimple_stmt (gimple stmt)
4124 {
4125   switch (gimple_code (stmt))
4126     {
4127     case GIMPLE_ASSIGN:
4128       return verify_gimple_assign (stmt);
4129
4130     case GIMPLE_LABEL:
4131       return verify_gimple_label (stmt);
4132
4133     case GIMPLE_CALL:
4134       return verify_gimple_call (stmt);
4135
4136     case GIMPLE_COND:
4137       if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
4138         {
4139           error ("invalid comparison code in gimple cond");
4140           return true;
4141         }
4142       if (!(!gimple_cond_true_label (stmt)
4143             || TREE_CODE (gimple_cond_true_label (stmt)) == LABEL_DECL)
4144           || !(!gimple_cond_false_label (stmt)
4145                || TREE_CODE (gimple_cond_false_label (stmt)) == LABEL_DECL))
4146         {
4147           error ("invalid labels in gimple cond");
4148           return true;
4149         }
4150
4151       return verify_gimple_comparison (boolean_type_node,
4152                                        gimple_cond_lhs (stmt),
4153                                        gimple_cond_rhs (stmt));
4154
4155     case GIMPLE_GOTO:
4156       return verify_gimple_goto (stmt);
4157
4158     case GIMPLE_SWITCH:
4159       return verify_gimple_switch (stmt);
4160
4161     case GIMPLE_RETURN:
4162       return verify_gimple_return (stmt);
4163
4164     case GIMPLE_ASM:
4165       return false;
4166
4167     /* Tuples that do not have tree operands.  */
4168     case GIMPLE_NOP:
4169     case GIMPLE_PREDICT:
4170     case GIMPLE_RESX:
4171     case GIMPLE_EH_DISPATCH:
4172     case GIMPLE_EH_MUST_NOT_THROW:
4173       return false;
4174
4175     CASE_GIMPLE_OMP:
4176       /* OpenMP directives are validated by the FE and never operated
4177          on by the optimizers.  Furthermore, GIMPLE_OMP_FOR may contain
4178          non-gimple expressions when the main index variable has had
4179          its address taken.  This does not affect the loop itself
4180          because the header of an GIMPLE_OMP_FOR is merely used to determine
4181          how to setup the parallel iteration.  */
4182       return false;
4183
4184     case GIMPLE_DEBUG:
4185       return verify_gimple_debug (stmt);
4186
4187     default:
4188       gcc_unreachable ();
4189     }
4190 }
4191
4192 /* Verify the contents of a GIMPLE_PHI.  Returns true if there is a problem,
4193    and false otherwise.  */
4194
4195 static bool
4196 verify_gimple_phi (gimple phi)
4197 {
4198   bool err = false;
4199   unsigned i;
4200   tree phi_result = gimple_phi_result (phi);
4201   bool virtual_p;
4202
4203   if (!phi_result)
4204     {
4205       error ("invalid PHI result");
4206       return true;
4207     }
4208
4209   virtual_p = !is_gimple_reg (phi_result);
4210   if (TREE_CODE (phi_result) != SSA_NAME
4211       || (virtual_p
4212           && SSA_NAME_VAR (phi_result) != gimple_vop (cfun)))
4213     {
4214       error ("invalid PHI result");
4215       err = true;
4216     }
4217
4218   for (i = 0; i < gimple_phi_num_args (phi); i++)
4219     {
4220       tree t = gimple_phi_arg_def (phi, i);
4221
4222       if (!t)
4223         {
4224           error ("missing PHI def");
4225           err |= true;
4226           continue;
4227         }
4228       /* Addressable variables do have SSA_NAMEs but they
4229          are not considered gimple values.  */
4230       else if ((TREE_CODE (t) == SSA_NAME
4231                 && virtual_p != !is_gimple_reg (t))
4232                || (virtual_p
4233                    && (TREE_CODE (t) != SSA_NAME
4234                        || SSA_NAME_VAR (t) != gimple_vop (cfun)))
4235                || (!virtual_p
4236                    && !is_gimple_val (t)))
4237         {
4238           error ("invalid PHI argument");
4239           debug_generic_expr (t);
4240           err |= true;
4241         }
4242 #ifdef ENABLE_TYPES_CHECKING
4243       if (!useless_type_conversion_p (TREE_TYPE (phi_result), TREE_TYPE (t)))
4244         {
4245           error ("incompatible types in PHI argument %u", i);
4246           debug_generic_stmt (TREE_TYPE (phi_result));
4247           debug_generic_stmt (TREE_TYPE (t));
4248           err |= true;
4249         }
4250 #endif
4251     }
4252
4253   return err;
4254 }
4255
4256 /* Verify the GIMPLE statements inside the sequence STMTS.  */
4257
4258 static bool
4259 verify_gimple_in_seq_2 (gimple_seq stmts)
4260 {
4261   gimple_stmt_iterator ittr;
4262   bool err = false;
4263
4264   for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
4265     {
4266       gimple stmt = gsi_stmt (ittr);
4267
4268       switch (gimple_code (stmt))
4269         {
4270         case GIMPLE_BIND:
4271           err |= verify_gimple_in_seq_2 (gimple_bind_body (stmt));
4272           break;
4273
4274         case GIMPLE_TRY:
4275           err |= verify_gimple_in_seq_2 (gimple_try_eval (stmt));
4276           err |= verify_gimple_in_seq_2 (gimple_try_cleanup (stmt));
4277           break;
4278
4279         case GIMPLE_EH_FILTER:
4280           err |= verify_gimple_in_seq_2 (gimple_eh_filter_failure (stmt));
4281           break;
4282
4283         case GIMPLE_CATCH:
4284           err |= verify_gimple_in_seq_2 (gimple_catch_handler (stmt));
4285           break;
4286
4287         default:
4288           {
4289             bool err2 = verify_gimple_stmt (stmt);
4290             if (err2)
4291               debug_gimple_stmt (stmt);
4292             err |= err2;
4293           }
4294         }
4295     }
4296
4297   return err;
4298 }
4299
4300
4301 /* Verify the GIMPLE statements inside the statement list STMTS.  */
4302
4303 DEBUG_FUNCTION void
4304 verify_gimple_in_seq (gimple_seq stmts)
4305 {
4306   timevar_push (TV_TREE_STMT_VERIFY);
4307   if (verify_gimple_in_seq_2 (stmts))
4308     internal_error ("verify_gimple failed");
4309   timevar_pop (TV_TREE_STMT_VERIFY);
4310 }
4311
4312 /* Return true when the T can be shared.  */
4313
4314 bool
4315 tree_node_can_be_shared (tree t)
4316 {
4317   if (IS_TYPE_OR_DECL_P (t)
4318       || is_gimple_min_invariant (t)
4319       || TREE_CODE (t) == SSA_NAME
4320       || t == error_mark_node
4321       || TREE_CODE (t) == IDENTIFIER_NODE)
4322     return true;
4323
4324   if (TREE_CODE (t) == CASE_LABEL_EXPR)
4325     return true;
4326
4327   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4328            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4329          || TREE_CODE (t) == COMPONENT_REF
4330          || TREE_CODE (t) == REALPART_EXPR
4331          || TREE_CODE (t) == IMAGPART_EXPR)
4332     t = TREE_OPERAND (t, 0);
4333
4334   if (DECL_P (t))
4335     return true;
4336
4337   return false;
4338 }
4339
4340 /* Called via walk_gimple_stmt.  Verify tree sharing.  */
4341
4342 static tree
4343 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4344 {
4345   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4346   struct pointer_set_t *visited = (struct pointer_set_t *) wi->info;
4347
4348   if (tree_node_can_be_shared (*tp))
4349     {
4350       *walk_subtrees = false;
4351       return NULL;
4352     }
4353
4354   if (pointer_set_insert (visited, *tp))
4355     return *tp;
4356
4357   return NULL;
4358 }
4359
4360 static bool eh_error_found;
4361 static int
4362 verify_eh_throw_stmt_node (void **slot, void *data)
4363 {
4364   struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4365   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4366
4367   if (!pointer_set_contains (visited, node->stmt))
4368     {
4369       error ("dead STMT in EH table");
4370       debug_gimple_stmt (node->stmt);
4371       eh_error_found = true;
4372     }
4373   return 1;
4374 }
4375
4376 /* Verify the GIMPLE statements in the CFG of FN.  */
4377
4378 DEBUG_FUNCTION void
4379 verify_gimple_in_cfg (struct function *fn)
4380 {
4381   basic_block bb;
4382   bool err = false;
4383   struct pointer_set_t *visited, *visited_stmts;
4384
4385   timevar_push (TV_TREE_STMT_VERIFY);
4386   visited = pointer_set_create ();
4387   visited_stmts = pointer_set_create ();
4388
4389   FOR_EACH_BB_FN (bb, fn)
4390     {
4391       gimple_stmt_iterator gsi;
4392
4393       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4394         {
4395           gimple phi = gsi_stmt (gsi);
4396           bool err2 = false;
4397           unsigned i;
4398
4399           pointer_set_insert (visited_stmts, phi);
4400
4401           if (gimple_bb (phi) != bb)
4402             {
4403               error ("gimple_bb (phi) is set to a wrong basic block");
4404               err2 = true;
4405             }
4406
4407           err2 |= verify_gimple_phi (phi);
4408
4409           for (i = 0; i < gimple_phi_num_args (phi); i++)
4410             {
4411               tree arg = gimple_phi_arg_def (phi, i);
4412               tree addr = walk_tree (&arg, verify_node_sharing, visited, NULL);
4413               if (addr)
4414                 {
4415                   error ("incorrect sharing of tree nodes");
4416                   debug_generic_expr (addr);
4417                   err2 |= true;
4418                 }
4419             }
4420
4421           if (err2)
4422             debug_gimple_stmt (phi);
4423           err |= err2;
4424         }
4425
4426       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4427         {
4428           gimple stmt = gsi_stmt (gsi);
4429           bool err2 = false;
4430           struct walk_stmt_info wi;
4431           tree addr;
4432           int lp_nr;
4433
4434           pointer_set_insert (visited_stmts, stmt);
4435
4436           if (gimple_bb (stmt) != bb)
4437             {
4438               error ("gimple_bb (stmt) is set to a wrong basic block");
4439               err2 = true;
4440             }
4441
4442           err2 |= verify_gimple_stmt (stmt);
4443
4444           memset (&wi, 0, sizeof (wi));
4445           wi.info = (void *) visited;
4446           addr = walk_gimple_op (stmt, verify_node_sharing, &wi);
4447           if (addr)
4448             {
4449               error ("incorrect sharing of tree nodes");
4450               debug_generic_expr (addr);
4451               err2 |= true;
4452             }
4453
4454           /* ???  Instead of not checking these stmts at all the walker
4455              should know its context via wi.  */
4456           if (!is_gimple_debug (stmt)
4457               && !is_gimple_omp (stmt))
4458             {
4459               memset (&wi, 0, sizeof (wi));
4460               addr = walk_gimple_op (stmt, verify_expr, &wi);
4461               if (addr)
4462                 {
4463                   debug_generic_expr (addr);
4464                   inform (gimple_location (stmt), "in statement");
4465                   err2 |= true;
4466                 }
4467             }
4468
4469           /* If the statement is marked as part of an EH region, then it is
4470              expected that the statement could throw.  Verify that when we
4471              have optimizations that simplify statements such that we prove
4472              that they cannot throw, that we update other data structures
4473              to match.  */
4474           lp_nr = lookup_stmt_eh_lp (stmt);
4475           if (lp_nr != 0)
4476             {
4477               if (!stmt_could_throw_p (stmt))
4478                 {
4479                   error ("statement marked for throw, but doesn%'t");
4480                   err2 |= true;
4481                 }
4482               else if (lp_nr > 0
4483                        && !gsi_one_before_end_p (gsi)
4484                        && stmt_can_throw_internal (stmt))
4485                 {
4486                   error ("statement marked for throw in middle of block");
4487                   err2 |= true;
4488                 }
4489             }
4490
4491           if (err2)
4492             debug_gimple_stmt (stmt);
4493           err |= err2;
4494         }
4495     }
4496
4497   eh_error_found = false;
4498   if (get_eh_throw_stmt_table (cfun))
4499     htab_traverse (get_eh_throw_stmt_table (cfun),
4500                    verify_eh_throw_stmt_node,
4501                    visited_stmts);
4502
4503   if (err || eh_error_found)
4504     internal_error ("verify_gimple failed");
4505
4506   pointer_set_destroy (visited);
4507   pointer_set_destroy (visited_stmts);
4508   verify_histograms ();
4509   timevar_pop (TV_TREE_STMT_VERIFY);
4510 }
4511
4512
4513 /* Verifies that the flow information is OK.  */
4514
4515 static int
4516 gimple_verify_flow_info (void)
4517 {
4518   int err = 0;
4519   basic_block bb;
4520   gimple_stmt_iterator gsi;
4521   gimple stmt;
4522   edge e;
4523   edge_iterator ei;
4524
4525   if (ENTRY_BLOCK_PTR->il.gimple)
4526     {
4527       error ("ENTRY_BLOCK has IL associated with it");
4528       err = 1;
4529     }
4530
4531   if (EXIT_BLOCK_PTR->il.gimple)
4532     {
4533       error ("EXIT_BLOCK has IL associated with it");
4534       err = 1;
4535     }
4536
4537   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4538     if (e->flags & EDGE_FALLTHRU)
4539       {
4540         error ("fallthru to exit from bb %d", e->src->index);
4541         err = 1;
4542       }
4543
4544   FOR_EACH_BB (bb)
4545     {
4546       bool found_ctrl_stmt = false;
4547
4548       stmt = NULL;
4549
4550       /* Skip labels on the start of basic block.  */
4551       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4552         {
4553           tree label;
4554           gimple prev_stmt = stmt;
4555
4556           stmt = gsi_stmt (gsi);
4557
4558           if (gimple_code (stmt) != GIMPLE_LABEL)
4559             break;
4560
4561           label = gimple_label_label (stmt);
4562           if (prev_stmt && DECL_NONLOCAL (label))
4563             {
4564               error ("nonlocal label ");
4565               print_generic_expr (stderr, label, 0);
4566               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4567                        bb->index);
4568               err = 1;
4569             }
4570
4571           if (prev_stmt && EH_LANDING_PAD_NR (label) != 0)
4572             {
4573               error ("EH landing pad label ");
4574               print_generic_expr (stderr, label, 0);
4575               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4576                        bb->index);
4577               err = 1;
4578             }
4579
4580           if (label_to_block (label) != bb)
4581             {
4582               error ("label ");
4583               print_generic_expr (stderr, label, 0);
4584               fprintf (stderr, " to block does not match in bb %d",
4585                        bb->index);
4586               err = 1;
4587             }
4588
4589           if (decl_function_context (label) != current_function_decl)
4590             {
4591               error ("label ");
4592               print_generic_expr (stderr, label, 0);
4593               fprintf (stderr, " has incorrect context in bb %d",
4594                        bb->index);
4595               err = 1;
4596             }
4597         }
4598
4599       /* Verify that body of basic block BB is free of control flow.  */
4600       for (; !gsi_end_p (gsi); gsi_next (&gsi))
4601         {
4602           gimple stmt = gsi_stmt (gsi);
4603
4604           if (found_ctrl_stmt)
4605             {
4606               error ("control flow in the middle of basic block %d",
4607                      bb->index);
4608               err = 1;
4609             }
4610
4611           if (stmt_ends_bb_p (stmt))
4612             found_ctrl_stmt = true;
4613
4614           if (gimple_code (stmt) == GIMPLE_LABEL)
4615             {
4616               error ("label ");
4617               print_generic_expr (stderr, gimple_label_label (stmt), 0);
4618               fprintf (stderr, " in the middle of basic block %d", bb->index);
4619               err = 1;
4620             }
4621         }
4622
4623       gsi = gsi_last_bb (bb);
4624       if (gsi_end_p (gsi))
4625         continue;
4626
4627       stmt = gsi_stmt (gsi);
4628
4629       if (gimple_code (stmt) == GIMPLE_LABEL)
4630         continue;
4631
4632       err |= verify_eh_edges (stmt);
4633
4634       if (is_ctrl_stmt (stmt))
4635         {
4636           FOR_EACH_EDGE (e, ei, bb->succs)
4637             if (e->flags & EDGE_FALLTHRU)
4638               {
4639                 error ("fallthru edge after a control statement in bb %d",
4640                        bb->index);
4641                 err = 1;
4642               }
4643         }
4644
4645       if (gimple_code (stmt) != GIMPLE_COND)
4646         {
4647           /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4648              after anything else but if statement.  */
4649           FOR_EACH_EDGE (e, ei, bb->succs)
4650             if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4651               {
4652                 error ("true/false edge after a non-GIMPLE_COND in bb %d",
4653                        bb->index);
4654                 err = 1;
4655               }
4656         }
4657
4658       switch (gimple_code (stmt))
4659         {
4660         case GIMPLE_COND:
4661           {
4662             edge true_edge;
4663             edge false_edge;
4664
4665             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4666
4667             if (!true_edge
4668                 || !false_edge
4669                 || !(true_edge->flags & EDGE_TRUE_VALUE)
4670                 || !(false_edge->flags & EDGE_FALSE_VALUE)
4671                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4672                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4673                 || EDGE_COUNT (bb->succs) >= 3)
4674               {
4675                 error ("wrong outgoing edge flags at end of bb %d",
4676                        bb->index);
4677                 err = 1;
4678               }
4679           }
4680           break;
4681
4682         case GIMPLE_GOTO:
4683           if (simple_goto_p (stmt))
4684             {
4685               error ("explicit goto at end of bb %d", bb->index);
4686               err = 1;
4687             }
4688           else
4689             {
4690               /* FIXME.  We should double check that the labels in the
4691                  destination blocks have their address taken.  */
4692               FOR_EACH_EDGE (e, ei, bb->succs)
4693                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4694                                  | EDGE_FALSE_VALUE))
4695                     || !(e->flags & EDGE_ABNORMAL))
4696                   {
4697                     error ("wrong outgoing edge flags at end of bb %d",
4698                            bb->index);
4699                     err = 1;
4700                   }
4701             }
4702           break;
4703
4704         case GIMPLE_CALL:
4705           if (!gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
4706             break;
4707           /* ... fallthru ... */
4708         case GIMPLE_RETURN:
4709           if (!single_succ_p (bb)
4710               || (single_succ_edge (bb)->flags
4711                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
4712                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4713             {
4714               error ("wrong outgoing edge flags at end of bb %d", bb->index);
4715               err = 1;
4716             }
4717           if (single_succ (bb) != EXIT_BLOCK_PTR)
4718             {
4719               error ("return edge does not point to exit in bb %d",
4720                      bb->index);
4721               err = 1;
4722             }
4723           break;
4724
4725         case GIMPLE_SWITCH:
4726           {
4727             tree prev;
4728             edge e;
4729             size_t i, n;
4730
4731             n = gimple_switch_num_labels (stmt);
4732
4733             /* Mark all the destination basic blocks.  */
4734             for (i = 0; i < n; ++i)
4735               {
4736                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4737                 basic_block label_bb = label_to_block (lab);
4738                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4739                 label_bb->aux = (void *)1;
4740               }
4741
4742             /* Verify that the case labels are sorted.  */
4743             prev = gimple_switch_label (stmt, 0);
4744             for (i = 1; i < n; ++i)
4745               {
4746                 tree c = gimple_switch_label (stmt, i);
4747                 if (!CASE_LOW (c))
4748                   {
4749                     error ("found default case not at the start of "
4750                            "case vector");
4751                     err = 1;
4752                     continue;
4753                   }
4754                 if (CASE_LOW (prev)
4755                     && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4756                   {
4757                     error ("case labels not sorted: ");
4758                     print_generic_expr (stderr, prev, 0);
4759                     fprintf (stderr," is greater than ");
4760                     print_generic_expr (stderr, c, 0);
4761                     fprintf (stderr," but comes before it.\n");
4762                     err = 1;
4763                   }
4764                 prev = c;
4765               }
4766             /* VRP will remove the default case if it can prove it will
4767                never be executed.  So do not verify there always exists
4768                a default case here.  */
4769
4770             FOR_EACH_EDGE (e, ei, bb->succs)
4771               {
4772                 if (!e->dest->aux)
4773                   {
4774                     error ("extra outgoing edge %d->%d",
4775                            bb->index, e->dest->index);
4776                     err = 1;
4777                   }
4778
4779                 e->dest->aux = (void *)2;
4780                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
4781                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4782                   {
4783                     error ("wrong outgoing edge flags at end of bb %d",
4784                            bb->index);
4785                     err = 1;
4786                   }
4787               }
4788
4789             /* Check that we have all of them.  */
4790             for (i = 0; i < n; ++i)
4791               {
4792                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4793                 basic_block label_bb = label_to_block (lab);
4794
4795                 if (label_bb->aux != (void *)2)
4796                   {
4797                     error ("missing edge %i->%i", bb->index, label_bb->index);
4798                     err = 1;
4799                   }
4800               }
4801
4802             FOR_EACH_EDGE (e, ei, bb->succs)
4803               e->dest->aux = (void *)0;
4804           }
4805           break;
4806
4807         case GIMPLE_EH_DISPATCH:
4808           err |= verify_eh_dispatch_edge (stmt);
4809           break;
4810
4811         default:
4812           break;
4813         }
4814     }
4815
4816   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
4817     verify_dominators (CDI_DOMINATORS);
4818
4819   return err;
4820 }
4821
4822
4823 /* Updates phi nodes after creating a forwarder block joined
4824    by edge FALLTHRU.  */
4825
4826 static void
4827 gimple_make_forwarder_block (edge fallthru)
4828 {
4829   edge e;
4830   edge_iterator ei;
4831   basic_block dummy, bb;
4832   tree var;
4833   gimple_stmt_iterator gsi;
4834
4835   dummy = fallthru->src;
4836   bb = fallthru->dest;
4837
4838   if (single_pred_p (bb))
4839     return;
4840
4841   /* If we redirected a branch we must create new PHI nodes at the
4842      start of BB.  */
4843   for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
4844     {
4845       gimple phi, new_phi;
4846
4847       phi = gsi_stmt (gsi);
4848       var = gimple_phi_result (phi);
4849       new_phi = create_phi_node (var, bb);
4850       SSA_NAME_DEF_STMT (var) = new_phi;
4851       gimple_phi_set_result (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
4852       add_phi_arg (new_phi, gimple_phi_result (phi), fallthru,
4853                    UNKNOWN_LOCATION);
4854     }
4855
4856   /* Add the arguments we have stored on edges.  */
4857   FOR_EACH_EDGE (e, ei, bb->preds)
4858     {
4859       if (e == fallthru)
4860         continue;
4861
4862       flush_pending_stmts (e);
4863     }
4864 }
4865
4866
4867 /* Return a non-special label in the head of basic block BLOCK.
4868    Create one if it doesn't exist.  */
4869
4870 tree
4871 gimple_block_label (basic_block bb)
4872 {
4873   gimple_stmt_iterator i, s = gsi_start_bb (bb);
4874   bool first = true;
4875   tree label;
4876   gimple stmt;
4877
4878   for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
4879     {
4880       stmt = gsi_stmt (i);
4881       if (gimple_code (stmt) != GIMPLE_LABEL)
4882         break;
4883       label = gimple_label_label (stmt);
4884       if (!DECL_NONLOCAL (label))
4885         {
4886           if (!first)
4887             gsi_move_before (&i, &s);
4888           return label;
4889         }
4890     }
4891
4892   label = create_artificial_label (UNKNOWN_LOCATION);
4893   stmt = gimple_build_label (label);
4894   gsi_insert_before (&s, stmt, GSI_NEW_STMT);
4895   return label;
4896 }
4897
4898
4899 /* Attempt to perform edge redirection by replacing a possibly complex
4900    jump instruction by a goto or by removing the jump completely.
4901    This can apply only if all edges now point to the same block.  The
4902    parameters and return values are equivalent to
4903    redirect_edge_and_branch.  */
4904
4905 static edge
4906 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
4907 {
4908   basic_block src = e->src;
4909   gimple_stmt_iterator i;
4910   gimple stmt;
4911
4912   /* We can replace or remove a complex jump only when we have exactly
4913      two edges.  */
4914   if (EDGE_COUNT (src->succs) != 2
4915       /* Verify that all targets will be TARGET.  Specifically, the
4916          edge that is not E must also go to TARGET.  */
4917       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4918     return NULL;
4919
4920   i = gsi_last_bb (src);
4921   if (gsi_end_p (i))
4922     return NULL;
4923
4924   stmt = gsi_stmt (i);
4925
4926   if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
4927     {
4928       gsi_remove (&i, true);
4929       e = ssa_redirect_edge (e, target);
4930       e->flags = EDGE_FALLTHRU;
4931       return e;
4932     }
4933
4934   return NULL;
4935 }
4936
4937
4938 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4939    edge representing the redirected branch.  */
4940
4941 static edge
4942 gimple_redirect_edge_and_branch (edge e, basic_block dest)
4943 {
4944   basic_block bb = e->src;
4945   gimple_stmt_iterator gsi;
4946   edge ret;
4947   gimple stmt;
4948
4949   if (e->flags & EDGE_ABNORMAL)
4950     return NULL;
4951
4952   if (e->dest == dest)
4953     return NULL;
4954
4955   if (e->flags & EDGE_EH)
4956     return redirect_eh_edge (e, dest);
4957
4958   if (e->src != ENTRY_BLOCK_PTR)
4959     {
4960       ret = gimple_try_redirect_by_replacing_jump (e, dest);
4961       if (ret)
4962         return ret;
4963     }
4964
4965   gsi = gsi_last_bb (bb);
4966   stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
4967
4968   switch (stmt ? gimple_code (stmt) : GIMPLE_ERROR_MARK)
4969     {
4970     case GIMPLE_COND:
4971       /* For COND_EXPR, we only need to redirect the edge.  */
4972       break;
4973
4974     case GIMPLE_GOTO:
4975       /* No non-abnormal edges should lead from a non-simple goto, and
4976          simple ones should be represented implicitly.  */
4977       gcc_unreachable ();
4978
4979     case GIMPLE_SWITCH:
4980       {
4981         tree label = gimple_block_label (dest);
4982         tree cases = get_cases_for_edge (e, stmt);
4983
4984         /* If we have a list of cases associated with E, then use it
4985            as it's a lot faster than walking the entire case vector.  */
4986         if (cases)
4987           {
4988             edge e2 = find_edge (e->src, dest);
4989             tree last, first;
4990
4991             first = cases;
4992             while (cases)
4993               {
4994                 last = cases;
4995                 CASE_LABEL (cases) = label;
4996                 cases = CASE_CHAIN (cases);
4997               }
4998
4999             /* If there was already an edge in the CFG, then we need
5000                to move all the cases associated with E to E2.  */
5001             if (e2)
5002               {
5003                 tree cases2 = get_cases_for_edge (e2, stmt);
5004
5005                 CASE_CHAIN (last) = CASE_CHAIN (cases2);
5006                 CASE_CHAIN (cases2) = first;
5007               }
5008             bitmap_set_bit (touched_switch_bbs, gimple_bb (stmt)->index);
5009           }
5010         else
5011           {
5012             size_t i, n = gimple_switch_num_labels (stmt);
5013
5014             for (i = 0; i < n; i++)
5015               {
5016                 tree elt = gimple_switch_label (stmt, i);
5017                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
5018                   CASE_LABEL (elt) = label;
5019               }
5020           }
5021       }
5022       break;
5023
5024     case GIMPLE_ASM:
5025       {
5026         int i, n = gimple_asm_nlabels (stmt);
5027         tree label = NULL;
5028
5029         for (i = 0; i < n; ++i)
5030           {
5031             tree cons = gimple_asm_label_op (stmt, i);
5032             if (label_to_block (TREE_VALUE (cons)) == e->dest)
5033               {
5034                 if (!label)
5035                   label = gimple_block_label (dest);
5036                 TREE_VALUE (cons) = label;
5037               }
5038           }
5039
5040         /* If we didn't find any label matching the former edge in the
5041            asm labels, we must be redirecting the fallthrough
5042            edge.  */
5043         gcc_assert (label || (e->flags & EDGE_FALLTHRU));
5044       }
5045       break;
5046
5047     case GIMPLE_RETURN:
5048       gsi_remove (&gsi, true);
5049       e->flags |= EDGE_FALLTHRU;
5050       break;
5051
5052     case GIMPLE_OMP_RETURN:
5053     case GIMPLE_OMP_CONTINUE:
5054     case GIMPLE_OMP_SECTIONS_SWITCH:
5055     case GIMPLE_OMP_FOR:
5056       /* The edges from OMP constructs can be simply redirected.  */
5057       break;
5058
5059     case GIMPLE_EH_DISPATCH:
5060       if (!(e->flags & EDGE_FALLTHRU))
5061         redirect_eh_dispatch_edge (stmt, e, dest);
5062       break;
5063
5064     default:
5065       /* Otherwise it must be a fallthru edge, and we don't need to
5066          do anything besides redirecting it.  */
5067       gcc_assert (e->flags & EDGE_FALLTHRU);
5068       break;
5069     }
5070
5071   /* Update/insert PHI nodes as necessary.  */
5072
5073   /* Now update the edges in the CFG.  */
5074   e = ssa_redirect_edge (e, dest);
5075
5076   return e;
5077 }
5078
5079 /* Returns true if it is possible to remove edge E by redirecting
5080    it to the destination of the other edge from E->src.  */
5081
5082 static bool
5083 gimple_can_remove_branch_p (const_edge e)
5084 {
5085   if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
5086     return false;
5087
5088   return true;
5089 }
5090
5091 /* Simple wrapper, as we can always redirect fallthru edges.  */
5092
5093 static basic_block
5094 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
5095 {
5096   e = gimple_redirect_edge_and_branch (e, dest);
5097   gcc_assert (e);
5098
5099   return NULL;
5100 }
5101
5102
5103 /* Splits basic block BB after statement STMT (but at least after the
5104    labels).  If STMT is NULL, BB is split just after the labels.  */
5105
5106 static basic_block
5107 gimple_split_block (basic_block bb, void *stmt)
5108 {
5109   gimple_stmt_iterator gsi;
5110   gimple_stmt_iterator gsi_tgt;
5111   gimple act;
5112   gimple_seq list;
5113   basic_block new_bb;
5114   edge e;
5115   edge_iterator ei;
5116
5117   new_bb = create_empty_bb (bb);
5118
5119   /* Redirect the outgoing edges.  */
5120   new_bb->succs = bb->succs;
5121   bb->succs = NULL;
5122   FOR_EACH_EDGE (e, ei, new_bb->succs)
5123     e->src = new_bb;
5124
5125   if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
5126     stmt = NULL;
5127
5128   /* Move everything from GSI to the new basic block.  */
5129   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5130     {
5131       act = gsi_stmt (gsi);
5132       if (gimple_code (act) == GIMPLE_LABEL)
5133         continue;
5134
5135       if (!stmt)
5136         break;
5137
5138       if (stmt == act)
5139         {
5140           gsi_next (&gsi);
5141           break;
5142         }
5143     }
5144
5145   if (gsi_end_p (gsi))
5146     return new_bb;
5147
5148   /* Split the statement list - avoid re-creating new containers as this
5149      brings ugly quadratic memory consumption in the inliner.
5150      (We are still quadratic since we need to update stmt BB pointers,
5151      sadly.)  */
5152   list = gsi_split_seq_before (&gsi);
5153   set_bb_seq (new_bb, list);
5154   for (gsi_tgt = gsi_start (list);
5155        !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
5156     gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
5157
5158   return new_bb;
5159 }
5160
5161
5162 /* Moves basic block BB after block AFTER.  */
5163
5164 static bool
5165 gimple_move_block_after (basic_block bb, basic_block after)
5166 {
5167   if (bb->prev_bb == after)
5168     return true;
5169
5170   unlink_block (bb);
5171   link_block (bb, after);
5172
5173   return true;
5174 }
5175
5176
5177 /* Return true if basic_block can be duplicated.  */
5178
5179 static bool
5180 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5181 {
5182   return true;
5183 }
5184
5185 /* Create a duplicate of the basic block BB.  NOTE: This does not
5186    preserve SSA form.  */
5187
5188 static basic_block
5189 gimple_duplicate_bb (basic_block bb)
5190 {
5191   basic_block new_bb;
5192   gimple_stmt_iterator gsi, gsi_tgt;
5193   gimple_seq phis = phi_nodes (bb);
5194   gimple phi, stmt, copy;
5195
5196   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
5197
5198   /* Copy the PHI nodes.  We ignore PHI node arguments here because
5199      the incoming edges have not been setup yet.  */
5200   for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
5201     {
5202       phi = gsi_stmt (gsi);
5203       copy = create_phi_node (gimple_phi_result (phi), new_bb);
5204       create_new_def_for (gimple_phi_result (copy), copy,
5205                           gimple_phi_result_ptr (copy));
5206     }
5207
5208   gsi_tgt = gsi_start_bb (new_bb);
5209   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5210     {
5211       def_operand_p def_p;
5212       ssa_op_iter op_iter;
5213       tree lhs;
5214
5215       stmt = gsi_stmt (gsi);
5216       if (gimple_code (stmt) == GIMPLE_LABEL)
5217         continue;
5218
5219       /* Don't duplicate label debug stmts.  */
5220       if (gimple_debug_bind_p (stmt)
5221           && TREE_CODE (gimple_debug_bind_get_var (stmt))
5222              == LABEL_DECL)
5223         continue;
5224
5225       /* Create a new copy of STMT and duplicate STMT's virtual
5226          operands.  */
5227       copy = gimple_copy (stmt);
5228       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
5229
5230       maybe_duplicate_eh_stmt (copy, stmt);
5231       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5232
5233       /* When copying around a stmt writing into a local non-user
5234          aggregate, make sure it won't share stack slot with other
5235          vars.  */
5236       lhs = gimple_get_lhs (stmt);
5237       if (lhs && TREE_CODE (lhs) != SSA_NAME)
5238         {
5239           tree base = get_base_address (lhs);
5240           if (base
5241               && (TREE_CODE (base) == VAR_DECL
5242                   || TREE_CODE (base) == RESULT_DECL)
5243               && DECL_IGNORED_P (base)
5244               && !TREE_STATIC (base)
5245               && !DECL_EXTERNAL (base)
5246               && (TREE_CODE (base) != VAR_DECL
5247                   || !DECL_HAS_VALUE_EXPR_P (base)))
5248             DECL_NONSHAREABLE (base) = 1;
5249         }
5250
5251       /* Create new names for all the definitions created by COPY and
5252          add replacement mappings for each new name.  */
5253       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5254         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5255     }
5256
5257   return new_bb;
5258 }
5259
5260 /* Adds phi node arguments for edge E_COPY after basic block duplication.  */
5261
5262 static void
5263 add_phi_args_after_copy_edge (edge e_copy)
5264 {
5265   basic_block bb, bb_copy = e_copy->src, dest;
5266   edge e;
5267   edge_iterator ei;
5268   gimple phi, phi_copy;
5269   tree def;
5270   gimple_stmt_iterator psi, psi_copy;
5271
5272   if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
5273     return;
5274
5275   bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5276
5277   if (e_copy->dest->flags & BB_DUPLICATED)
5278     dest = get_bb_original (e_copy->dest);
5279   else
5280     dest = e_copy->dest;
5281
5282   e = find_edge (bb, dest);
5283   if (!e)
5284     {
5285       /* During loop unrolling the target of the latch edge is copied.
5286          In this case we are not looking for edge to dest, but to
5287          duplicated block whose original was dest.  */
5288       FOR_EACH_EDGE (e, ei, bb->succs)
5289         {
5290           if ((e->dest->flags & BB_DUPLICATED)
5291               && get_bb_original (e->dest) == dest)
5292             break;
5293         }
5294
5295       gcc_assert (e != NULL);
5296     }
5297
5298   for (psi = gsi_start_phis (e->dest),
5299        psi_copy = gsi_start_phis (e_copy->dest);
5300        !gsi_end_p (psi);
5301        gsi_next (&psi), gsi_next (&psi_copy))
5302     {
5303       phi = gsi_stmt (psi);
5304       phi_copy = gsi_stmt (psi_copy);
5305       def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5306       add_phi_arg (phi_copy, def, e_copy,
5307                    gimple_phi_arg_location_from_edge (phi, e));
5308     }
5309 }
5310
5311
5312 /* Basic block BB_COPY was created by code duplication.  Add phi node
5313    arguments for edges going out of BB_COPY.  The blocks that were
5314    duplicated have BB_DUPLICATED set.  */
5315
5316 void
5317 add_phi_args_after_copy_bb (basic_block bb_copy)
5318 {
5319   edge e_copy;
5320   edge_iterator ei;
5321
5322   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5323     {
5324       add_phi_args_after_copy_edge (e_copy);
5325     }
5326 }
5327
5328 /* Blocks in REGION_COPY array of length N_REGION were created by
5329    duplication of basic blocks.  Add phi node arguments for edges
5330    going from these blocks.  If E_COPY is not NULL, also add
5331    phi node arguments for its destination.*/
5332
5333 void
5334 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5335                          edge e_copy)
5336 {
5337   unsigned i;
5338
5339   for (i = 0; i < n_region; i++)
5340     region_copy[i]->flags |= BB_DUPLICATED;
5341
5342   for (i = 0; i < n_region; i++)
5343     add_phi_args_after_copy_bb (region_copy[i]);
5344   if (e_copy)
5345     add_phi_args_after_copy_edge (e_copy);
5346
5347   for (i = 0; i < n_region; i++)
5348     region_copy[i]->flags &= ~BB_DUPLICATED;
5349 }
5350
5351 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5352    important exit edge EXIT.  By important we mean that no SSA name defined
5353    inside region is live over the other exit edges of the region.  All entry
5354    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
5355    to the duplicate of the region.  SSA form, dominance and loop information
5356    is updated.  The new basic blocks are stored to REGION_COPY in the same
5357    order as they had in REGION, provided that REGION_COPY is not NULL.
5358    The function returns false if it is unable to copy the region,
5359    true otherwise.  */
5360
5361 bool
5362 gimple_duplicate_sese_region (edge entry, edge exit,
5363                             basic_block *region, unsigned n_region,
5364                             basic_block *region_copy)
5365 {
5366   unsigned i;
5367   bool free_region_copy = false, copying_header = false;
5368   struct loop *loop = entry->dest->loop_father;
5369   edge exit_copy;
5370   VEC (basic_block, heap) *doms;
5371   edge redirected;
5372   int total_freq = 0, entry_freq = 0;
5373   gcov_type total_count = 0, entry_count = 0;
5374
5375   if (!can_copy_bbs_p (region, n_region))
5376     return false;
5377
5378   /* Some sanity checking.  Note that we do not check for all possible
5379      missuses of the functions.  I.e. if you ask to copy something weird,
5380      it will work, but the state of structures probably will not be
5381      correct.  */
5382   for (i = 0; i < n_region; i++)
5383     {
5384       /* We do not handle subloops, i.e. all the blocks must belong to the
5385          same loop.  */
5386       if (region[i]->loop_father != loop)
5387         return false;
5388
5389       if (region[i] != entry->dest
5390           && region[i] == loop->header)
5391         return false;
5392     }
5393
5394   set_loop_copy (loop, loop);
5395
5396   /* In case the function is used for loop header copying (which is the primary
5397      use), ensure that EXIT and its copy will be new latch and entry edges.  */
5398   if (loop->header == entry->dest)
5399     {
5400       copying_header = true;
5401       set_loop_copy (loop, loop_outer (loop));
5402
5403       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5404         return false;
5405
5406       for (i = 0; i < n_region; i++)
5407         if (region[i] != exit->src
5408             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5409           return false;
5410     }
5411
5412   if (!region_copy)
5413     {
5414       region_copy = XNEWVEC (basic_block, n_region);
5415       free_region_copy = true;
5416     }
5417
5418   gcc_assert (!need_ssa_update_p (cfun));
5419
5420   /* Record blocks outside the region that are dominated by something
5421      inside.  */
5422   doms = NULL;
5423   initialize_original_copy_tables ();
5424
5425   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5426
5427   if (entry->dest->count)
5428     {
5429       total_count = entry->dest->count;
5430       entry_count = entry->count;
5431       /* Fix up corner cases, to avoid division by zero or creation of negative
5432          frequencies.  */
5433       if (entry_count > total_count)
5434         entry_count = total_count;
5435     }
5436   else
5437     {
5438       total_freq = entry->dest->frequency;
5439       entry_freq = EDGE_FREQUENCY (entry);
5440       /* Fix up corner cases, to avoid division by zero or creation of negative
5441          frequencies.  */
5442       if (total_freq == 0)
5443         total_freq = 1;
5444       else if (entry_freq > total_freq)
5445         entry_freq = total_freq;
5446     }
5447
5448   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5449             split_edge_bb_loc (entry));
5450   if (total_count)
5451     {
5452       scale_bbs_frequencies_gcov_type (region, n_region,
5453                                        total_count - entry_count,
5454                                        total_count);
5455       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5456                                        total_count);
5457     }
5458   else
5459     {
5460       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5461                                  total_freq);
5462       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5463     }
5464
5465   if (copying_header)
5466     {
5467       loop->header = exit->dest;
5468       loop->latch = exit->src;
5469     }
5470
5471   /* Redirect the entry and add the phi node arguments.  */
5472   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5473   gcc_assert (redirected != NULL);
5474   flush_pending_stmts (entry);
5475
5476   /* Concerning updating of dominators:  We must recount dominators
5477      for entry block and its copy.  Anything that is outside of the
5478      region, but was dominated by something inside needs recounting as
5479      well.  */
5480   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5481   VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
5482   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5483   VEC_free (basic_block, heap, doms);
5484
5485   /* Add the other PHI node arguments.  */
5486   add_phi_args_after_copy (region_copy, n_region, NULL);
5487
5488   /* Update the SSA web.  */
5489   update_ssa (TODO_update_ssa);
5490
5491   if (free_region_copy)
5492     free (region_copy);
5493
5494   free_original_copy_tables ();
5495   return true;
5496 }
5497
5498 /* Duplicates REGION consisting of N_REGION blocks.  The new blocks
5499    are stored to REGION_COPY in the same order in that they appear
5500    in REGION, if REGION_COPY is not NULL.  ENTRY is the entry to
5501    the region, EXIT an exit from it.  The condition guarding EXIT
5502    is moved to ENTRY.  Returns true if duplication succeeds, false
5503    otherwise.
5504
5505    For example,
5506
5507    some_code;
5508    if (cond)
5509      A;
5510    else
5511      B;
5512
5513    is transformed to
5514
5515    if (cond)
5516      {
5517        some_code;
5518        A;
5519      }
5520    else
5521      {
5522        some_code;
5523        B;
5524      }
5525 */
5526
5527 bool
5528 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
5529                           basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
5530                           basic_block *region_copy ATTRIBUTE_UNUSED)
5531 {
5532   unsigned i;
5533   bool free_region_copy = false;
5534   struct loop *loop = exit->dest->loop_father;
5535   struct loop *orig_loop = entry->dest->loop_father;
5536   basic_block switch_bb, entry_bb, nentry_bb;
5537   VEC (basic_block, heap) *doms;
5538   int total_freq = 0, exit_freq = 0;
5539   gcov_type total_count = 0, exit_count = 0;
5540   edge exits[2], nexits[2], e;
5541   gimple_stmt_iterator gsi;
5542   gimple cond_stmt;
5543   edge sorig, snew;
5544   basic_block exit_bb;
5545   gimple_stmt_iterator psi;
5546   gimple phi;
5547   tree def;
5548
5549   gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5550   exits[0] = exit;
5551   exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5552
5553   if (!can_copy_bbs_p (region, n_region))
5554     return false;
5555
5556   initialize_original_copy_tables ();
5557   set_loop_copy (orig_loop, loop);
5558   duplicate_subloops (orig_loop, loop);
5559
5560   if (!region_copy)
5561     {
5562       region_copy = XNEWVEC (basic_block, n_region);
5563       free_region_copy = true;
5564     }
5565
5566   gcc_assert (!need_ssa_update_p (cfun));
5567
5568   /* Record blocks outside the region that are dominated by something
5569      inside.  */
5570   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5571
5572   if (exit->src->count)
5573     {
5574       total_count = exit->src->count;
5575       exit_count = exit->count;
5576       /* Fix up corner cases, to avoid division by zero or creation of negative
5577          frequencies.  */
5578       if (exit_count > total_count)
5579         exit_count = total_count;
5580     }
5581   else
5582     {
5583       total_freq = exit->src->frequency;
5584       exit_freq = EDGE_FREQUENCY (exit);
5585       /* Fix up corner cases, to avoid division by zero or creation of negative
5586          frequencies.  */
5587       if (total_freq == 0)
5588         total_freq = 1;
5589       if (exit_freq > total_freq)
5590         exit_freq = total_freq;
5591     }
5592
5593   copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5594             split_edge_bb_loc (exit));
5595   if (total_count)
5596     {
5597       scale_bbs_frequencies_gcov_type (region, n_region,
5598                                        total_count - exit_count,
5599                                        total_count);
5600       scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5601                                        total_count);
5602     }
5603   else
5604     {
5605       scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5606                                  total_freq);
5607       scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5608     }
5609
5610   /* Create the switch block, and put the exit condition to it.  */
5611   entry_bb = entry->dest;
5612   nentry_bb = get_bb_copy (entry_bb);
5613   if (!last_stmt (entry->src)
5614       || !stmt_ends_bb_p (last_stmt (entry->src)))
5615     switch_bb = entry->src;
5616   else
5617     switch_bb = split_edge (entry);
5618   set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5619
5620   gsi = gsi_last_bb (switch_bb);
5621   cond_stmt = last_stmt (exit->src);
5622   gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
5623   cond_stmt = gimple_copy (cond_stmt);
5624
5625   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
5626
5627   sorig = single_succ_edge (switch_bb);
5628   sorig->flags = exits[1]->flags;
5629   snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5630
5631   /* Register the new edge from SWITCH_BB in loop exit lists.  */
5632   rescan_loop_exit (snew, true, false);
5633
5634   /* Add the PHI node arguments.  */
5635   add_phi_args_after_copy (region_copy, n_region, snew);
5636
5637   /* Get rid of now superfluous conditions and associated edges (and phi node
5638      arguments).  */
5639   exit_bb = exit->dest;
5640
5641   e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5642   PENDING_STMT (e) = NULL;
5643
5644   /* The latch of ORIG_LOOP was copied, and so was the backedge
5645      to the original header.  We redirect this backedge to EXIT_BB.  */
5646   for (i = 0; i < n_region; i++)
5647     if (get_bb_original (region_copy[i]) == orig_loop->latch)
5648       {
5649         gcc_assert (single_succ_edge (region_copy[i]));
5650         e = redirect_edge_and_branch (single_succ_edge (region_copy[i]), exit_bb);
5651         PENDING_STMT (e) = NULL;
5652         for (psi = gsi_start_phis (exit_bb);
5653              !gsi_end_p (psi);
5654              gsi_next (&psi))
5655           {
5656             phi = gsi_stmt (psi);
5657             def = PHI_ARG_DEF (phi, nexits[0]->dest_idx);
5658             add_phi_arg (phi, def, e, gimple_phi_arg_location_from_edge (phi, e));
5659           }
5660       }
5661   e = redirect_edge_and_branch (nexits[0], nexits[1]->dest);
5662   PENDING_STMT (e) = NULL;
5663
5664   /* Anything that is outside of the region, but was dominated by something
5665      inside needs to update dominance info.  */
5666   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5667   VEC_free (basic_block, heap, doms);
5668   /* Update the SSA web.  */
5669   update_ssa (TODO_update_ssa);
5670
5671   if (free_region_copy)
5672     free (region_copy);
5673
5674   free_original_copy_tables ();
5675   return true;
5676 }
5677
5678 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
5679    adding blocks when the dominator traversal reaches EXIT.  This
5680    function silently assumes that ENTRY strictly dominates EXIT.  */
5681
5682 void
5683 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5684                               VEC(basic_block,heap) **bbs_p)
5685 {
5686   basic_block son;
5687
5688   for (son = first_dom_son (CDI_DOMINATORS, entry);
5689        son;
5690        son = next_dom_son (CDI_DOMINATORS, son))
5691     {
5692       VEC_safe_push (basic_block, heap, *bbs_p, son);
5693       if (son != exit)
5694         gather_blocks_in_sese_region (son, exit, bbs_p);
5695     }
5696 }
5697
5698 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5699    The duplicates are recorded in VARS_MAP.  */
5700
5701 static void
5702 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5703                            tree to_context)
5704 {
5705   tree t = *tp, new_t;
5706   struct function *f = DECL_STRUCT_FUNCTION (to_context);
5707   void **loc;
5708
5709   if (DECL_CONTEXT (t) == to_context)
5710     return;
5711
5712   loc = pointer_map_contains (vars_map, t);
5713
5714   if (!loc)
5715     {
5716       loc = pointer_map_insert (vars_map, t);
5717
5718       if (SSA_VAR_P (t))
5719         {
5720           new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5721           add_local_decl (f, new_t);
5722         }
5723       else
5724         {
5725           gcc_assert (TREE_CODE (t) == CONST_DECL);
5726           new_t = copy_node (t);
5727         }
5728       DECL_CONTEXT (new_t) = to_context;
5729
5730       *loc = new_t;
5731     }
5732   else
5733     new_t = (tree) *loc;
5734
5735   *tp = new_t;
5736 }
5737
5738
5739 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5740    VARS_MAP maps old ssa names and var_decls to the new ones.  */
5741
5742 static tree
5743 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5744                   tree to_context)
5745 {
5746   void **loc;
5747   tree new_name, decl = SSA_NAME_VAR (name);
5748
5749   gcc_assert (is_gimple_reg (name));
5750
5751   loc = pointer_map_contains (vars_map, name);
5752
5753   if (!loc)
5754     {
5755       replace_by_duplicate_decl (&decl, vars_map, to_context);
5756
5757       push_cfun (DECL_STRUCT_FUNCTION (to_context));
5758       if (gimple_in_ssa_p (cfun))
5759         add_referenced_var (decl);
5760
5761       new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5762       if (SSA_NAME_IS_DEFAULT_DEF (name))
5763         set_default_def (decl, new_name);
5764       pop_cfun ();
5765
5766       loc = pointer_map_insert (vars_map, name);
5767       *loc = new_name;
5768     }
5769   else
5770     new_name = (tree) *loc;
5771
5772   return new_name;
5773 }
5774
5775 struct move_stmt_d
5776 {
5777   tree orig_block;
5778   tree new_block;
5779   tree from_context;
5780   tree to_context;
5781   struct pointer_map_t *vars_map;
5782   htab_t new_label_map;
5783   struct pointer_map_t *eh_map;
5784   bool remap_decls_p;
5785 };
5786
5787 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
5788    contained in *TP if it has been ORIG_BLOCK previously and change the
5789    DECL_CONTEXT of every local variable referenced in *TP.  */
5790
5791 static tree
5792 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
5793 {
5794   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
5795   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5796   tree t = *tp;
5797
5798   if (EXPR_P (t))
5799     /* We should never have TREE_BLOCK set on non-statements.  */
5800     gcc_assert (!TREE_BLOCK (t));
5801
5802   else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
5803     {
5804       if (TREE_CODE (t) == SSA_NAME)
5805         *tp = replace_ssa_name (t, p->vars_map, p->to_context);
5806       else if (TREE_CODE (t) == LABEL_DECL)
5807         {
5808           if (p->new_label_map)
5809             {
5810               struct tree_map in, *out;
5811               in.base.from = t;
5812               out = (struct tree_map *)
5813                 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
5814               if (out)
5815                 *tp = t = out->to;
5816             }
5817
5818           DECL_CONTEXT (t) = p->to_context;
5819         }
5820       else if (p->remap_decls_p)
5821         {
5822           /* Replace T with its duplicate.  T should no longer appear in the
5823              parent function, so this looks wasteful; however, it may appear
5824              in referenced_vars, and more importantly, as virtual operands of
5825              statements, and in alias lists of other variables.  It would be
5826              quite difficult to expunge it from all those places.  ??? It might
5827              suffice to do this for addressable variables.  */
5828           if ((TREE_CODE (t) == VAR_DECL
5829                && !is_global_var (t))
5830               || TREE_CODE (t) == CONST_DECL)
5831             replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
5832
5833           if (SSA_VAR_P (t)
5834               && gimple_in_ssa_p (cfun))
5835             {
5836               push_cfun (DECL_STRUCT_FUNCTION (p->to_context));
5837               add_referenced_var (*tp);
5838               pop_cfun ();
5839             }
5840         }
5841       *walk_subtrees = 0;
5842     }
5843   else if (TYPE_P (t))
5844     *walk_subtrees = 0;
5845
5846   return NULL_TREE;
5847 }
5848
5849 /* Helper for move_stmt_r.  Given an EH region number for the source
5850    function, map that to the duplicate EH regio number in the dest.  */
5851
5852 static int
5853 move_stmt_eh_region_nr (int old_nr, struct move_stmt_d *p)
5854 {
5855   eh_region old_r, new_r;
5856   void **slot;
5857
5858   old_r = get_eh_region_from_number (old_nr);
5859   slot = pointer_map_contains (p->eh_map, old_r);
5860   new_r = (eh_region) *slot;
5861
5862   return new_r->index;
5863 }
5864
5865 /* Similar, but operate on INTEGER_CSTs.  */
5866
5867 static tree
5868 move_stmt_eh_region_tree_nr (tree old_t_nr, struct move_stmt_d *p)
5869 {
5870   int old_nr, new_nr;
5871
5872   old_nr = tree_low_cst (old_t_nr, 0);
5873   new_nr = move_stmt_eh_region_nr (old_nr, p);
5874
5875   return build_int_cst (integer_type_node, new_nr);
5876 }
5877
5878 /* Like move_stmt_op, but for gimple statements.
5879
5880    Helper for move_block_to_fn.  Set GIMPLE_BLOCK in every expression
5881    contained in the current statement in *GSI_P and change the
5882    DECL_CONTEXT of every local variable referenced in the current
5883    statement.  */
5884
5885 static tree
5886 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
5887              struct walk_stmt_info *wi)
5888 {
5889   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5890   gimple stmt = gsi_stmt (*gsi_p);
5891   tree block = gimple_block (stmt);
5892
5893   if (p->orig_block == NULL_TREE
5894       || block == p->orig_block
5895       || block == NULL_TREE)
5896     gimple_set_block (stmt, p->new_block);
5897 #ifdef ENABLE_CHECKING
5898   else if (block != p->new_block)
5899     {
5900       while (block && block != p->orig_block)
5901         block = BLOCK_SUPERCONTEXT (block);
5902       gcc_assert (block);
5903     }
5904 #endif
5905
5906   switch (gimple_code (stmt))
5907     {
5908     case GIMPLE_CALL:
5909       /* Remap the region numbers for __builtin_eh_{pointer,filter}.  */
5910       {
5911         tree r, fndecl = gimple_call_fndecl (stmt);
5912         if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
5913           switch (DECL_FUNCTION_CODE (fndecl))
5914             {
5915             case BUILT_IN_EH_COPY_VALUES:
5916               r = gimple_call_arg (stmt, 1);
5917               r = move_stmt_eh_region_tree_nr (r, p);
5918               gimple_call_set_arg (stmt, 1, r);
5919               /* FALLTHRU */
5920
5921             case BUILT_IN_EH_POINTER:
5922             case BUILT_IN_EH_FILTER:
5923               r = gimple_call_arg (stmt, 0);
5924               r = move_stmt_eh_region_tree_nr (r, p);
5925               gimple_call_set_arg (stmt, 0, r);
5926               break;
5927
5928             default:
5929               break;
5930             }
5931       }
5932       break;
5933
5934     case GIMPLE_RESX:
5935       {
5936         int r = gimple_resx_region (stmt);
5937         r = move_stmt_eh_region_nr (r, p);
5938         gimple_resx_set_region (stmt, r);
5939       }
5940       break;
5941
5942     case GIMPLE_EH_DISPATCH:
5943       {
5944         int r = gimple_eh_dispatch_region (stmt);
5945         r = move_stmt_eh_region_nr (r, p);
5946         gimple_eh_dispatch_set_region (stmt, r);
5947       }
5948       break;
5949
5950     case GIMPLE_OMP_RETURN:
5951     case GIMPLE_OMP_CONTINUE:
5952       break;
5953     default:
5954       if (is_gimple_omp (stmt))
5955         {
5956           /* Do not remap variables inside OMP directives.  Variables
5957              referenced in clauses and directive header belong to the
5958              parent function and should not be moved into the child
5959              function.  */
5960           bool save_remap_decls_p = p->remap_decls_p;
5961           p->remap_decls_p = false;
5962           *handled_ops_p = true;
5963
5964           walk_gimple_seq (gimple_omp_body (stmt), move_stmt_r,
5965                            move_stmt_op, wi);
5966
5967           p->remap_decls_p = save_remap_decls_p;
5968         }
5969       break;
5970     }
5971
5972   return NULL_TREE;
5973 }
5974
5975 /* Move basic block BB from function CFUN to function DEST_FN.  The
5976    block is moved out of the original linked list and placed after
5977    block AFTER in the new list.  Also, the block is removed from the
5978    original array of blocks and placed in DEST_FN's array of blocks.
5979    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
5980    updated to reflect the moved edges.
5981
5982    The local variables are remapped to new instances, VARS_MAP is used
5983    to record the mapping.  */
5984
5985 static void
5986 move_block_to_fn (struct function *dest_cfun, basic_block bb,
5987                   basic_block after, bool update_edge_count_p,
5988                   struct move_stmt_d *d)
5989 {
5990   struct control_flow_graph *cfg;
5991   edge_iterator ei;
5992   edge e;
5993   gimple_stmt_iterator si;
5994   unsigned old_len, new_len;
5995
5996   /* Remove BB from dominance structures.  */
5997   delete_from_dominance_info (CDI_DOMINATORS, bb);
5998   if (current_loops)
5999     remove_bb_from_loops (bb);
6000
6001   /* Link BB to the new linked list.  */
6002   move_block_after (bb, after);
6003
6004   /* Update the edge count in the corresponding flowgraphs.  */
6005   if (update_edge_count_p)
6006     FOR_EACH_EDGE (e, ei, bb->succs)
6007       {
6008         cfun->cfg->x_n_edges--;
6009         dest_cfun->cfg->x_n_edges++;
6010       }
6011
6012   /* Remove BB from the original basic block array.  */
6013   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
6014   cfun->cfg->x_n_basic_blocks--;
6015
6016   /* Grow DEST_CFUN's basic block array if needed.  */
6017   cfg = dest_cfun->cfg;
6018   cfg->x_n_basic_blocks++;
6019   if (bb->index >= cfg->x_last_basic_block)
6020     cfg->x_last_basic_block = bb->index + 1;
6021
6022   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
6023   if ((unsigned) cfg->x_last_basic_block >= old_len)
6024     {
6025       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
6026       VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
6027                              new_len);
6028     }
6029
6030   VEC_replace (basic_block, cfg->x_basic_block_info,
6031                bb->index, bb);
6032
6033   /* Remap the variables in phi nodes.  */
6034   for (si = gsi_start_phis (bb); !gsi_end_p (si); )
6035     {
6036       gimple phi = gsi_stmt (si);
6037       use_operand_p use;
6038       tree op = PHI_RESULT (phi);
6039       ssa_op_iter oi;
6040
6041       if (!is_gimple_reg (op))
6042         {
6043           /* Remove the phi nodes for virtual operands (alias analysis will be
6044              run for the new function, anyway).  */
6045           remove_phi_node (&si, true);
6046           continue;
6047         }
6048
6049       SET_PHI_RESULT (phi,
6050                       replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6051       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
6052         {
6053           op = USE_FROM_PTR (use);
6054           if (TREE_CODE (op) == SSA_NAME)
6055             SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6056         }
6057
6058       gsi_next (&si);
6059     }
6060
6061   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6062     {
6063       gimple stmt = gsi_stmt (si);
6064       struct walk_stmt_info wi;
6065
6066       memset (&wi, 0, sizeof (wi));
6067       wi.info = d;
6068       walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
6069
6070       if (gimple_code (stmt) == GIMPLE_LABEL)
6071         {
6072           tree label = gimple_label_label (stmt);
6073           int uid = LABEL_DECL_UID (label);
6074
6075           gcc_assert (uid > -1);
6076
6077           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
6078           if (old_len <= (unsigned) uid)
6079             {
6080               new_len = 3 * uid / 2 + 1;
6081               VEC_safe_grow_cleared (basic_block, gc,
6082                                      cfg->x_label_to_block_map, new_len);
6083             }
6084
6085           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
6086           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
6087
6088           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
6089
6090           if (uid >= dest_cfun->cfg->last_label_uid)
6091             dest_cfun->cfg->last_label_uid = uid + 1;
6092         }
6093
6094       maybe_duplicate_eh_stmt_fn (dest_cfun, stmt, cfun, stmt, d->eh_map, 0);
6095       remove_stmt_from_eh_lp_fn (cfun, stmt);
6096
6097       gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
6098       gimple_remove_stmt_histograms (cfun, stmt);
6099
6100       /* We cannot leave any operands allocated from the operand caches of
6101          the current function.  */
6102       free_stmt_operands (stmt);
6103       push_cfun (dest_cfun);
6104       update_stmt (stmt);
6105       pop_cfun ();
6106     }
6107
6108   FOR_EACH_EDGE (e, ei, bb->succs)
6109     if (e->goto_locus)
6110       {
6111         tree block = e->goto_block;
6112         if (d->orig_block == NULL_TREE
6113             || block == d->orig_block)
6114           e->goto_block = d->new_block;
6115 #ifdef ENABLE_CHECKING
6116         else if (block != d->new_block)
6117           {
6118             while (block && block != d->orig_block)
6119               block = BLOCK_SUPERCONTEXT (block);
6120             gcc_assert (block);
6121           }
6122 #endif
6123       }
6124 }
6125
6126 /* Examine the statements in BB (which is in SRC_CFUN); find and return
6127    the outermost EH region.  Use REGION as the incoming base EH region.  */
6128
6129 static eh_region
6130 find_outermost_region_in_block (struct function *src_cfun,
6131                                 basic_block bb, eh_region region)
6132 {
6133   gimple_stmt_iterator si;
6134
6135   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6136     {
6137       gimple stmt = gsi_stmt (si);
6138       eh_region stmt_region;
6139       int lp_nr;
6140
6141       lp_nr = lookup_stmt_eh_lp_fn (src_cfun, stmt);
6142       stmt_region = get_eh_region_from_lp_number_fn (src_cfun, lp_nr);
6143       if (stmt_region)
6144         {
6145           if (region == NULL)
6146             region = stmt_region;
6147           else if (stmt_region != region)
6148             {
6149               region = eh_region_outermost (src_cfun, stmt_region, region);
6150               gcc_assert (region != NULL);
6151             }
6152         }
6153     }
6154
6155   return region;
6156 }
6157
6158 static tree
6159 new_label_mapper (tree decl, void *data)
6160 {
6161   htab_t hash = (htab_t) data;
6162   struct tree_map *m;
6163   void **slot;
6164
6165   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
6166
6167   m = XNEW (struct tree_map);
6168   m->hash = DECL_UID (decl);
6169   m->base.from = decl;
6170   m->to = create_artificial_label (UNKNOWN_LOCATION);
6171   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
6172   if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
6173     cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
6174
6175   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
6176   gcc_assert (*slot == NULL);
6177
6178   *slot = m;
6179
6180   return m->to;
6181 }
6182
6183 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
6184    subblocks.  */
6185
6186 static void
6187 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map,
6188                                   tree to_context)
6189 {
6190   tree *tp, t;
6191
6192   for (tp = &BLOCK_VARS (block); *tp; tp = &DECL_CHAIN (*tp))
6193     {
6194       t = *tp;
6195       if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL)
6196         continue;
6197       replace_by_duplicate_decl (&t, vars_map, to_context);
6198       if (t != *tp)
6199         {
6200           if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
6201             {
6202               SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
6203               DECL_HAS_VALUE_EXPR_P (t) = 1;
6204             }
6205           DECL_CHAIN (t) = DECL_CHAIN (*tp);
6206           *tp = t;
6207         }
6208     }
6209
6210   for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
6211     replace_block_vars_by_duplicates (block, vars_map, to_context);
6212 }
6213
6214 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
6215    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
6216    single basic block in the original CFG and the new basic block is
6217    returned.  DEST_CFUN must not have a CFG yet.
6218
6219    Note that the region need not be a pure SESE region.  Blocks inside
6220    the region may contain calls to abort/exit.  The only restriction
6221    is that ENTRY_BB should be the only entry point and it must
6222    dominate EXIT_BB.
6223
6224    Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
6225    functions outermost BLOCK, move all subblocks of ORIG_BLOCK
6226    to the new function.
6227
6228    All local variables referenced in the region are assumed to be in
6229    the corresponding BLOCK_VARS and unexpanded variable lists
6230    associated with DEST_CFUN.  */
6231
6232 basic_block
6233 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
6234                         basic_block exit_bb, tree orig_block)
6235 {
6236   VEC(basic_block,heap) *bbs, *dom_bbs;
6237   basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
6238   basic_block after, bb, *entry_pred, *exit_succ, abb;
6239   struct function *saved_cfun = cfun;
6240   int *entry_flag, *exit_flag;
6241   unsigned *entry_prob, *exit_prob;
6242   unsigned i, num_entry_edges, num_exit_edges;
6243   edge e;
6244   edge_iterator ei;
6245   htab_t new_label_map;
6246   struct pointer_map_t *vars_map, *eh_map;
6247   struct loop *loop = entry_bb->loop_father;
6248   struct move_stmt_d d;
6249
6250   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
6251      region.  */
6252   gcc_assert (entry_bb != exit_bb
6253               && (!exit_bb
6254                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
6255
6256   /* Collect all the blocks in the region.  Manually add ENTRY_BB
6257      because it won't be added by dfs_enumerate_from.  */
6258   bbs = NULL;
6259   VEC_safe_push (basic_block, heap, bbs, entry_bb);
6260   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
6261
6262   /* The blocks that used to be dominated by something in BBS will now be
6263      dominated by the new block.  */
6264   dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
6265                                      VEC_address (basic_block, bbs),
6266                                      VEC_length (basic_block, bbs));
6267
6268   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
6269      the predecessor edges to ENTRY_BB and the successor edges to
6270      EXIT_BB so that we can re-attach them to the new basic block that
6271      will replace the region.  */
6272   num_entry_edges = EDGE_COUNT (entry_bb->preds);
6273   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
6274   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
6275   entry_prob = XNEWVEC (unsigned, num_entry_edges);
6276   i = 0;
6277   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
6278     {
6279       entry_prob[i] = e->probability;
6280       entry_flag[i] = e->flags;
6281       entry_pred[i++] = e->src;
6282       remove_edge (e);
6283     }
6284
6285   if (exit_bb)
6286     {
6287       num_exit_edges = EDGE_COUNT (exit_bb->succs);
6288       exit_succ = (basic_block *) xcalloc (num_exit_edges,
6289                                            sizeof (basic_block));
6290       exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
6291       exit_prob = XNEWVEC (unsigned, num_exit_edges);
6292       i = 0;
6293       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6294         {
6295           exit_prob[i] = e->probability;
6296           exit_flag[i] = e->flags;
6297           exit_succ[i++] = e->dest;
6298           remove_edge (e);
6299         }
6300     }
6301   else
6302     {
6303       num_exit_edges = 0;
6304       exit_succ = NULL;
6305       exit_flag = NULL;
6306       exit_prob = NULL;
6307     }
6308
6309   /* Switch context to the child function to initialize DEST_FN's CFG.  */
6310   gcc_assert (dest_cfun->cfg == NULL);
6311   push_cfun (dest_cfun);
6312
6313   init_empty_tree_cfg ();
6314
6315   /* Initialize EH information for the new function.  */
6316   eh_map = NULL;
6317   new_label_map = NULL;
6318   if (saved_cfun->eh)
6319     {
6320       eh_region region = NULL;
6321
6322       FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
6323         region = find_outermost_region_in_block (saved_cfun, bb, region);
6324
6325       init_eh_for_function ();
6326       if (region != NULL)
6327         {
6328           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6329           eh_map = duplicate_eh_regions (saved_cfun, region, 0,
6330                                          new_label_mapper, new_label_map);
6331         }
6332     }
6333
6334   pop_cfun ();
6335
6336   /* Move blocks from BBS into DEST_CFUN.  */
6337   gcc_assert (VEC_length (basic_block, bbs) >= 2);
6338   after = dest_cfun->cfg->x_entry_block_ptr;
6339   vars_map = pointer_map_create ();
6340
6341   memset (&d, 0, sizeof (d));
6342   d.orig_block = orig_block;
6343   d.new_block = DECL_INITIAL (dest_cfun->decl);
6344   d.from_context = cfun->decl;
6345   d.to_context = dest_cfun->decl;
6346   d.vars_map = vars_map;
6347   d.new_label_map = new_label_map;
6348   d.eh_map = eh_map;
6349   d.remap_decls_p = true;
6350
6351   FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
6352     {
6353       /* No need to update edge counts on the last block.  It has
6354          already been updated earlier when we detached the region from
6355          the original CFG.  */
6356       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d);
6357       after = bb;
6358     }
6359
6360   /* Rewire BLOCK_SUBBLOCKS of orig_block.  */
6361   if (orig_block)
6362     {
6363       tree block;
6364       gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6365                   == NULL_TREE);
6366       BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6367         = BLOCK_SUBBLOCKS (orig_block);
6368       for (block = BLOCK_SUBBLOCKS (orig_block);
6369            block; block = BLOCK_CHAIN (block))
6370         BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
6371       BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
6372     }
6373
6374   replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
6375                                     vars_map, dest_cfun->decl);
6376
6377   if (new_label_map)
6378     htab_delete (new_label_map);
6379   if (eh_map)
6380     pointer_map_destroy (eh_map);
6381   pointer_map_destroy (vars_map);
6382
6383   /* Rewire the entry and exit blocks.  The successor to the entry
6384      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6385      the child function.  Similarly, the predecessor of DEST_FN's
6386      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
6387      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6388      various CFG manipulation function get to the right CFG.
6389
6390      FIXME, this is silly.  The CFG ought to become a parameter to
6391      these helpers.  */
6392   push_cfun (dest_cfun);
6393   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6394   if (exit_bb)
6395     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
6396   pop_cfun ();
6397
6398   /* Back in the original function, the SESE region has disappeared,
6399      create a new basic block in its place.  */
6400   bb = create_empty_bb (entry_pred[0]);
6401   if (current_loops)
6402     add_bb_to_loop (bb, loop);
6403   for (i = 0; i < num_entry_edges; i++)
6404     {
6405       e = make_edge (entry_pred[i], bb, entry_flag[i]);
6406       e->probability = entry_prob[i];
6407     }
6408
6409   for (i = 0; i < num_exit_edges; i++)
6410     {
6411       e = make_edge (bb, exit_succ[i], exit_flag[i]);
6412       e->probability = exit_prob[i];
6413     }
6414
6415   set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6416   FOR_EACH_VEC_ELT (basic_block, dom_bbs, i, abb)
6417     set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6418   VEC_free (basic_block, heap, dom_bbs);
6419
6420   if (exit_bb)
6421     {
6422       free (exit_prob);
6423       free (exit_flag);
6424       free (exit_succ);
6425     }
6426   free (entry_prob);
6427   free (entry_flag);
6428   free (entry_pred);
6429   VEC_free (basic_block, heap, bbs);
6430
6431   return bb;
6432 }
6433
6434
6435 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree-pass.h)
6436    */
6437
6438 void
6439 dump_function_to_file (tree fn, FILE *file, int flags)
6440 {
6441   tree arg, var;
6442   struct function *dsf;
6443   bool ignore_topmost_bind = false, any_var = false;
6444   basic_block bb;
6445   tree chain;
6446
6447   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
6448
6449   arg = DECL_ARGUMENTS (fn);
6450   while (arg)
6451     {
6452       print_generic_expr (file, TREE_TYPE (arg), dump_flags);
6453       fprintf (file, " ");
6454       print_generic_expr (file, arg, dump_flags);
6455       if (flags & TDF_VERBOSE)
6456         print_node (file, "", arg, 4);
6457       if (DECL_CHAIN (arg))
6458         fprintf (file, ", ");
6459       arg = DECL_CHAIN (arg);
6460     }
6461   fprintf (file, ")\n");
6462
6463   if (flags & TDF_VERBOSE)
6464     print_node (file, "", fn, 2);
6465
6466   dsf = DECL_STRUCT_FUNCTION (fn);
6467   if (dsf && (flags & TDF_EH))
6468     dump_eh_tree (file, dsf);
6469
6470   if (flags & TDF_RAW && !gimple_has_body_p (fn))
6471     {
6472       dump_node (fn, TDF_SLIM | flags, file);
6473       return;
6474     }
6475
6476   /* Switch CFUN to point to FN.  */
6477   push_cfun (DECL_STRUCT_FUNCTION (fn));
6478
6479   /* When GIMPLE is lowered, the variables are no longer available in
6480      BIND_EXPRs, so display them separately.  */
6481   if (cfun && cfun->decl == fn && !VEC_empty (tree, cfun->local_decls))
6482     {
6483       unsigned ix;
6484       ignore_topmost_bind = true;
6485
6486       fprintf (file, "{\n");
6487       FOR_EACH_LOCAL_DECL (cfun, ix, var)
6488         {
6489           print_generic_decl (file, var, flags);
6490           if (flags & TDF_VERBOSE)
6491             print_node (file, "", var, 4);
6492           fprintf (file, "\n");
6493
6494           any_var = true;
6495         }
6496     }
6497
6498   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
6499     {
6500       /* If the CFG has been built, emit a CFG-based dump.  */
6501       check_bb_profile (ENTRY_BLOCK_PTR, file);
6502       if (!ignore_topmost_bind)
6503         fprintf (file, "{\n");
6504
6505       if (any_var && n_basic_blocks)
6506         fprintf (file, "\n");
6507
6508       FOR_EACH_BB (bb)
6509         gimple_dump_bb (bb, file, 2, flags);
6510
6511       fprintf (file, "}\n");
6512       check_bb_profile (EXIT_BLOCK_PTR, file);
6513     }
6514   else if (DECL_SAVED_TREE (fn) == NULL)
6515     {
6516       /* The function is now in GIMPLE form but the CFG has not been
6517          built yet.  Emit the single sequence of GIMPLE statements
6518          that make up its body.  */
6519       gimple_seq body = gimple_body (fn);
6520
6521       if (gimple_seq_first_stmt (body)
6522           && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
6523           && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
6524         print_gimple_seq (file, body, 0, flags);
6525       else
6526         {
6527           if (!ignore_topmost_bind)
6528             fprintf (file, "{\n");
6529
6530           if (any_var)
6531             fprintf (file, "\n");
6532
6533           print_gimple_seq (file, body, 2, flags);
6534           fprintf (file, "}\n");
6535         }
6536     }
6537   else
6538     {
6539       int indent;
6540
6541       /* Make a tree based dump.  */
6542       chain = DECL_SAVED_TREE (fn);
6543
6544       if (chain && TREE_CODE (chain) == BIND_EXPR)
6545         {
6546           if (ignore_topmost_bind)
6547             {
6548               chain = BIND_EXPR_BODY (chain);
6549               indent = 2;
6550             }
6551           else
6552             indent = 0;
6553         }
6554       else
6555         {
6556           if (!ignore_topmost_bind)
6557             fprintf (file, "{\n");
6558           indent = 2;
6559         }
6560
6561       if (any_var)
6562         fprintf (file, "\n");
6563
6564       print_generic_stmt_indented (file, chain, flags, indent);
6565       if (ignore_topmost_bind)
6566         fprintf (file, "}\n");
6567     }
6568
6569   if (flags & TDF_ENUMERATE_LOCALS)
6570     dump_enumerated_decls (file, flags);
6571   fprintf (file, "\n\n");
6572
6573   /* Restore CFUN.  */
6574   pop_cfun ();
6575 }
6576
6577
6578 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
6579
6580 DEBUG_FUNCTION void
6581 debug_function (tree fn, int flags)
6582 {
6583   dump_function_to_file (fn, stderr, flags);
6584 }
6585
6586
6587 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
6588
6589 static void
6590 print_pred_bbs (FILE *file, basic_block bb)
6591 {
6592   edge e;
6593   edge_iterator ei;
6594
6595   FOR_EACH_EDGE (e, ei, bb->preds)
6596     fprintf (file, "bb_%d ", e->src->index);
6597 }
6598
6599
6600 /* Print on FILE the indexes for the successors of basic_block BB.  */
6601
6602 static void
6603 print_succ_bbs (FILE *file, basic_block bb)
6604 {
6605   edge e;
6606   edge_iterator ei;
6607
6608   FOR_EACH_EDGE (e, ei, bb->succs)
6609     fprintf (file, "bb_%d ", e->dest->index);
6610 }
6611
6612 /* Print to FILE the basic block BB following the VERBOSITY level.  */
6613
6614 void
6615 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6616 {
6617   char *s_indent = (char *) alloca ((size_t) indent + 1);
6618   memset ((void *) s_indent, ' ', (size_t) indent);
6619   s_indent[indent] = '\0';
6620
6621   /* Print basic_block's header.  */
6622   if (verbosity >= 2)
6623     {
6624       fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
6625       print_pred_bbs (file, bb);
6626       fprintf (file, "}, succs = {");
6627       print_succ_bbs (file, bb);
6628       fprintf (file, "})\n");
6629     }
6630
6631   /* Print basic_block's body.  */
6632   if (verbosity >= 3)
6633     {
6634       fprintf (file, "%s  {\n", s_indent);
6635       gimple_dump_bb (bb, file, indent + 4, TDF_VOPS|TDF_MEMSYMS);
6636       fprintf (file, "%s  }\n", s_indent);
6637     }
6638 }
6639
6640 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6641
6642 /* Pretty print LOOP on FILE, indented INDENT spaces.  Following
6643    VERBOSITY level this outputs the contents of the loop, or just its
6644    structure.  */
6645
6646 static void
6647 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6648 {
6649   char *s_indent;
6650   basic_block bb;
6651
6652   if (loop == NULL)
6653     return;
6654
6655   s_indent = (char *) alloca ((size_t) indent + 1);
6656   memset ((void *) s_indent, ' ', (size_t) indent);
6657   s_indent[indent] = '\0';
6658
6659   /* Print loop's header.  */
6660   fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent,
6661            loop->num, loop->header->index, loop->latch->index);
6662   fprintf (file, ", niter = ");
6663   print_generic_expr (file, loop->nb_iterations, 0);
6664
6665   if (loop->any_upper_bound)
6666     {
6667       fprintf (file, ", upper_bound = ");
6668       dump_double_int (file, loop->nb_iterations_upper_bound, true);
6669     }
6670
6671   if (loop->any_estimate)
6672     {
6673       fprintf (file, ", estimate = ");
6674       dump_double_int (file, loop->nb_iterations_estimate, true);
6675     }
6676   fprintf (file, ")\n");
6677
6678   /* Print loop's body.  */
6679   if (verbosity >= 1)
6680     {
6681       fprintf (file, "%s{\n", s_indent);
6682       FOR_EACH_BB (bb)
6683         if (bb->loop_father == loop)
6684           print_loops_bb (file, bb, indent, verbosity);
6685
6686       print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
6687       fprintf (file, "%s}\n", s_indent);
6688     }
6689 }
6690
6691 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6692    spaces.  Following VERBOSITY level this outputs the contents of the
6693    loop, or just its structure.  */
6694
6695 static void
6696 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
6697 {
6698   if (loop == NULL)
6699     return;
6700
6701   print_loop (file, loop, indent, verbosity);
6702   print_loop_and_siblings (file, loop->next, indent, verbosity);
6703 }
6704
6705 /* Follow a CFG edge from the entry point of the program, and on entry
6706    of a loop, pretty print the loop structure on FILE.  */
6707
6708 void
6709 print_loops (FILE *file, int verbosity)
6710 {
6711   basic_block bb;
6712
6713   bb = ENTRY_BLOCK_PTR;
6714   if (bb && bb->loop_father)
6715     print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
6716 }
6717
6718
6719 /* Debugging loops structure at tree level, at some VERBOSITY level.  */
6720
6721 DEBUG_FUNCTION void
6722 debug_loops (int verbosity)
6723 {
6724   print_loops (stderr, verbosity);
6725 }
6726
6727 /* Print on stderr the code of LOOP, at some VERBOSITY level.  */
6728
6729 DEBUG_FUNCTION void
6730 debug_loop (struct loop *loop, int verbosity)
6731 {
6732   print_loop (stderr, loop, 0, verbosity);
6733 }
6734
6735 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6736    level.  */
6737
6738 DEBUG_FUNCTION void
6739 debug_loop_num (unsigned num, int verbosity)
6740 {
6741   debug_loop (get_loop (num), verbosity);
6742 }
6743
6744 /* Return true if BB ends with a call, possibly followed by some
6745    instructions that must stay with the call.  Return false,
6746    otherwise.  */
6747
6748 static bool
6749 gimple_block_ends_with_call_p (basic_block bb)
6750 {
6751   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
6752   return !gsi_end_p (gsi) && is_gimple_call (gsi_stmt (gsi));
6753 }
6754
6755
6756 /* Return true if BB ends with a conditional branch.  Return false,
6757    otherwise.  */
6758
6759 static bool
6760 gimple_block_ends_with_condjump_p (const_basic_block bb)
6761 {
6762   gimple stmt = last_stmt (CONST_CAST_BB (bb));
6763   return (stmt && gimple_code (stmt) == GIMPLE_COND);
6764 }
6765
6766
6767 /* Return true if we need to add fake edge to exit at statement T.
6768    Helper function for gimple_flow_call_edges_add.  */
6769
6770 static bool
6771 need_fake_edge_p (gimple t)
6772 {
6773   tree fndecl = NULL_TREE;
6774   int call_flags = 0;
6775
6776   /* NORETURN and LONGJMP calls already have an edge to exit.
6777      CONST and PURE calls do not need one.
6778      We don't currently check for CONST and PURE here, although
6779      it would be a good idea, because those attributes are
6780      figured out from the RTL in mark_constant_function, and
6781      the counter incrementation code from -fprofile-arcs
6782      leads to different results from -fbranch-probabilities.  */
6783   if (is_gimple_call (t))
6784     {
6785       fndecl = gimple_call_fndecl (t);
6786       call_flags = gimple_call_flags (t);
6787     }
6788
6789   if (is_gimple_call (t)
6790       && fndecl
6791       && DECL_BUILT_IN (fndecl)
6792       && (call_flags & ECF_NOTHROW)
6793       && !(call_flags & ECF_RETURNS_TWICE)
6794       /* fork() doesn't really return twice, but the effect of
6795          wrapping it in __gcov_fork() which calls __gcov_flush()
6796          and clears the counters before forking has the same
6797          effect as returning twice.  Force a fake edge.  */
6798       && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
6799            && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK))
6800     return false;
6801
6802   if (is_gimple_call (t)
6803       && !(call_flags & ECF_NORETURN))
6804     return true;
6805
6806   if (gimple_code (t) == GIMPLE_ASM
6807        && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
6808     return true;
6809
6810   return false;
6811 }
6812
6813
6814 /* Add fake edges to the function exit for any non constant and non
6815    noreturn calls, volatile inline assembly in the bitmap of blocks
6816    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
6817    the number of blocks that were split.
6818
6819    The goal is to expose cases in which entering a basic block does
6820    not imply that all subsequent instructions must be executed.  */
6821
6822 static int
6823 gimple_flow_call_edges_add (sbitmap blocks)
6824 {
6825   int i;
6826   int blocks_split = 0;
6827   int last_bb = last_basic_block;
6828   bool check_last_block = false;
6829
6830   if (n_basic_blocks == NUM_FIXED_BLOCKS)
6831     return 0;
6832
6833   if (! blocks)
6834     check_last_block = true;
6835   else
6836     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
6837
6838   /* In the last basic block, before epilogue generation, there will be
6839      a fallthru edge to EXIT.  Special care is required if the last insn
6840      of the last basic block is a call because make_edge folds duplicate
6841      edges, which would result in the fallthru edge also being marked
6842      fake, which would result in the fallthru edge being removed by
6843      remove_fake_edges, which would result in an invalid CFG.
6844
6845      Moreover, we can't elide the outgoing fake edge, since the block
6846      profiler needs to take this into account in order to solve the minimal
6847      spanning tree in the case that the call doesn't return.
6848
6849      Handle this by adding a dummy instruction in a new last basic block.  */
6850   if (check_last_block)
6851     {
6852       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
6853       gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
6854       gimple t = NULL;
6855
6856       if (!gsi_end_p (gsi))
6857         t = gsi_stmt (gsi);
6858
6859       if (t && need_fake_edge_p (t))
6860         {
6861           edge e;
6862
6863           e = find_edge (bb, EXIT_BLOCK_PTR);
6864           if (e)
6865             {
6866               gsi_insert_on_edge (e, gimple_build_nop ());
6867               gsi_commit_edge_inserts ();
6868             }
6869         }
6870     }
6871
6872   /* Now add fake edges to the function exit for any non constant
6873      calls since there is no way that we can determine if they will
6874      return or not...  */
6875   for (i = 0; i < last_bb; i++)
6876     {
6877       basic_block bb = BASIC_BLOCK (i);
6878       gimple_stmt_iterator gsi;
6879       gimple stmt, last_stmt;
6880
6881       if (!bb)
6882         continue;
6883
6884       if (blocks && !TEST_BIT (blocks, i))
6885         continue;
6886
6887       gsi = gsi_last_nondebug_bb (bb);
6888       if (!gsi_end_p (gsi))
6889         {
6890           last_stmt = gsi_stmt (gsi);
6891           do
6892             {
6893               stmt = gsi_stmt (gsi);
6894               if (need_fake_edge_p (stmt))
6895                 {
6896                   edge e;
6897
6898                   /* The handling above of the final block before the
6899                      epilogue should be enough to verify that there is
6900                      no edge to the exit block in CFG already.
6901                      Calling make_edge in such case would cause us to
6902                      mark that edge as fake and remove it later.  */
6903 #ifdef ENABLE_CHECKING
6904                   if (stmt == last_stmt)
6905                     {
6906                       e = find_edge (bb, EXIT_BLOCK_PTR);
6907                       gcc_assert (e == NULL);
6908                     }
6909 #endif
6910
6911                   /* Note that the following may create a new basic block
6912                      and renumber the existing basic blocks.  */
6913                   if (stmt != last_stmt)
6914                     {
6915                       e = split_block (bb, stmt);
6916                       if (e)
6917                         blocks_split++;
6918                     }
6919                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
6920                 }
6921               gsi_prev (&gsi);
6922             }
6923           while (!gsi_end_p (gsi));
6924         }
6925     }
6926
6927   if (blocks_split)
6928     verify_flow_info ();
6929
6930   return blocks_split;
6931 }
6932
6933 /* Removes edge E and all the blocks dominated by it, and updates dominance
6934    information.  The IL in E->src needs to be updated separately.
6935    If dominance info is not available, only the edge E is removed.*/
6936
6937 void
6938 remove_edge_and_dominated_blocks (edge e)
6939 {
6940   VEC (basic_block, heap) *bbs_to_remove = NULL;
6941   VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
6942   bitmap df, df_idom;
6943   edge f;
6944   edge_iterator ei;
6945   bool none_removed = false;
6946   unsigned i;
6947   basic_block bb, dbb;
6948   bitmap_iterator bi;
6949
6950   if (!dom_info_available_p (CDI_DOMINATORS))
6951     {
6952       remove_edge (e);
6953       return;
6954     }
6955
6956   /* No updating is needed for edges to exit.  */
6957   if (e->dest == EXIT_BLOCK_PTR)
6958     {
6959       if (cfgcleanup_altered_bbs)
6960         bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6961       remove_edge (e);
6962       return;
6963     }
6964
6965   /* First, we find the basic blocks to remove.  If E->dest has a predecessor
6966      that is not dominated by E->dest, then this set is empty.  Otherwise,
6967      all the basic blocks dominated by E->dest are removed.
6968
6969      Also, to DF_IDOM we store the immediate dominators of the blocks in
6970      the dominance frontier of E (i.e., of the successors of the
6971      removed blocks, if there are any, and of E->dest otherwise).  */
6972   FOR_EACH_EDGE (f, ei, e->dest->preds)
6973     {
6974       if (f == e)
6975         continue;
6976
6977       if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
6978         {
6979           none_removed = true;
6980           break;
6981         }
6982     }
6983
6984   df = BITMAP_ALLOC (NULL);
6985   df_idom = BITMAP_ALLOC (NULL);
6986
6987   if (none_removed)
6988     bitmap_set_bit (df_idom,
6989                     get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
6990   else
6991     {
6992       bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest);
6993       FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb)
6994         {
6995           FOR_EACH_EDGE (f, ei, bb->succs)
6996             {
6997               if (f->dest != EXIT_BLOCK_PTR)
6998                 bitmap_set_bit (df, f->dest->index);
6999             }
7000         }
7001       FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb)
7002         bitmap_clear_bit (df, bb->index);
7003
7004       EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
7005         {
7006           bb = BASIC_BLOCK (i);
7007           bitmap_set_bit (df_idom,
7008                           get_immediate_dominator (CDI_DOMINATORS, bb)->index);
7009         }
7010     }
7011
7012   if (cfgcleanup_altered_bbs)
7013     {
7014       /* Record the set of the altered basic blocks.  */
7015       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7016       bitmap_ior_into (cfgcleanup_altered_bbs, df);
7017     }
7018
7019   /* Remove E and the cancelled blocks.  */
7020   if (none_removed)
7021     remove_edge (e);
7022   else
7023     {
7024       /* Walk backwards so as to get a chance to substitute all
7025          released DEFs into debug stmts.  See
7026          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
7027          details.  */
7028       for (i = VEC_length (basic_block, bbs_to_remove); i-- > 0; )
7029         delete_basic_block (VEC_index (basic_block, bbs_to_remove, i));
7030     }
7031
7032   /* Update the dominance information.  The immediate dominator may change only
7033      for blocks whose immediate dominator belongs to DF_IDOM:
7034
7035      Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
7036      removal.  Let Z the arbitrary block such that idom(Z) = Y and
7037      Z dominates X after the removal.  Before removal, there exists a path P
7038      from Y to X that avoids Z.  Let F be the last edge on P that is
7039      removed, and let W = F->dest.  Before removal, idom(W) = Y (since Y
7040      dominates W, and because of P, Z does not dominate W), and W belongs to
7041      the dominance frontier of E.  Therefore, Y belongs to DF_IDOM.  */
7042   EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
7043     {
7044       bb = BASIC_BLOCK (i);
7045       for (dbb = first_dom_son (CDI_DOMINATORS, bb);
7046            dbb;
7047            dbb = next_dom_son (CDI_DOMINATORS, dbb))
7048         VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
7049     }
7050
7051   iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
7052
7053   BITMAP_FREE (df);
7054   BITMAP_FREE (df_idom);
7055   VEC_free (basic_block, heap, bbs_to_remove);
7056   VEC_free (basic_block, heap, bbs_to_fix_dom);
7057 }
7058
7059 /* Purge dead EH edges from basic block BB.  */
7060
7061 bool
7062 gimple_purge_dead_eh_edges (basic_block bb)
7063 {
7064   bool changed = false;
7065   edge e;
7066   edge_iterator ei;
7067   gimple stmt = last_stmt (bb);
7068
7069   if (stmt && stmt_can_throw_internal (stmt))
7070     return false;
7071
7072   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7073     {
7074       if (e->flags & EDGE_EH)
7075         {
7076           remove_edge_and_dominated_blocks (e);
7077           changed = true;
7078         }
7079       else
7080         ei_next (&ei);
7081     }
7082
7083   return changed;
7084 }
7085
7086 /* Purge dead EH edges from basic block listed in BLOCKS.  */
7087
7088 bool
7089 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
7090 {
7091   bool changed = false;
7092   unsigned i;
7093   bitmap_iterator bi;
7094
7095   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7096     {
7097       basic_block bb = BASIC_BLOCK (i);
7098
7099       /* Earlier gimple_purge_dead_eh_edges could have removed
7100          this basic block already.  */
7101       gcc_assert (bb || changed);
7102       if (bb != NULL)
7103         changed |= gimple_purge_dead_eh_edges (bb);
7104     }
7105
7106   return changed;
7107 }
7108
7109 /* Purge dead abnormal call edges from basic block BB.  */
7110
7111 bool
7112 gimple_purge_dead_abnormal_call_edges (basic_block bb)
7113 {
7114   bool changed = false;
7115   edge e;
7116   edge_iterator ei;
7117   gimple stmt = last_stmt (bb);
7118
7119   if (!cfun->has_nonlocal_label)
7120     return false;
7121
7122   if (stmt && stmt_can_make_abnormal_goto (stmt))
7123     return false;
7124
7125   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7126     {
7127       if (e->flags & EDGE_ABNORMAL)
7128         {
7129           remove_edge_and_dominated_blocks (e);
7130           changed = true;
7131         }
7132       else
7133         ei_next (&ei);
7134     }
7135
7136   return changed;
7137 }
7138
7139 /* Purge dead abnormal call edges from basic block listed in BLOCKS.  */
7140
7141 bool
7142 gimple_purge_all_dead_abnormal_call_edges (const_bitmap blocks)
7143 {
7144   bool changed = false;
7145   unsigned i;
7146   bitmap_iterator bi;
7147
7148   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7149     {
7150       basic_block bb = BASIC_BLOCK (i);
7151
7152       /* Earlier gimple_purge_dead_abnormal_call_edges could have removed
7153          this basic block already.  */
7154       gcc_assert (bb || changed);
7155       if (bb != NULL)
7156         changed |= gimple_purge_dead_abnormal_call_edges (bb);
7157     }
7158
7159   return changed;
7160 }
7161
7162 /* This function is called whenever a new edge is created or
7163    redirected.  */
7164
7165 static void
7166 gimple_execute_on_growing_pred (edge e)
7167 {
7168   basic_block bb = e->dest;
7169
7170   if (!gimple_seq_empty_p (phi_nodes (bb)))
7171     reserve_phi_args_for_new_edge (bb);
7172 }
7173
7174 /* This function is called immediately before edge E is removed from
7175    the edge vector E->dest->preds.  */
7176
7177 static void
7178 gimple_execute_on_shrinking_pred (edge e)
7179 {
7180   if (!gimple_seq_empty_p (phi_nodes (e->dest)))
7181     remove_phi_args (e);
7182 }
7183
7184 /*---------------------------------------------------------------------------
7185   Helper functions for Loop versioning
7186   ---------------------------------------------------------------------------*/
7187
7188 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
7189    of 'first'. Both of them are dominated by 'new_head' basic block. When
7190    'new_head' was created by 'second's incoming edge it received phi arguments
7191    on the edge by split_edge(). Later, additional edge 'e' was created to
7192    connect 'new_head' and 'first'. Now this routine adds phi args on this
7193    additional edge 'e' that new_head to second edge received as part of edge
7194    splitting.  */
7195
7196 static void
7197 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
7198                                   basic_block new_head, edge e)
7199 {
7200   gimple phi1, phi2;
7201   gimple_stmt_iterator psi1, psi2;
7202   tree def;
7203   edge e2 = find_edge (new_head, second);
7204
7205   /* Because NEW_HEAD has been created by splitting SECOND's incoming
7206      edge, we should always have an edge from NEW_HEAD to SECOND.  */
7207   gcc_assert (e2 != NULL);
7208
7209   /* Browse all 'second' basic block phi nodes and add phi args to
7210      edge 'e' for 'first' head. PHI args are always in correct order.  */
7211
7212   for (psi2 = gsi_start_phis (second),
7213        psi1 = gsi_start_phis (first);
7214        !gsi_end_p (psi2) && !gsi_end_p (psi1);
7215        gsi_next (&psi2),  gsi_next (&psi1))
7216     {
7217       phi1 = gsi_stmt (psi1);
7218       phi2 = gsi_stmt (psi2);
7219       def = PHI_ARG_DEF (phi2, e2->dest_idx);
7220       add_phi_arg (phi1, def, e, gimple_phi_arg_location_from_edge (phi2, e2));
7221     }
7222 }
7223
7224
7225 /* Adds a if else statement to COND_BB with condition COND_EXPR.
7226    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
7227    the destination of the ELSE part.  */
7228
7229 static void
7230 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
7231                                basic_block second_head ATTRIBUTE_UNUSED,
7232                                basic_block cond_bb, void *cond_e)
7233 {
7234   gimple_stmt_iterator gsi;
7235   gimple new_cond_expr;
7236   tree cond_expr = (tree) cond_e;
7237   edge e0;
7238
7239   /* Build new conditional expr */
7240   new_cond_expr = gimple_build_cond_from_tree (cond_expr,
7241                                                NULL_TREE, NULL_TREE);
7242
7243   /* Add new cond in cond_bb.  */
7244   gsi = gsi_last_bb (cond_bb);
7245   gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
7246
7247   /* Adjust edges appropriately to connect new head with first head
7248      as well as second head.  */
7249   e0 = single_succ_edge (cond_bb);
7250   e0->flags &= ~EDGE_FALLTHRU;
7251   e0->flags |= EDGE_FALSE_VALUE;
7252 }
7253
7254 struct cfg_hooks gimple_cfg_hooks = {
7255   "gimple",
7256   gimple_verify_flow_info,
7257   gimple_dump_bb,               /* dump_bb  */
7258   create_bb,                    /* create_basic_block  */
7259   gimple_redirect_edge_and_branch, /* redirect_edge_and_branch  */
7260   gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force  */
7261   gimple_can_remove_branch_p,   /* can_remove_branch_p  */
7262   remove_bb,                    /* delete_basic_block  */
7263   gimple_split_block,           /* split_block  */
7264   gimple_move_block_after,      /* move_block_after  */
7265   gimple_can_merge_blocks_p,    /* can_merge_blocks_p  */
7266   gimple_merge_blocks,          /* merge_blocks  */
7267   gimple_predict_edge,          /* predict_edge  */
7268   gimple_predicted_by_p,        /* predicted_by_p  */
7269   gimple_can_duplicate_bb_p,    /* can_duplicate_block_p  */
7270   gimple_duplicate_bb,          /* duplicate_block  */
7271   gimple_split_edge,            /* split_edge  */
7272   gimple_make_forwarder_block,  /* make_forward_block  */
7273   NULL,                         /* tidy_fallthru_edge  */
7274   NULL,                         /* force_nonfallthru */
7275   gimple_block_ends_with_call_p,/* block_ends_with_call_p */
7276   gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
7277   gimple_flow_call_edges_add,   /* flow_call_edges_add */
7278   gimple_execute_on_growing_pred,       /* execute_on_growing_pred */
7279   gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
7280   gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
7281   gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
7282   gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
7283   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
7284   flush_pending_stmts           /* flush_pending_stmts */
7285 };
7286
7287
7288 /* Split all critical edges.  */
7289
7290 static unsigned int
7291 split_critical_edges (void)
7292 {
7293   basic_block bb;
7294   edge e;
7295   edge_iterator ei;
7296
7297   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
7298      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
7299      mappings around the calls to split_edge.  */
7300   start_recording_case_labels ();
7301   FOR_ALL_BB (bb)
7302     {
7303       FOR_EACH_EDGE (e, ei, bb->succs)
7304         {
7305           if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
7306             split_edge (e);
7307           /* PRE inserts statements to edges and expects that
7308              since split_critical_edges was done beforehand, committing edge
7309              insertions will not split more edges.  In addition to critical
7310              edges we must split edges that have multiple successors and
7311              end by control flow statements, such as RESX.
7312              Go ahead and split them too.  This matches the logic in
7313              gimple_find_edge_insert_loc.  */
7314           else if ((!single_pred_p (e->dest)
7315                     || !gimple_seq_empty_p (phi_nodes (e->dest))
7316                     || e->dest == EXIT_BLOCK_PTR)
7317                    && e->src != ENTRY_BLOCK_PTR
7318                    && !(e->flags & EDGE_ABNORMAL))
7319             {
7320               gimple_stmt_iterator gsi;
7321
7322               gsi = gsi_last_bb (e->src);
7323               if (!gsi_end_p (gsi)
7324                   && stmt_ends_bb_p (gsi_stmt (gsi))
7325                   && (gimple_code (gsi_stmt (gsi)) != GIMPLE_RETURN
7326                       && !gimple_call_builtin_p (gsi_stmt (gsi),
7327                                                  BUILT_IN_RETURN)))
7328                 split_edge (e);
7329             }
7330         }
7331     }
7332   end_recording_case_labels ();
7333   return 0;
7334 }
7335
7336 struct gimple_opt_pass pass_split_crit_edges =
7337 {
7338  {
7339   GIMPLE_PASS,
7340   "crited",                          /* name */
7341   NULL,                          /* gate */
7342   split_critical_edges,          /* execute */
7343   NULL,                          /* sub */
7344   NULL,                          /* next */
7345   0,                             /* static_pass_number */
7346   TV_TREE_SPLIT_EDGES,           /* tv_id */
7347   PROP_cfg,                      /* properties required */
7348   PROP_no_crit_edges,            /* properties_provided */
7349   0,                             /* properties_destroyed */
7350   0,                             /* todo_flags_start */
7351   TODO_verify_flow               /* todo_flags_finish */
7352  }
7353 };
7354
7355
7356 /* Build a ternary operation and gimplify it.  Emit code before GSI.
7357    Return the gimple_val holding the result.  */
7358
7359 tree
7360 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
7361                  tree type, tree a, tree b, tree c)
7362 {
7363   tree ret;
7364   location_t loc = gimple_location (gsi_stmt (*gsi));
7365
7366   ret = fold_build3_loc (loc, code, type, a, b, c);
7367   STRIP_NOPS (ret);
7368
7369   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7370                                    GSI_SAME_STMT);
7371 }
7372
7373 /* Build a binary operation and gimplify it.  Emit code before GSI.
7374    Return the gimple_val holding the result.  */
7375
7376 tree
7377 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
7378                  tree type, tree a, tree b)
7379 {
7380   tree ret;
7381
7382   ret = fold_build2_loc (gimple_location (gsi_stmt (*gsi)), code, type, a, b);
7383   STRIP_NOPS (ret);
7384
7385   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7386                                    GSI_SAME_STMT);
7387 }
7388
7389 /* Build a unary operation and gimplify it.  Emit code before GSI.
7390    Return the gimple_val holding the result.  */
7391
7392 tree
7393 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
7394                  tree a)
7395 {
7396   tree ret;
7397
7398   ret = fold_build1_loc (gimple_location (gsi_stmt (*gsi)), code, type, a);
7399   STRIP_NOPS (ret);
7400
7401   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7402                                    GSI_SAME_STMT);
7403 }
7404
7405
7406 \f
7407 /* Emit return warnings.  */
7408
7409 static unsigned int
7410 execute_warn_function_return (void)
7411 {
7412   source_location location;
7413   gimple last;
7414   edge e;
7415   edge_iterator ei;
7416
7417   /* If we have a path to EXIT, then we do return.  */
7418   if (TREE_THIS_VOLATILE (cfun->decl)
7419       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
7420     {
7421       location = UNKNOWN_LOCATION;
7422       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7423         {
7424           last = last_stmt (e->src);
7425           if ((gimple_code (last) == GIMPLE_RETURN
7426                || gimple_call_builtin_p (last, BUILT_IN_RETURN))
7427               && (location = gimple_location (last)) != UNKNOWN_LOCATION)
7428             break;
7429         }
7430       if (location == UNKNOWN_LOCATION)
7431         location = cfun->function_end_locus;
7432       warning_at (location, 0, "%<noreturn%> function does return");
7433     }
7434
7435   /* If we see "return;" in some basic block, then we do reach the end
7436      without returning a value.  */
7437   else if (warn_return_type
7438            && !TREE_NO_WARNING (cfun->decl)
7439            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
7440            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
7441     {
7442       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7443         {
7444           gimple last = last_stmt (e->src);
7445           if (gimple_code (last) == GIMPLE_RETURN
7446               && gimple_return_retval (last) == NULL
7447               && !gimple_no_warning_p (last))
7448             {
7449               location = gimple_location (last);
7450               if (location == UNKNOWN_LOCATION)
7451                   location = cfun->function_end_locus;
7452               warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
7453               TREE_NO_WARNING (cfun->decl) = 1;
7454               break;
7455             }
7456         }
7457     }
7458   return 0;
7459 }
7460
7461
7462 /* Given a basic block B which ends with a conditional and has
7463    precisely two successors, determine which of the edges is taken if
7464    the conditional is true and which is taken if the conditional is
7465    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
7466
7467 void
7468 extract_true_false_edges_from_block (basic_block b,
7469                                      edge *true_edge,
7470                                      edge *false_edge)
7471 {
7472   edge e = EDGE_SUCC (b, 0);
7473
7474   if (e->flags & EDGE_TRUE_VALUE)
7475     {
7476       *true_edge = e;
7477       *false_edge = EDGE_SUCC (b, 1);
7478     }
7479   else
7480     {
7481       *false_edge = e;
7482       *true_edge = EDGE_SUCC (b, 1);
7483     }
7484 }
7485
7486 struct gimple_opt_pass pass_warn_function_return =
7487 {
7488  {
7489   GIMPLE_PASS,
7490   "*warn_function_return",              /* name */
7491   NULL,                                 /* gate */
7492   execute_warn_function_return,         /* execute */
7493   NULL,                                 /* sub */
7494   NULL,                                 /* next */
7495   0,                                    /* static_pass_number */
7496   TV_NONE,                              /* tv_id */
7497   PROP_cfg,                             /* properties_required */
7498   0,                                    /* properties_provided */
7499   0,                                    /* properties_destroyed */
7500   0,                                    /* todo_flags_start */
7501   0                                     /* todo_flags_finish */
7502  }
7503 };
7504
7505 /* Emit noreturn warnings.  */
7506
7507 static unsigned int
7508 execute_warn_function_noreturn (void)
7509 {
7510   if (!TREE_THIS_VOLATILE (current_function_decl)
7511       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0)
7512     warn_function_noreturn (current_function_decl);
7513   return 0;
7514 }
7515
7516 static bool
7517 gate_warn_function_noreturn (void)
7518 {
7519   return warn_suggest_attribute_noreturn;
7520 }
7521
7522 struct gimple_opt_pass pass_warn_function_noreturn =
7523 {
7524  {
7525   GIMPLE_PASS,
7526   "*warn_function_noreturn",            /* name */
7527   gate_warn_function_noreturn,          /* gate */
7528   execute_warn_function_noreturn,       /* execute */
7529   NULL,                                 /* sub */
7530   NULL,                                 /* next */
7531   0,                                    /* static_pass_number */
7532   TV_NONE,                              /* tv_id */
7533   PROP_cfg,                             /* properties_required */
7534   0,                                    /* properties_provided */
7535   0,                                    /* properties_destroyed */
7536   0,                                    /* todo_flags_start */
7537   0                                     /* todo_flags_finish */
7538  }
7539 };
7540
7541
7542 /* Walk a gimplified function and warn for functions whose return value is
7543    ignored and attribute((warn_unused_result)) is set.  This is done before
7544    inlining, so we don't have to worry about that.  */
7545
7546 static void
7547 do_warn_unused_result (gimple_seq seq)
7548 {
7549   tree fdecl, ftype;
7550   gimple_stmt_iterator i;
7551
7552   for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
7553     {
7554       gimple g = gsi_stmt (i);
7555
7556       switch (gimple_code (g))
7557         {
7558         case GIMPLE_BIND:
7559           do_warn_unused_result (gimple_bind_body (g));
7560           break;
7561         case GIMPLE_TRY:
7562           do_warn_unused_result (gimple_try_eval (g));
7563           do_warn_unused_result (gimple_try_cleanup (g));
7564           break;
7565         case GIMPLE_CATCH:
7566           do_warn_unused_result (gimple_catch_handler (g));
7567           break;
7568         case GIMPLE_EH_FILTER:
7569           do_warn_unused_result (gimple_eh_filter_failure (g));
7570           break;
7571
7572         case GIMPLE_CALL:
7573           if (gimple_call_lhs (g))
7574             break;
7575           if (gimple_call_internal_p (g))
7576             break;
7577
7578           /* This is a naked call, as opposed to a GIMPLE_CALL with an
7579              LHS.  All calls whose value is ignored should be
7580              represented like this.  Look for the attribute.  */
7581           fdecl = gimple_call_fndecl (g);
7582           ftype = gimple_call_fntype (g);
7583
7584           if (lookup_attribute ("warn_unused_result", TYPE_ATTRIBUTES (ftype)))
7585             {
7586               location_t loc = gimple_location (g);
7587
7588               if (fdecl)
7589                 warning_at (loc, OPT_Wunused_result,
7590                             "ignoring return value of %qD, "
7591                             "declared with attribute warn_unused_result",
7592                             fdecl);
7593               else
7594                 warning_at (loc, OPT_Wunused_result,
7595                             "ignoring return value of function "
7596                             "declared with attribute warn_unused_result");
7597             }
7598           break;
7599
7600         default:
7601           /* Not a container, not a call, or a call whose value is used.  */
7602           break;
7603         }
7604     }
7605 }
7606
7607 static unsigned int
7608 run_warn_unused_result (void)
7609 {
7610   do_warn_unused_result (gimple_body (current_function_decl));
7611   return 0;
7612 }
7613
7614 static bool
7615 gate_warn_unused_result (void)
7616 {
7617   return flag_warn_unused_result;
7618 }
7619
7620 struct gimple_opt_pass pass_warn_unused_result =
7621 {
7622   {
7623     GIMPLE_PASS,
7624     "*warn_unused_result",              /* name */
7625     gate_warn_unused_result,            /* gate */
7626     run_warn_unused_result,             /* execute */
7627     NULL,                               /* sub */
7628     NULL,                               /* next */
7629     0,                                  /* static_pass_number */
7630     TV_NONE,                            /* tv_id */
7631     PROP_gimple_any,                    /* properties_required */
7632     0,                                  /* properties_provided */
7633     0,                                  /* properties_destroyed */
7634     0,                                  /* todo_flags_start */
7635     0,                                  /* todo_flags_finish */
7636   }
7637 };