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 labels.  */
1458       if (!DECL_ARTIFICIAL (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
1705           lp_nr = EH_LANDING_PAD_NR (label);
1706           if (lp_nr)
1707             {
1708               eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1709               lp->post_landing_pad = NULL;
1710             }
1711         }
1712       else
1713         {
1714           gimple_set_bb (stmt, a);
1715           gsi_next (&gsi);
1716         }
1717     }
1718
1719   /* Merge the sequences.  */
1720   last = gsi_last_bb (a);
1721   gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1722   set_bb_seq (b, NULL);
1723
1724   if (cfgcleanup_altered_bbs)
1725     bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1726 }
1727
1728
1729 /* Return the one of two successors of BB that is not reachable by a
1730    complex edge, if there is one.  Else, return BB.  We use
1731    this in optimizations that use post-dominators for their heuristics,
1732    to catch the cases in C++ where function calls are involved.  */
1733
1734 basic_block
1735 single_noncomplex_succ (basic_block bb)
1736 {
1737   edge e0, e1;
1738   if (EDGE_COUNT (bb->succs) != 2)
1739     return bb;
1740
1741   e0 = EDGE_SUCC (bb, 0);
1742   e1 = EDGE_SUCC (bb, 1);
1743   if (e0->flags & EDGE_COMPLEX)
1744     return e1->dest;
1745   if (e1->flags & EDGE_COMPLEX)
1746     return e0->dest;
1747
1748   return bb;
1749 }
1750
1751 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1752
1753 void
1754 notice_special_calls (gimple call)
1755 {
1756   int flags = gimple_call_flags (call);
1757
1758   if (flags & ECF_MAY_BE_ALLOCA)
1759     cfun->calls_alloca = true;
1760   if (flags & ECF_RETURNS_TWICE)
1761     cfun->calls_setjmp = true;
1762 }
1763
1764
1765 /* Clear flags set by notice_special_calls.  Used by dead code removal
1766    to update the flags.  */
1767
1768 void
1769 clear_special_calls (void)
1770 {
1771   cfun->calls_alloca = false;
1772   cfun->calls_setjmp = false;
1773 }
1774
1775 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1776
1777 static void
1778 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1779 {
1780   /* Since this block is no longer reachable, we can just delete all
1781      of its PHI nodes.  */
1782   remove_phi_nodes (bb);
1783
1784   /* Remove edges to BB's successors.  */
1785   while (EDGE_COUNT (bb->succs) > 0)
1786     remove_edge (EDGE_SUCC (bb, 0));
1787 }
1788
1789
1790 /* Remove statements of basic block BB.  */
1791
1792 static void
1793 remove_bb (basic_block bb)
1794 {
1795   gimple_stmt_iterator i;
1796
1797   if (dump_file)
1798     {
1799       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1800       if (dump_flags & TDF_DETAILS)
1801         {
1802           dump_bb (bb, dump_file, 0);
1803           fprintf (dump_file, "\n");
1804         }
1805     }
1806
1807   if (current_loops)
1808     {
1809       struct loop *loop = bb->loop_father;
1810
1811       /* If a loop gets removed, clean up the information associated
1812          with it.  */
1813       if (loop->latch == bb
1814           || loop->header == bb)
1815         free_numbers_of_iterations_estimates_loop (loop);
1816     }
1817
1818   /* Remove all the instructions in the block.  */
1819   if (bb_seq (bb) != NULL)
1820     {
1821       /* Walk backwards so as to get a chance to substitute all
1822          released DEFs into debug stmts.  See
1823          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
1824          details.  */
1825       for (i = gsi_last_bb (bb); !gsi_end_p (i);)
1826         {
1827           gimple stmt = gsi_stmt (i);
1828           if (gimple_code (stmt) == GIMPLE_LABEL
1829               && (FORCED_LABEL (gimple_label_label (stmt))
1830                   || DECL_NONLOCAL (gimple_label_label (stmt))))
1831             {
1832               basic_block new_bb;
1833               gimple_stmt_iterator new_gsi;
1834
1835               /* A non-reachable non-local label may still be referenced.
1836                  But it no longer needs to carry the extra semantics of
1837                  non-locality.  */
1838               if (DECL_NONLOCAL (gimple_label_label (stmt)))
1839                 {
1840                   DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
1841                   FORCED_LABEL (gimple_label_label (stmt)) = 1;
1842                 }
1843
1844               new_bb = bb->prev_bb;
1845               new_gsi = gsi_start_bb (new_bb);
1846               gsi_remove (&i, false);
1847               gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
1848             }
1849           else
1850             {
1851               /* Release SSA definitions if we are in SSA.  Note that we
1852                  may be called when not in SSA.  For example,
1853                  final_cleanup calls this function via
1854                  cleanup_tree_cfg.  */
1855               if (gimple_in_ssa_p (cfun))
1856                 release_defs (stmt);
1857
1858               gsi_remove (&i, true);
1859             }
1860
1861           if (gsi_end_p (i))
1862             i = gsi_last_bb (bb);
1863           else
1864             gsi_prev (&i);
1865         }
1866     }
1867
1868   remove_phi_nodes_and_edges_for_unreachable_block (bb);
1869   bb->il.gimple = NULL;
1870 }
1871
1872
1873 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
1874    predicate VAL, return the edge that will be taken out of the block.
1875    If VAL does not match a unique edge, NULL is returned.  */
1876
1877 edge
1878 find_taken_edge (basic_block bb, tree val)
1879 {
1880   gimple stmt;
1881
1882   stmt = last_stmt (bb);
1883
1884   gcc_assert (stmt);
1885   gcc_assert (is_ctrl_stmt (stmt));
1886
1887   if (val == NULL)
1888     return NULL;
1889
1890   if (!is_gimple_min_invariant (val))
1891     return NULL;
1892
1893   if (gimple_code (stmt) == GIMPLE_COND)
1894     return find_taken_edge_cond_expr (bb, val);
1895
1896   if (gimple_code (stmt) == GIMPLE_SWITCH)
1897     return find_taken_edge_switch_expr (bb, val);
1898
1899   if (computed_goto_p (stmt))
1900     {
1901       /* Only optimize if the argument is a label, if the argument is
1902          not a label then we can not construct a proper CFG.
1903
1904          It may be the case that we only need to allow the LABEL_REF to
1905          appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
1906          appear inside a LABEL_EXPR just to be safe.  */
1907       if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
1908           && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
1909         return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
1910       return NULL;
1911     }
1912
1913   gcc_unreachable ();
1914 }
1915
1916 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
1917    statement, determine which of the outgoing edges will be taken out of the
1918    block.  Return NULL if either edge may be taken.  */
1919
1920 static edge
1921 find_taken_edge_computed_goto (basic_block bb, tree val)
1922 {
1923   basic_block dest;
1924   edge e = NULL;
1925
1926   dest = label_to_block (val);
1927   if (dest)
1928     {
1929       e = find_edge (bb, dest);
1930       gcc_assert (e != NULL);
1931     }
1932
1933   return e;
1934 }
1935
1936 /* Given a constant value VAL and the entry block BB to a COND_EXPR
1937    statement, determine which of the two edges will be taken out of the
1938    block.  Return NULL if either edge may be taken.  */
1939
1940 static edge
1941 find_taken_edge_cond_expr (basic_block bb, tree val)
1942 {
1943   edge true_edge, false_edge;
1944
1945   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1946
1947   gcc_assert (TREE_CODE (val) == INTEGER_CST);
1948   return (integer_zerop (val) ? false_edge : true_edge);
1949 }
1950
1951 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
1952    statement, determine which edge will be taken out of the block.  Return
1953    NULL if any edge may be taken.  */
1954
1955 static edge
1956 find_taken_edge_switch_expr (basic_block bb, tree val)
1957 {
1958   basic_block dest_bb;
1959   edge e;
1960   gimple switch_stmt;
1961   tree taken_case;
1962
1963   switch_stmt = last_stmt (bb);
1964   taken_case = find_case_label_for_value (switch_stmt, val);
1965   dest_bb = label_to_block (CASE_LABEL (taken_case));
1966
1967   e = find_edge (bb, dest_bb);
1968   gcc_assert (e);
1969   return e;
1970 }
1971
1972
1973 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
1974    We can make optimal use here of the fact that the case labels are
1975    sorted: We can do a binary search for a case matching VAL.  */
1976
1977 static tree
1978 find_case_label_for_value (gimple switch_stmt, tree val)
1979 {
1980   size_t low, high, n = gimple_switch_num_labels (switch_stmt);
1981   tree default_case = gimple_switch_default_label (switch_stmt);
1982
1983   for (low = 0, high = n; high - low > 1; )
1984     {
1985       size_t i = (high + low) / 2;
1986       tree t = gimple_switch_label (switch_stmt, i);
1987       int cmp;
1988
1989       /* Cache the result of comparing CASE_LOW and val.  */
1990       cmp = tree_int_cst_compare (CASE_LOW (t), val);
1991
1992       if (cmp > 0)
1993         high = i;
1994       else
1995         low = i;
1996
1997       if (CASE_HIGH (t) == NULL)
1998         {
1999           /* A singe-valued case label.  */
2000           if (cmp == 0)
2001             return t;
2002         }
2003       else
2004         {
2005           /* A case range.  We can only handle integer ranges.  */
2006           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2007             return t;
2008         }
2009     }
2010
2011   return default_case;
2012 }
2013
2014
2015 /* Dump a basic block on stderr.  */
2016
2017 void
2018 gimple_debug_bb (basic_block bb)
2019 {
2020   gimple_dump_bb (bb, stderr, 0, TDF_VOPS|TDF_MEMSYMS);
2021 }
2022
2023
2024 /* Dump basic block with index N on stderr.  */
2025
2026 basic_block
2027 gimple_debug_bb_n (int n)
2028 {
2029   gimple_debug_bb (BASIC_BLOCK (n));
2030   return BASIC_BLOCK (n);
2031 }
2032
2033
2034 /* Dump the CFG on stderr.
2035
2036    FLAGS are the same used by the tree dumping functions
2037    (see TDF_* in tree-pass.h).  */
2038
2039 void
2040 gimple_debug_cfg (int flags)
2041 {
2042   gimple_dump_cfg (stderr, flags);
2043 }
2044
2045
2046 /* Dump the program showing basic block boundaries on the given FILE.
2047
2048    FLAGS are the same used by the tree dumping functions (see TDF_* in
2049    tree.h).  */
2050
2051 void
2052 gimple_dump_cfg (FILE *file, int flags)
2053 {
2054   if (flags & TDF_DETAILS)
2055     {
2056       dump_function_header (file, current_function_decl, flags);
2057       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2058                n_basic_blocks, n_edges, last_basic_block);
2059
2060       brief_dump_cfg (file);
2061       fprintf (file, "\n");
2062     }
2063
2064   if (flags & TDF_STATS)
2065     dump_cfg_stats (file);
2066
2067   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2068 }
2069
2070
2071 /* Dump CFG statistics on FILE.  */
2072
2073 void
2074 dump_cfg_stats (FILE *file)
2075 {
2076   static long max_num_merged_labels = 0;
2077   unsigned long size, total = 0;
2078   long num_edges;
2079   basic_block bb;
2080   const char * const fmt_str   = "%-30s%-13s%12s\n";
2081   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2082   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2083   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2084   const char *funcname
2085     = lang_hooks.decl_printable_name (current_function_decl, 2);
2086
2087
2088   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2089
2090   fprintf (file, "---------------------------------------------------------\n");
2091   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2092   fprintf (file, fmt_str, "", "  instances  ", "used ");
2093   fprintf (file, "---------------------------------------------------------\n");
2094
2095   size = n_basic_blocks * sizeof (struct basic_block_def);
2096   total += size;
2097   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2098            SCALE (size), LABEL (size));
2099
2100   num_edges = 0;
2101   FOR_EACH_BB (bb)
2102     num_edges += EDGE_COUNT (bb->succs);
2103   size = num_edges * sizeof (struct edge_def);
2104   total += size;
2105   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2106
2107   fprintf (file, "---------------------------------------------------------\n");
2108   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2109            LABEL (total));
2110   fprintf (file, "---------------------------------------------------------\n");
2111   fprintf (file, "\n");
2112
2113   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2114     max_num_merged_labels = cfg_stats.num_merged_labels;
2115
2116   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2117            cfg_stats.num_merged_labels, max_num_merged_labels);
2118
2119   fprintf (file, "\n");
2120 }
2121
2122
2123 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2124    linked in the final executable.  */
2125
2126 DEBUG_FUNCTION void
2127 debug_cfg_stats (void)
2128 {
2129   dump_cfg_stats (stderr);
2130 }
2131
2132
2133 /* Dump the flowgraph to a .vcg FILE.  */
2134
2135 static void
2136 gimple_cfg2vcg (FILE *file)
2137 {
2138   edge e;
2139   edge_iterator ei;
2140   basic_block bb;
2141   const char *funcname
2142     = lang_hooks.decl_printable_name (current_function_decl, 2);
2143
2144   /* Write the file header.  */
2145   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2146   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2147   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2148
2149   /* Write blocks and edges.  */
2150   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2151     {
2152       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2153                e->dest->index);
2154
2155       if (e->flags & EDGE_FAKE)
2156         fprintf (file, " linestyle: dotted priority: 10");
2157       else
2158         fprintf (file, " linestyle: solid priority: 100");
2159
2160       fprintf (file, " }\n");
2161     }
2162   fputc ('\n', file);
2163
2164   FOR_EACH_BB (bb)
2165     {
2166       enum gimple_code head_code, end_code;
2167       const char *head_name, *end_name;
2168       int head_line = 0;
2169       int end_line = 0;
2170       gimple first = first_stmt (bb);
2171       gimple last = last_stmt (bb);
2172
2173       if (first)
2174         {
2175           head_code = gimple_code (first);
2176           head_name = gimple_code_name[head_code];
2177           head_line = get_lineno (first);
2178         }
2179       else
2180         head_name = "no-statement";
2181
2182       if (last)
2183         {
2184           end_code = gimple_code (last);
2185           end_name = gimple_code_name[end_code];
2186           end_line = get_lineno (last);
2187         }
2188       else
2189         end_name = "no-statement";
2190
2191       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2192                bb->index, bb->index, head_name, head_line, end_name,
2193                end_line);
2194
2195       FOR_EACH_EDGE (e, ei, bb->succs)
2196         {
2197           if (e->dest == EXIT_BLOCK_PTR)
2198             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2199           else
2200             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2201
2202           if (e->flags & EDGE_FAKE)
2203             fprintf (file, " priority: 10 linestyle: dotted");
2204           else
2205             fprintf (file, " priority: 100 linestyle: solid");
2206
2207           fprintf (file, " }\n");
2208         }
2209
2210       if (bb->next_bb != EXIT_BLOCK_PTR)
2211         fputc ('\n', file);
2212     }
2213
2214   fputs ("}\n\n", file);
2215 }
2216
2217
2218
2219 /*---------------------------------------------------------------------------
2220                              Miscellaneous helpers
2221 ---------------------------------------------------------------------------*/
2222
2223 /* Return true if T represents a stmt that always transfers control.  */
2224
2225 bool
2226 is_ctrl_stmt (gimple t)
2227 {
2228   switch (gimple_code (t))
2229     {
2230     case GIMPLE_COND:
2231     case GIMPLE_SWITCH:
2232     case GIMPLE_GOTO:
2233     case GIMPLE_RETURN:
2234     case GIMPLE_RESX:
2235       return true;
2236     default:
2237       return false;
2238     }
2239 }
2240
2241
2242 /* Return true if T is a statement that may alter the flow of control
2243    (e.g., a call to a non-returning function).  */
2244
2245 bool
2246 is_ctrl_altering_stmt (gimple t)
2247 {
2248   gcc_assert (t);
2249
2250   switch (gimple_code (t))
2251     {
2252     case GIMPLE_CALL:
2253       {
2254         int flags = gimple_call_flags (t);
2255
2256         /* A non-pure/const call alters flow control if the current
2257            function has nonlocal labels.  */
2258         if (!(flags & (ECF_CONST | ECF_PURE | ECF_LEAF))
2259             && cfun->has_nonlocal_label)
2260           return true;
2261
2262         /* A call also alters control flow if it does not return.  */
2263         if (flags & ECF_NORETURN)
2264           return true;
2265
2266         /* BUILT_IN_RETURN call is same as return statement.  */
2267         if (gimple_call_builtin_p (t, BUILT_IN_RETURN))
2268           return true;
2269       }
2270       break;
2271
2272     case GIMPLE_EH_DISPATCH:
2273       /* EH_DISPATCH branches to the individual catch handlers at
2274          this level of a try or allowed-exceptions region.  It can
2275          fallthru to the next statement as well.  */
2276       return true;
2277
2278     case GIMPLE_ASM:
2279       if (gimple_asm_nlabels (t) > 0)
2280         return true;
2281       break;
2282
2283     CASE_GIMPLE_OMP:
2284       /* OpenMP directives alter control flow.  */
2285       return true;
2286
2287     default:
2288       break;
2289     }
2290
2291   /* If a statement can throw, it alters control flow.  */
2292   return stmt_can_throw_internal (t);
2293 }
2294
2295
2296 /* Return true if T is a simple local goto.  */
2297
2298 bool
2299 simple_goto_p (gimple t)
2300 {
2301   return (gimple_code (t) == GIMPLE_GOTO
2302           && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2303 }
2304
2305
2306 /* Return true if T can make an abnormal transfer of control flow.
2307    Transfers of control flow associated with EH are excluded.  */
2308
2309 bool
2310 stmt_can_make_abnormal_goto (gimple t)
2311 {
2312   if (computed_goto_p (t))
2313     return true;
2314   if (is_gimple_call (t))
2315     return (gimple_has_side_effects (t) && cfun->has_nonlocal_label
2316             && !(gimple_call_flags (t) & ECF_LEAF));
2317   return false;
2318 }
2319
2320
2321 /* Return true if STMT should start a new basic block.  PREV_STMT is
2322    the statement preceding STMT.  It is used when STMT is a label or a
2323    case label.  Labels should only start a new basic block if their
2324    previous statement wasn't a label.  Otherwise, sequence of labels
2325    would generate unnecessary basic blocks that only contain a single
2326    label.  */
2327
2328 static inline bool
2329 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2330 {
2331   if (stmt == NULL)
2332     return false;
2333
2334   /* Labels start a new basic block only if the preceding statement
2335      wasn't a label of the same type.  This prevents the creation of
2336      consecutive blocks that have nothing but a single label.  */
2337   if (gimple_code (stmt) == GIMPLE_LABEL)
2338     {
2339       /* Nonlocal and computed GOTO targets always start a new block.  */
2340       if (DECL_NONLOCAL (gimple_label_label (stmt))
2341           || FORCED_LABEL (gimple_label_label (stmt)))
2342         return true;
2343
2344       if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2345         {
2346           if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2347             return true;
2348
2349           cfg_stats.num_merged_labels++;
2350           return false;
2351         }
2352       else
2353         return true;
2354     }
2355
2356   return false;
2357 }
2358
2359
2360 /* Return true if T should end a basic block.  */
2361
2362 bool
2363 stmt_ends_bb_p (gimple t)
2364 {
2365   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2366 }
2367
2368 /* Remove block annotations and other data structures.  */
2369
2370 void
2371 delete_tree_cfg_annotations (void)
2372 {
2373   label_to_block_map = NULL;
2374 }
2375
2376
2377 /* Return the first statement in basic block BB.  */
2378
2379 gimple
2380 first_stmt (basic_block bb)
2381 {
2382   gimple_stmt_iterator i = gsi_start_bb (bb);
2383   gimple stmt = NULL;
2384
2385   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2386     {
2387       gsi_next (&i);
2388       stmt = NULL;
2389     }
2390   return stmt;
2391 }
2392
2393 /* Return the first non-label statement in basic block BB.  */
2394
2395 static gimple
2396 first_non_label_stmt (basic_block bb)
2397 {
2398   gimple_stmt_iterator i = gsi_start_bb (bb);
2399   while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2400     gsi_next (&i);
2401   return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2402 }
2403
2404 /* Return the last statement in basic block BB.  */
2405
2406 gimple
2407 last_stmt (basic_block bb)
2408 {
2409   gimple_stmt_iterator i = gsi_last_bb (bb);
2410   gimple stmt = NULL;
2411
2412   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2413     {
2414       gsi_prev (&i);
2415       stmt = NULL;
2416     }
2417   return stmt;
2418 }
2419
2420 /* Return the last statement of an otherwise empty block.  Return NULL
2421    if the block is totally empty, or if it contains more than one
2422    statement.  */
2423
2424 gimple
2425 last_and_only_stmt (basic_block bb)
2426 {
2427   gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
2428   gimple last, prev;
2429
2430   if (gsi_end_p (i))
2431     return NULL;
2432
2433   last = gsi_stmt (i);
2434   gsi_prev_nondebug (&i);
2435   if (gsi_end_p (i))
2436     return last;
2437
2438   /* Empty statements should no longer appear in the instruction stream.
2439      Everything that might have appeared before should be deleted by
2440      remove_useless_stmts, and the optimizers should just gsi_remove
2441      instead of smashing with build_empty_stmt.
2442
2443      Thus the only thing that should appear here in a block containing
2444      one executable statement is a label.  */
2445   prev = gsi_stmt (i);
2446   if (gimple_code (prev) == GIMPLE_LABEL)
2447     return last;
2448   else
2449     return NULL;
2450 }
2451
2452 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
2453
2454 static void
2455 reinstall_phi_args (edge new_edge, edge old_edge)
2456 {
2457   edge_var_map_vector v;
2458   edge_var_map *vm;
2459   int i;
2460   gimple_stmt_iterator phis;
2461
2462   v = redirect_edge_var_map_vector (old_edge);
2463   if (!v)
2464     return;
2465
2466   for (i = 0, phis = gsi_start_phis (new_edge->dest);
2467        VEC_iterate (edge_var_map, v, i, vm) && !gsi_end_p (phis);
2468        i++, gsi_next (&phis))
2469     {
2470       gimple phi = gsi_stmt (phis);
2471       tree result = redirect_edge_var_map_result (vm);
2472       tree arg = redirect_edge_var_map_def (vm);
2473
2474       gcc_assert (result == gimple_phi_result (phi));
2475
2476       add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
2477     }
2478
2479   redirect_edge_var_map_clear (old_edge);
2480 }
2481
2482 /* Returns the basic block after which the new basic block created
2483    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
2484    near its "logical" location.  This is of most help to humans looking
2485    at debugging dumps.  */
2486
2487 static basic_block
2488 split_edge_bb_loc (edge edge_in)
2489 {
2490   basic_block dest = edge_in->dest;
2491   basic_block dest_prev = dest->prev_bb;
2492
2493   if (dest_prev)
2494     {
2495       edge e = find_edge (dest_prev, dest);
2496       if (e && !(e->flags & EDGE_COMPLEX))
2497         return edge_in->src;
2498     }
2499   return dest_prev;
2500 }
2501
2502 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
2503    Abort on abnormal edges.  */
2504
2505 static basic_block
2506 gimple_split_edge (edge edge_in)
2507 {
2508   basic_block new_bb, after_bb, dest;
2509   edge new_edge, e;
2510
2511   /* Abnormal edges cannot be split.  */
2512   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2513
2514   dest = edge_in->dest;
2515
2516   after_bb = split_edge_bb_loc (edge_in);
2517
2518   new_bb = create_empty_bb (after_bb);
2519   new_bb->frequency = EDGE_FREQUENCY (edge_in);
2520   new_bb->count = edge_in->count;
2521   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2522   new_edge->probability = REG_BR_PROB_BASE;
2523   new_edge->count = edge_in->count;
2524
2525   e = redirect_edge_and_branch (edge_in, new_bb);
2526   gcc_assert (e == edge_in);
2527   reinstall_phi_args (new_edge, e);
2528
2529   return new_bb;
2530 }
2531
2532
2533 /* Verify properties of the address expression T with base object BASE.  */
2534
2535 static tree
2536 verify_address (tree t, tree base)
2537 {
2538   bool old_constant;
2539   bool old_side_effects;
2540   bool new_constant;
2541   bool new_side_effects;
2542
2543   old_constant = TREE_CONSTANT (t);
2544   old_side_effects = TREE_SIDE_EFFECTS (t);
2545
2546   recompute_tree_invariant_for_addr_expr (t);
2547   new_side_effects = TREE_SIDE_EFFECTS (t);
2548   new_constant = TREE_CONSTANT (t);
2549
2550   if (old_constant != new_constant)
2551     {
2552       error ("constant not recomputed when ADDR_EXPR changed");
2553       return t;
2554     }
2555   if (old_side_effects != new_side_effects)
2556     {
2557       error ("side effects not recomputed when ADDR_EXPR changed");
2558       return t;
2559     }
2560
2561   if (!(TREE_CODE (base) == VAR_DECL
2562         || TREE_CODE (base) == PARM_DECL
2563         || TREE_CODE (base) == RESULT_DECL))
2564     return NULL_TREE;
2565
2566   if (DECL_GIMPLE_REG_P (base))
2567     {
2568       error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2569       return base;
2570     }
2571
2572   return NULL_TREE;
2573 }
2574
2575 /* Callback for walk_tree, check that all elements with address taken are
2576    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
2577    inside a PHI node.  */
2578
2579 static tree
2580 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2581 {
2582   tree t = *tp, x;
2583
2584   if (TYPE_P (t))
2585     *walk_subtrees = 0;
2586
2587   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
2588 #define CHECK_OP(N, MSG) \
2589   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
2590        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2591
2592   switch (TREE_CODE (t))
2593     {
2594     case SSA_NAME:
2595       if (SSA_NAME_IN_FREE_LIST (t))
2596         {
2597           error ("SSA name in freelist but still referenced");
2598           return *tp;
2599         }
2600       break;
2601
2602     case INDIRECT_REF:
2603       error ("INDIRECT_REF in gimple IL");
2604       return t;
2605
2606     case MEM_REF:
2607       x = TREE_OPERAND (t, 0);
2608       if (!POINTER_TYPE_P (TREE_TYPE (x))
2609           || !is_gimple_mem_ref_addr (x))
2610         {
2611           error ("invalid first operand of MEM_REF");
2612           return x;
2613         }
2614       if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST
2615           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1))))
2616         {
2617           error ("invalid offset operand of MEM_REF");
2618           return TREE_OPERAND (t, 1);
2619         }
2620       if (TREE_CODE (x) == ADDR_EXPR
2621           && (x = verify_address (x, TREE_OPERAND (x, 0))))
2622         return x;
2623       *walk_subtrees = 0;
2624       break;
2625
2626     case ASSERT_EXPR:
2627       x = fold (ASSERT_EXPR_COND (t));
2628       if (x == boolean_false_node)
2629         {
2630           error ("ASSERT_EXPR with an always-false condition");
2631           return *tp;
2632         }
2633       break;
2634
2635     case MODIFY_EXPR:
2636       error ("MODIFY_EXPR not expected while having tuples");
2637       return *tp;
2638
2639     case ADDR_EXPR:
2640       {
2641         tree tem;
2642
2643         gcc_assert (is_gimple_address (t));
2644
2645         /* Skip any references (they will be checked when we recurse down the
2646            tree) and ensure that any variable used as a prefix is marked
2647            addressable.  */
2648         for (x = TREE_OPERAND (t, 0);
2649              handled_component_p (x);
2650              x = TREE_OPERAND (x, 0))
2651           ;
2652
2653         if ((tem = verify_address (t, x)))
2654           return tem;
2655
2656         if (!(TREE_CODE (x) == VAR_DECL
2657               || TREE_CODE (x) == PARM_DECL
2658               || TREE_CODE (x) == RESULT_DECL))
2659           return NULL;
2660
2661         if (!TREE_ADDRESSABLE (x))
2662           {
2663             error ("address taken, but ADDRESSABLE bit not set");
2664             return x;
2665           }
2666
2667         break;
2668       }
2669
2670     case COND_EXPR:
2671       x = COND_EXPR_COND (t);
2672       if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2673         {
2674           error ("non-integral used in condition");
2675           return x;
2676         }
2677       if (!is_gimple_condexpr (x))
2678         {
2679           error ("invalid conditional operand");
2680           return x;
2681         }
2682       break;
2683
2684     case NON_LVALUE_EXPR:
2685     case TRUTH_NOT_EXPR:
2686       gcc_unreachable ();
2687
2688     CASE_CONVERT:
2689     case FIX_TRUNC_EXPR:
2690     case FLOAT_EXPR:
2691     case NEGATE_EXPR:
2692     case ABS_EXPR:
2693     case BIT_NOT_EXPR:
2694       CHECK_OP (0, "invalid operand to unary operator");
2695       break;
2696
2697     case REALPART_EXPR:
2698     case IMAGPART_EXPR:
2699     case COMPONENT_REF:
2700     case ARRAY_REF:
2701     case ARRAY_RANGE_REF:
2702     case BIT_FIELD_REF:
2703     case VIEW_CONVERT_EXPR:
2704       /* We have a nest of references.  Verify that each of the operands
2705          that determine where to reference is either a constant or a variable,
2706          verify that the base is valid, and then show we've already checked
2707          the subtrees.  */
2708       while (handled_component_p (t))
2709         {
2710           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2711             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2712           else if (TREE_CODE (t) == ARRAY_REF
2713                    || TREE_CODE (t) == ARRAY_RANGE_REF)
2714             {
2715               CHECK_OP (1, "invalid array index");
2716               if (TREE_OPERAND (t, 2))
2717                 CHECK_OP (2, "invalid array lower bound");
2718               if (TREE_OPERAND (t, 3))
2719                 CHECK_OP (3, "invalid array stride");
2720             }
2721           else if (TREE_CODE (t) == BIT_FIELD_REF)
2722             {
2723               if (!host_integerp (TREE_OPERAND (t, 1), 1)
2724                   || !host_integerp (TREE_OPERAND (t, 2), 1))
2725                 {
2726                   error ("invalid position or size operand to BIT_FIELD_REF");
2727                   return t;
2728                 }
2729               else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2730                        && (TYPE_PRECISION (TREE_TYPE (t))
2731                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2732                 {
2733                   error ("integral result type precision does not match "
2734                          "field size of BIT_FIELD_REF");
2735                   return t;
2736                 }
2737               if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2738                   && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2739                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2740                 {
2741                   error ("mode precision of non-integral result does not "
2742                          "match field size of BIT_FIELD_REF");
2743                   return t;
2744                 }
2745             }
2746
2747           t = TREE_OPERAND (t, 0);
2748         }
2749
2750       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2751         {
2752           error ("invalid reference prefix");
2753           return t;
2754         }
2755       *walk_subtrees = 0;
2756       break;
2757     case PLUS_EXPR:
2758     case MINUS_EXPR:
2759       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2760          POINTER_PLUS_EXPR. */
2761       if (POINTER_TYPE_P (TREE_TYPE (t)))
2762         {
2763           error ("invalid operand to plus/minus, type is a pointer");
2764           return t;
2765         }
2766       CHECK_OP (0, "invalid operand to binary operator");
2767       CHECK_OP (1, "invalid operand to binary operator");
2768       break;
2769
2770     case POINTER_PLUS_EXPR:
2771       /* Check to make sure the first operand is a pointer or reference type. */
2772       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
2773         {
2774           error ("invalid operand to pointer plus, first operand is not a pointer");
2775           return t;
2776         }
2777       /* Check to make sure the second operand is a ptrofftype.  */
2778       if (!ptrofftype_p (TREE_TYPE (TREE_OPERAND (t, 1))))
2779         {
2780           error ("invalid operand to pointer plus, second operand is not an "
2781                  "integer type of appropriate width");
2782           return t;
2783         }
2784       /* FALLTHROUGH */
2785     case LT_EXPR:
2786     case LE_EXPR:
2787     case GT_EXPR:
2788     case GE_EXPR:
2789     case EQ_EXPR:
2790     case NE_EXPR:
2791     case UNORDERED_EXPR:
2792     case ORDERED_EXPR:
2793     case UNLT_EXPR:
2794     case UNLE_EXPR:
2795     case UNGT_EXPR:
2796     case UNGE_EXPR:
2797     case UNEQ_EXPR:
2798     case LTGT_EXPR:
2799     case MULT_EXPR:
2800     case TRUNC_DIV_EXPR:
2801     case CEIL_DIV_EXPR:
2802     case FLOOR_DIV_EXPR:
2803     case ROUND_DIV_EXPR:
2804     case TRUNC_MOD_EXPR:
2805     case CEIL_MOD_EXPR:
2806     case FLOOR_MOD_EXPR:
2807     case ROUND_MOD_EXPR:
2808     case RDIV_EXPR:
2809     case EXACT_DIV_EXPR:
2810     case MIN_EXPR:
2811     case MAX_EXPR:
2812     case LSHIFT_EXPR:
2813     case RSHIFT_EXPR:
2814     case LROTATE_EXPR:
2815     case RROTATE_EXPR:
2816     case BIT_IOR_EXPR:
2817     case BIT_XOR_EXPR:
2818     case BIT_AND_EXPR:
2819       CHECK_OP (0, "invalid operand to binary operator");
2820       CHECK_OP (1, "invalid operand to binary operator");
2821       break;
2822
2823     case CONSTRUCTOR:
2824       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2825         *walk_subtrees = 0;
2826       break;
2827
2828     case CASE_LABEL_EXPR:
2829       if (CASE_CHAIN (t))
2830         {
2831           error ("invalid CASE_CHAIN");
2832           return t;
2833         }
2834       break;
2835
2836     default:
2837       break;
2838     }
2839   return NULL;
2840
2841 #undef CHECK_OP
2842 }
2843
2844
2845 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
2846    Returns true if there is an error, otherwise false.  */
2847
2848 static bool
2849 verify_types_in_gimple_min_lval (tree expr)
2850 {
2851   tree op;
2852
2853   if (is_gimple_id (expr))
2854     return false;
2855
2856   if (TREE_CODE (expr) != TARGET_MEM_REF
2857       && TREE_CODE (expr) != MEM_REF)
2858     {
2859       error ("invalid expression for min lvalue");
2860       return true;
2861     }
2862
2863   /* TARGET_MEM_REFs are strange beasts.  */
2864   if (TREE_CODE (expr) == TARGET_MEM_REF)
2865     return false;
2866
2867   op = TREE_OPERAND (expr, 0);
2868   if (!is_gimple_val (op))
2869     {
2870       error ("invalid operand in indirect reference");
2871       debug_generic_stmt (op);
2872       return true;
2873     }
2874   /* Memory references now generally can involve a value conversion.  */
2875
2876   return false;
2877 }
2878
2879 /* Verify if EXPR is a valid GIMPLE reference expression.  If
2880    REQUIRE_LVALUE is true verifies it is an lvalue.  Returns true
2881    if there is an error, otherwise false.  */
2882
2883 static bool
2884 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
2885 {
2886   while (handled_component_p (expr))
2887     {
2888       tree op = TREE_OPERAND (expr, 0);
2889
2890       if (TREE_CODE (expr) == ARRAY_REF
2891           || TREE_CODE (expr) == ARRAY_RANGE_REF)
2892         {
2893           if (!is_gimple_val (TREE_OPERAND (expr, 1))
2894               || (TREE_OPERAND (expr, 2)
2895                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
2896               || (TREE_OPERAND (expr, 3)
2897                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
2898             {
2899               error ("invalid operands to array reference");
2900               debug_generic_stmt (expr);
2901               return true;
2902             }
2903         }
2904
2905       /* Verify if the reference array element types are compatible.  */
2906       if (TREE_CODE (expr) == ARRAY_REF
2907           && !useless_type_conversion_p (TREE_TYPE (expr),
2908                                          TREE_TYPE (TREE_TYPE (op))))
2909         {
2910           error ("type mismatch in array reference");
2911           debug_generic_stmt (TREE_TYPE (expr));
2912           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2913           return true;
2914         }
2915       if (TREE_CODE (expr) == ARRAY_RANGE_REF
2916           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
2917                                          TREE_TYPE (TREE_TYPE (op))))
2918         {
2919           error ("type mismatch in array range reference");
2920           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
2921           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2922           return true;
2923         }
2924
2925       if ((TREE_CODE (expr) == REALPART_EXPR
2926            || TREE_CODE (expr) == IMAGPART_EXPR)
2927           && !useless_type_conversion_p (TREE_TYPE (expr),
2928                                          TREE_TYPE (TREE_TYPE (op))))
2929         {
2930           error ("type mismatch in real/imagpart reference");
2931           debug_generic_stmt (TREE_TYPE (expr));
2932           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2933           return true;
2934         }
2935
2936       if (TREE_CODE (expr) == COMPONENT_REF
2937           && !useless_type_conversion_p (TREE_TYPE (expr),
2938                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
2939         {
2940           error ("type mismatch in component reference");
2941           debug_generic_stmt (TREE_TYPE (expr));
2942           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
2943           return true;
2944         }
2945
2946       if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
2947         {
2948           /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check
2949              that their operand is not an SSA name or an invariant when
2950              requiring an lvalue (this usually means there is a SRA or IPA-SRA
2951              bug).  Otherwise there is nothing to verify, gross mismatches at
2952              most invoke undefined behavior.  */
2953           if (require_lvalue
2954               && (TREE_CODE (op) == SSA_NAME
2955                   || is_gimple_min_invariant (op)))
2956             {
2957               error ("conversion of an SSA_NAME on the left hand side");
2958               debug_generic_stmt (expr);
2959               return true;
2960             }
2961           else if (TREE_CODE (op) == SSA_NAME
2962                    && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op)))
2963             {
2964               error ("conversion of register to a different size");
2965               debug_generic_stmt (expr);
2966               return true;
2967             }
2968           else if (!handled_component_p (op))
2969             return false;
2970         }
2971
2972       expr = op;
2973     }
2974
2975   if (TREE_CODE (expr) == MEM_REF)
2976     {
2977       if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0)))
2978         {
2979           error ("invalid address operand in MEM_REF");
2980           debug_generic_stmt (expr);
2981           return true;
2982         }
2983       if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST
2984           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
2985         {
2986           error ("invalid offset operand in MEM_REF");
2987           debug_generic_stmt (expr);
2988           return true;
2989         }
2990     }
2991   else if (TREE_CODE (expr) == TARGET_MEM_REF)
2992     {
2993       if (!TMR_BASE (expr)
2994           || !is_gimple_mem_ref_addr (TMR_BASE (expr)))
2995         {
2996           error ("invalid address operand in TARGET_MEM_REF");
2997           return true;
2998         }
2999       if (!TMR_OFFSET (expr)
3000           || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST
3001           || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr))))
3002         {
3003           error ("invalid offset operand in TARGET_MEM_REF");
3004           debug_generic_stmt (expr);
3005           return true;
3006         }
3007     }
3008
3009   return ((require_lvalue || !is_gimple_min_invariant (expr))
3010           && verify_types_in_gimple_min_lval (expr));
3011 }
3012
3013 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3014    list of pointer-to types that is trivially convertible to DEST.  */
3015
3016 static bool
3017 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3018 {
3019   tree src;
3020
3021   if (!TYPE_POINTER_TO (src_obj))
3022     return true;
3023
3024   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3025     if (useless_type_conversion_p (dest, src))
3026       return true;
3027
3028   return false;
3029 }
3030
3031 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3032    from TYPE2 can be handled by FIXED_CONVERT_EXPR.  */
3033
3034 static bool
3035 valid_fixed_convert_types_p (tree type1, tree type2)
3036 {
3037   return (FIXED_POINT_TYPE_P (type1)
3038           && (INTEGRAL_TYPE_P (type2)
3039               || SCALAR_FLOAT_TYPE_P (type2)
3040               || FIXED_POINT_TYPE_P (type2)));
3041 }
3042
3043 /* Verify the contents of a GIMPLE_CALL STMT.  Returns true when there
3044    is a problem, otherwise false.  */
3045
3046 static bool
3047 verify_gimple_call (gimple stmt)
3048 {
3049   tree fn = gimple_call_fn (stmt);
3050   tree fntype, fndecl;
3051   unsigned i;
3052
3053   if (gimple_call_internal_p (stmt))
3054     {
3055       if (fn)
3056         {
3057           error ("gimple call has two targets");
3058           debug_generic_stmt (fn);
3059           return true;
3060         }
3061     }
3062   else
3063     {
3064       if (!fn)
3065         {
3066           error ("gimple call has no target");
3067           return true;
3068         }
3069     }
3070
3071   if (fn && !is_gimple_call_addr (fn))
3072     {
3073       error ("invalid function in gimple call");
3074       debug_generic_stmt (fn);
3075       return true;
3076     }
3077
3078   if (fn
3079       && (!POINTER_TYPE_P (TREE_TYPE (fn))
3080           || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3081               && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE)))
3082     {
3083       error ("non-function in gimple call");
3084       return true;
3085     }
3086
3087    fndecl = gimple_call_fndecl (stmt);
3088    if (fndecl
3089        && TREE_CODE (fndecl) == FUNCTION_DECL
3090        && DECL_LOOPING_CONST_OR_PURE_P (fndecl)
3091        && !DECL_PURE_P (fndecl)
3092        && !TREE_READONLY (fndecl))
3093      {
3094        error ("invalid pure const state for function");
3095        return true;
3096      }
3097
3098   if (gimple_call_lhs (stmt)
3099       && (!is_gimple_lvalue (gimple_call_lhs (stmt))
3100           || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true)))
3101     {
3102       error ("invalid LHS in gimple call");
3103       return true;
3104     }
3105
3106   if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt))
3107     {
3108       error ("LHS in noreturn call");
3109       return true;
3110     }
3111
3112   fntype = gimple_call_fntype (stmt);
3113   if (fntype
3114       && gimple_call_lhs (stmt)
3115       && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3116                                      TREE_TYPE (fntype))
3117       /* ???  At least C++ misses conversions at assignments from
3118          void * call results.
3119          ???  Java is completely off.  Especially with functions
3120          returning java.lang.Object.
3121          For now simply allow arbitrary pointer type conversions.  */
3122       && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3123            && POINTER_TYPE_P (TREE_TYPE (fntype))))
3124     {
3125       error ("invalid conversion in gimple call");
3126       debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3127       debug_generic_stmt (TREE_TYPE (fntype));
3128       return true;
3129     }
3130
3131   if (gimple_call_chain (stmt)
3132       && !is_gimple_val (gimple_call_chain (stmt)))
3133     {
3134       error ("invalid static chain in gimple call");
3135       debug_generic_stmt (gimple_call_chain (stmt));
3136       return true;
3137     }
3138
3139   /* If there is a static chain argument, this should not be an indirect
3140      call, and the decl should have DECL_STATIC_CHAIN set.  */
3141   if (gimple_call_chain (stmt))
3142     {
3143       if (!gimple_call_fndecl (stmt))
3144         {
3145           error ("static chain in indirect gimple call");
3146           return true;
3147         }
3148       fn = TREE_OPERAND (fn, 0);
3149
3150       if (!DECL_STATIC_CHAIN (fn))
3151         {
3152           error ("static chain with function that doesn%'t use one");
3153           return true;
3154         }
3155     }
3156
3157   /* ???  The C frontend passes unpromoted arguments in case it
3158      didn't see a function declaration before the call.  So for now
3159      leave the call arguments mostly unverified.  Once we gimplify
3160      unit-at-a-time we have a chance to fix this.  */
3161
3162   for (i = 0; i < gimple_call_num_args (stmt); ++i)
3163     {
3164       tree arg = gimple_call_arg (stmt, i);
3165       if ((is_gimple_reg_type (TREE_TYPE (arg))
3166            && !is_gimple_val (arg))
3167           || (!is_gimple_reg_type (TREE_TYPE (arg))
3168               && !is_gimple_lvalue (arg)))
3169         {
3170           error ("invalid argument to gimple call");
3171           debug_generic_expr (arg);
3172           return true;
3173         }
3174     }
3175
3176   return false;
3177 }
3178
3179 /* Verifies the gimple comparison with the result type TYPE and
3180    the operands OP0 and OP1.  */
3181
3182 static bool
3183 verify_gimple_comparison (tree type, tree op0, tree op1)
3184 {
3185   tree op0_type = TREE_TYPE (op0);
3186   tree op1_type = TREE_TYPE (op1);
3187
3188   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3189     {
3190       error ("invalid operands in gimple comparison");
3191       return true;
3192     }
3193
3194   /* For comparisons we do not have the operations type as the
3195      effective type the comparison is carried out in.  Instead
3196      we require that either the first operand is trivially
3197      convertible into the second, or the other way around.
3198      Because we special-case pointers to void we allow
3199      comparisons of pointers with the same mode as well.  */
3200   if (!useless_type_conversion_p (op0_type, op1_type)
3201       && !useless_type_conversion_p (op1_type, op0_type)
3202       && (!POINTER_TYPE_P (op0_type)
3203           || !POINTER_TYPE_P (op1_type)
3204           || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3205     {
3206       error ("mismatching comparison operand types");
3207       debug_generic_expr (op0_type);
3208       debug_generic_expr (op1_type);
3209       return true;
3210     }
3211
3212   /* The resulting type of a comparison may be an effective boolean type.  */
3213   if (INTEGRAL_TYPE_P (type)
3214       && (TREE_CODE (type) == BOOLEAN_TYPE
3215           || TYPE_PRECISION (type) == 1))
3216     ;
3217   /* Or an integer vector type with the same size and element count
3218      as the comparison operand types.  */
3219   else if (TREE_CODE (type) == VECTOR_TYPE
3220            && TREE_CODE (TREE_TYPE (type)) == INTEGER_TYPE)
3221     {
3222       if (TREE_CODE (op0_type) != VECTOR_TYPE
3223           || TREE_CODE (op1_type) != VECTOR_TYPE)
3224         {
3225           error ("non-vector operands in vector comparison");
3226           debug_generic_expr (op0_type);
3227           debug_generic_expr (op1_type);
3228           return true;
3229         }
3230
3231       if (TYPE_VECTOR_SUBPARTS (type) != TYPE_VECTOR_SUBPARTS (op0_type)
3232           || (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (type)))
3233               != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0_type)))))
3234         {
3235           error ("invalid vector comparison resulting type");
3236           debug_generic_expr (type);
3237           return true;
3238         }
3239     }
3240   else
3241     {
3242       error ("bogus comparison result type");
3243       debug_generic_expr (type);
3244       return true;
3245     }
3246
3247   return false;
3248 }
3249
3250 /* Verify a gimple assignment statement STMT with an unary rhs.
3251    Returns true if anything is wrong.  */
3252
3253 static bool
3254 verify_gimple_assign_unary (gimple stmt)
3255 {
3256   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3257   tree lhs = gimple_assign_lhs (stmt);
3258   tree lhs_type = TREE_TYPE (lhs);
3259   tree rhs1 = gimple_assign_rhs1 (stmt);
3260   tree rhs1_type = TREE_TYPE (rhs1);
3261
3262   if (!is_gimple_reg (lhs))
3263     {
3264       error ("non-register as LHS of unary operation");
3265       return true;
3266     }
3267
3268   if (!is_gimple_val (rhs1))
3269     {
3270       error ("invalid operand in unary operation");
3271       return true;
3272     }
3273
3274   /* First handle conversions.  */
3275   switch (rhs_code)
3276     {
3277     CASE_CONVERT:
3278       {
3279         /* Allow conversions between integral types and pointers only if
3280            there is no sign or zero extension involved.
3281            For targets were the precision of ptrofftype doesn't match that
3282            of pointers we need to allow arbitrary conversions from and
3283            to ptrofftype.  */
3284         if ((POINTER_TYPE_P (lhs_type)
3285              && INTEGRAL_TYPE_P (rhs1_type)
3286              && (TYPE_PRECISION (lhs_type) >= TYPE_PRECISION (rhs1_type)
3287                  || ptrofftype_p (rhs1_type)))
3288             || (POINTER_TYPE_P (rhs1_type)
3289                 && INTEGRAL_TYPE_P (lhs_type)
3290                 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3291                     || ptrofftype_p (sizetype))))
3292           return false;
3293
3294         /* Allow conversion from integer to offset type and vice versa.  */
3295         if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3296              && TREE_CODE (rhs1_type) == INTEGER_TYPE)
3297             || (TREE_CODE (lhs_type) == INTEGER_TYPE
3298                 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3299           return false;
3300
3301         /* Otherwise assert we are converting between types of the
3302            same kind.  */
3303         if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3304           {
3305             error ("invalid types in nop conversion");
3306             debug_generic_expr (lhs_type);
3307             debug_generic_expr (rhs1_type);
3308             return true;
3309           }
3310
3311         return false;
3312       }
3313
3314     case ADDR_SPACE_CONVERT_EXPR:
3315       {
3316         if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3317             || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3318                 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3319           {
3320             error ("invalid types in address space conversion");
3321             debug_generic_expr (lhs_type);
3322             debug_generic_expr (rhs1_type);
3323             return true;
3324           }
3325
3326         return false;
3327       }
3328
3329     case FIXED_CONVERT_EXPR:
3330       {
3331         if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3332             && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3333           {
3334             error ("invalid types in fixed-point conversion");
3335             debug_generic_expr (lhs_type);
3336             debug_generic_expr (rhs1_type);
3337             return true;
3338           }
3339
3340         return false;
3341       }
3342
3343     case FLOAT_EXPR:
3344       {
3345         if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3346             && (!VECTOR_INTEGER_TYPE_P (rhs1_type)
3347                 || !VECTOR_FLOAT_TYPE_P(lhs_type)))
3348           {
3349             error ("invalid types in conversion to floating point");
3350             debug_generic_expr (lhs_type);
3351             debug_generic_expr (rhs1_type);
3352             return true;
3353           }
3354
3355         return false;
3356       }
3357
3358     case FIX_TRUNC_EXPR:
3359       {
3360         if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3361             && (!VECTOR_INTEGER_TYPE_P (lhs_type)
3362                 || !VECTOR_FLOAT_TYPE_P(rhs1_type)))
3363           {
3364             error ("invalid types in conversion to integer");
3365             debug_generic_expr (lhs_type);
3366             debug_generic_expr (rhs1_type);
3367             return true;
3368           }
3369
3370         return false;
3371       }
3372
3373     case VEC_UNPACK_HI_EXPR:
3374     case VEC_UNPACK_LO_EXPR:
3375     case REDUC_MAX_EXPR:
3376     case REDUC_MIN_EXPR:
3377     case REDUC_PLUS_EXPR:
3378     case VEC_UNPACK_FLOAT_HI_EXPR:
3379     case VEC_UNPACK_FLOAT_LO_EXPR:
3380       /* FIXME.  */
3381       return false;
3382
3383     case NEGATE_EXPR:
3384     case ABS_EXPR:
3385     case BIT_NOT_EXPR:
3386     case PAREN_EXPR:
3387     case NON_LVALUE_EXPR:
3388     case CONJ_EXPR:
3389       break;
3390
3391     default:
3392       gcc_unreachable ();
3393     }
3394
3395   /* For the remaining codes assert there is no conversion involved.  */
3396   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3397     {
3398       error ("non-trivial conversion in unary operation");
3399       debug_generic_expr (lhs_type);
3400       debug_generic_expr (rhs1_type);
3401       return true;
3402     }
3403
3404   return false;
3405 }
3406
3407 /* Verify a gimple assignment statement STMT with a binary rhs.
3408    Returns true if anything is wrong.  */
3409
3410 static bool
3411 verify_gimple_assign_binary (gimple stmt)
3412 {
3413   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3414   tree lhs = gimple_assign_lhs (stmt);
3415   tree lhs_type = TREE_TYPE (lhs);
3416   tree rhs1 = gimple_assign_rhs1 (stmt);
3417   tree rhs1_type = TREE_TYPE (rhs1);
3418   tree rhs2 = gimple_assign_rhs2 (stmt);
3419   tree rhs2_type = TREE_TYPE (rhs2);
3420
3421   if (!is_gimple_reg (lhs))
3422     {
3423       error ("non-register as LHS of binary operation");
3424       return true;
3425     }
3426
3427   if (!is_gimple_val (rhs1)
3428       || !is_gimple_val (rhs2))
3429     {
3430       error ("invalid operands in binary operation");
3431       return true;
3432     }
3433
3434   /* First handle operations that involve different types.  */
3435   switch (rhs_code)
3436     {
3437     case COMPLEX_EXPR:
3438       {
3439         if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3440             || !(INTEGRAL_TYPE_P (rhs1_type)
3441                  || SCALAR_FLOAT_TYPE_P (rhs1_type))
3442             || !(INTEGRAL_TYPE_P (rhs2_type)
3443                  || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3444           {
3445             error ("type mismatch in complex expression");
3446             debug_generic_expr (lhs_type);
3447             debug_generic_expr (rhs1_type);
3448             debug_generic_expr (rhs2_type);
3449             return true;
3450           }
3451
3452         return false;
3453       }
3454
3455     case LSHIFT_EXPR:
3456     case RSHIFT_EXPR:
3457     case LROTATE_EXPR:
3458     case RROTATE_EXPR:
3459       {
3460         /* Shifts and rotates are ok on integral types, fixed point
3461            types and integer vector types.  */
3462         if ((!INTEGRAL_TYPE_P (rhs1_type)
3463              && !FIXED_POINT_TYPE_P (rhs1_type)
3464              && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3465                   && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3466             || (!INTEGRAL_TYPE_P (rhs2_type)
3467                 /* Vector shifts of vectors are also ok.  */
3468                 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3469                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3470                      && TREE_CODE (rhs2_type) == VECTOR_TYPE
3471                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3472             || !useless_type_conversion_p (lhs_type, rhs1_type))
3473           {
3474             error ("type mismatch in shift expression");
3475             debug_generic_expr (lhs_type);
3476             debug_generic_expr (rhs1_type);
3477             debug_generic_expr (rhs2_type);
3478             return true;
3479           }
3480
3481         return false;
3482       }
3483
3484     case VEC_LSHIFT_EXPR:
3485     case VEC_RSHIFT_EXPR:
3486       {
3487         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3488             || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3489                  || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3490                  || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3491                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3492             || (!INTEGRAL_TYPE_P (rhs2_type)
3493                 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3494                     || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3495             || !useless_type_conversion_p (lhs_type, rhs1_type))
3496           {
3497             error ("type mismatch in vector shift expression");
3498             debug_generic_expr (lhs_type);
3499             debug_generic_expr (rhs1_type);
3500             debug_generic_expr (rhs2_type);
3501             return true;
3502           }
3503         /* For shifting a vector of non-integral components we
3504            only allow shifting by a constant multiple of the element size.  */
3505         if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3506             && (TREE_CODE (rhs2) != INTEGER_CST
3507                 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3508                                            TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3509           {
3510             error ("non-element sized vector shift of floating point vector");
3511             return true;
3512           }
3513
3514         return false;
3515       }
3516
3517     case WIDEN_LSHIFT_EXPR:
3518       {
3519         if (!INTEGRAL_TYPE_P (lhs_type)
3520             || !INTEGRAL_TYPE_P (rhs1_type)
3521             || TREE_CODE (rhs2) != INTEGER_CST
3522             || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)))
3523           {
3524             error ("type mismatch in widening vector shift expression");
3525             debug_generic_expr (lhs_type);
3526             debug_generic_expr (rhs1_type);
3527             debug_generic_expr (rhs2_type);
3528             return true;
3529           }
3530
3531         return false;
3532       }
3533
3534     case VEC_WIDEN_LSHIFT_HI_EXPR:
3535     case VEC_WIDEN_LSHIFT_LO_EXPR:
3536       {
3537         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3538             || TREE_CODE (lhs_type) != VECTOR_TYPE
3539             || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3540             || !INTEGRAL_TYPE_P (TREE_TYPE (lhs_type))
3541             || TREE_CODE (rhs2) != INTEGER_CST
3542             || (2 * TYPE_PRECISION (TREE_TYPE (rhs1_type))
3543                 > TYPE_PRECISION (TREE_TYPE (lhs_type))))
3544           {
3545             error ("type mismatch in widening vector shift expression");
3546             debug_generic_expr (lhs_type);
3547             debug_generic_expr (rhs1_type);
3548             debug_generic_expr (rhs2_type);
3549             return true;
3550           }
3551
3552         return false;
3553       }
3554
3555     case PLUS_EXPR:
3556     case MINUS_EXPR:
3557       {
3558         /* We use regular PLUS_EXPR and MINUS_EXPR for vectors.
3559            ???  This just makes the checker happy and may not be what is
3560            intended.  */
3561         if (TREE_CODE (lhs_type) == VECTOR_TYPE
3562             && POINTER_TYPE_P (TREE_TYPE (lhs_type)))
3563           {
3564             if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3565                 || TREE_CODE (rhs2_type) != VECTOR_TYPE)
3566               {
3567                 error ("invalid non-vector operands to vector valued plus");
3568                 return true;
3569               }
3570             lhs_type = TREE_TYPE (lhs_type);
3571             rhs1_type = TREE_TYPE (rhs1_type);
3572             rhs2_type = TREE_TYPE (rhs2_type);
3573             /* PLUS_EXPR is commutative, so we might end up canonicalizing
3574                the pointer to 2nd place.  */
3575             if (POINTER_TYPE_P (rhs2_type))
3576               {
3577                 tree tem = rhs1_type;
3578                 rhs1_type = rhs2_type;
3579                 rhs2_type = tem;
3580               }
3581             goto do_pointer_plus_expr_check;
3582           }
3583         if (POINTER_TYPE_P (lhs_type)
3584             || POINTER_TYPE_P (rhs1_type)
3585             || POINTER_TYPE_P (rhs2_type))
3586           {
3587             error ("invalid (pointer) operands to plus/minus");
3588             return true;
3589           }
3590
3591         /* Continue with generic binary expression handling.  */
3592         break;
3593       }
3594
3595     case POINTER_PLUS_EXPR:
3596       {
3597 do_pointer_plus_expr_check:
3598         if (!POINTER_TYPE_P (rhs1_type)
3599             || !useless_type_conversion_p (lhs_type, rhs1_type)
3600             || !ptrofftype_p (rhs2_type))
3601           {
3602             error ("type mismatch in pointer plus expression");
3603             debug_generic_stmt (lhs_type);
3604             debug_generic_stmt (rhs1_type);
3605             debug_generic_stmt (rhs2_type);
3606             return true;
3607           }
3608
3609         return false;
3610       }
3611
3612     case TRUTH_ANDIF_EXPR:
3613     case TRUTH_ORIF_EXPR:
3614     case TRUTH_AND_EXPR:
3615     case TRUTH_OR_EXPR:
3616     case TRUTH_XOR_EXPR:
3617
3618       gcc_unreachable ();
3619
3620     case LT_EXPR:
3621     case LE_EXPR:
3622     case GT_EXPR:
3623     case GE_EXPR:
3624     case EQ_EXPR:
3625     case NE_EXPR:
3626     case UNORDERED_EXPR:
3627     case ORDERED_EXPR:
3628     case UNLT_EXPR:
3629     case UNLE_EXPR:
3630     case UNGT_EXPR:
3631     case UNGE_EXPR:
3632     case UNEQ_EXPR:
3633     case LTGT_EXPR:
3634       /* Comparisons are also binary, but the result type is not
3635          connected to the operand types.  */
3636       return verify_gimple_comparison (lhs_type, rhs1, rhs2);
3637
3638     case WIDEN_MULT_EXPR:
3639       if (TREE_CODE (lhs_type) != INTEGER_TYPE)
3640         return true;
3641       return ((2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type))
3642               || (TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type)));
3643
3644     case WIDEN_SUM_EXPR:
3645     case VEC_WIDEN_MULT_HI_EXPR:
3646     case VEC_WIDEN_MULT_LO_EXPR:
3647     case VEC_PACK_TRUNC_EXPR:
3648     case VEC_PACK_SAT_EXPR:
3649     case VEC_PACK_FIX_TRUNC_EXPR:
3650     case VEC_EXTRACT_EVEN_EXPR:
3651     case VEC_EXTRACT_ODD_EXPR:
3652     case VEC_INTERLEAVE_HIGH_EXPR:
3653     case VEC_INTERLEAVE_LOW_EXPR:
3654       /* FIXME.  */
3655       return false;
3656
3657     case MULT_EXPR:
3658     case TRUNC_DIV_EXPR:
3659     case CEIL_DIV_EXPR:
3660     case FLOOR_DIV_EXPR:
3661     case ROUND_DIV_EXPR:
3662     case TRUNC_MOD_EXPR:
3663     case CEIL_MOD_EXPR:
3664     case FLOOR_MOD_EXPR:
3665     case ROUND_MOD_EXPR:
3666     case RDIV_EXPR:
3667     case EXACT_DIV_EXPR:
3668     case MIN_EXPR:
3669     case MAX_EXPR:
3670     case BIT_IOR_EXPR:
3671     case BIT_XOR_EXPR:
3672     case BIT_AND_EXPR:
3673       /* Continue with generic binary expression handling.  */
3674       break;
3675
3676     default:
3677       gcc_unreachable ();
3678     }
3679
3680   if (!useless_type_conversion_p (lhs_type, rhs1_type)
3681       || !useless_type_conversion_p (lhs_type, rhs2_type))
3682     {
3683       error ("type mismatch in binary expression");
3684       debug_generic_stmt (lhs_type);
3685       debug_generic_stmt (rhs1_type);
3686       debug_generic_stmt (rhs2_type);
3687       return true;
3688     }
3689
3690   return false;
3691 }
3692
3693 /* Verify a gimple assignment statement STMT with a ternary rhs.
3694    Returns true if anything is wrong.  */
3695
3696 static bool
3697 verify_gimple_assign_ternary (gimple stmt)
3698 {
3699   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3700   tree lhs = gimple_assign_lhs (stmt);
3701   tree lhs_type = TREE_TYPE (lhs);
3702   tree rhs1 = gimple_assign_rhs1 (stmt);
3703   tree rhs1_type = TREE_TYPE (rhs1);
3704   tree rhs2 = gimple_assign_rhs2 (stmt);
3705   tree rhs2_type = TREE_TYPE (rhs2);
3706   tree rhs3 = gimple_assign_rhs3 (stmt);
3707   tree rhs3_type = TREE_TYPE (rhs3);
3708
3709   if (!is_gimple_reg (lhs))
3710     {
3711       error ("non-register as LHS of ternary operation");
3712       return true;
3713     }
3714
3715   if (((rhs_code == VEC_COND_EXPR || rhs_code == COND_EXPR)
3716        ? !is_gimple_condexpr (rhs1) : !is_gimple_val (rhs1))
3717       || !is_gimple_val (rhs2)
3718       || !is_gimple_val (rhs3))
3719     {
3720       error ("invalid operands in ternary operation");
3721       return true;
3722     }
3723
3724   /* First handle operations that involve different types.  */
3725   switch (rhs_code)
3726     {
3727     case WIDEN_MULT_PLUS_EXPR:
3728     case WIDEN_MULT_MINUS_EXPR:
3729       if ((!INTEGRAL_TYPE_P (rhs1_type)
3730            && !FIXED_POINT_TYPE_P (rhs1_type))
3731           || !useless_type_conversion_p (rhs1_type, rhs2_type)
3732           || !useless_type_conversion_p (lhs_type, rhs3_type)
3733           || 2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)
3734           || TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type))
3735         {
3736           error ("type mismatch in widening multiply-accumulate expression");
3737           debug_generic_expr (lhs_type);
3738           debug_generic_expr (rhs1_type);
3739           debug_generic_expr (rhs2_type);
3740           debug_generic_expr (rhs3_type);
3741           return true;
3742         }
3743       break;
3744
3745     case FMA_EXPR:
3746       if (!useless_type_conversion_p (lhs_type, rhs1_type)
3747           || !useless_type_conversion_p (lhs_type, rhs2_type)
3748           || !useless_type_conversion_p (lhs_type, rhs3_type))
3749         {
3750           error ("type mismatch in fused multiply-add expression");
3751           debug_generic_expr (lhs_type);
3752           debug_generic_expr (rhs1_type);
3753           debug_generic_expr (rhs2_type);
3754           debug_generic_expr (rhs3_type);
3755           return true;
3756         }
3757       break;
3758
3759     case COND_EXPR:
3760     case VEC_COND_EXPR:
3761       if (!useless_type_conversion_p (lhs_type, rhs2_type)
3762           || !useless_type_conversion_p (lhs_type, rhs3_type))
3763         {
3764           error ("type mismatch in conditional expression");
3765           debug_generic_expr (lhs_type);
3766           debug_generic_expr (rhs2_type);
3767           debug_generic_expr (rhs3_type);
3768           return true;
3769         }
3770       break;
3771
3772     case VEC_PERM_EXPR:
3773       if (!useless_type_conversion_p (lhs_type, rhs1_type)
3774           || !useless_type_conversion_p (lhs_type, rhs2_type))
3775         {
3776           error ("type mismatch in vector permute expression");
3777           debug_generic_expr (lhs_type);
3778           debug_generic_expr (rhs1_type);
3779           debug_generic_expr (rhs2_type);
3780           debug_generic_expr (rhs3_type);
3781           return true;
3782         }
3783
3784       if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3785           || TREE_CODE (rhs2_type) != VECTOR_TYPE
3786           || TREE_CODE (rhs3_type) != VECTOR_TYPE)
3787         {
3788           error ("vector types expected in vector permute expression");
3789           debug_generic_expr (lhs_type);
3790           debug_generic_expr (rhs1_type);
3791           debug_generic_expr (rhs2_type);
3792           debug_generic_expr (rhs3_type);
3793           return true;
3794         }
3795
3796       if (TYPE_VECTOR_SUBPARTS (rhs1_type) != TYPE_VECTOR_SUBPARTS (rhs2_type)
3797           || TYPE_VECTOR_SUBPARTS (rhs2_type)
3798              != TYPE_VECTOR_SUBPARTS (rhs3_type)
3799           || TYPE_VECTOR_SUBPARTS (rhs3_type)
3800              != TYPE_VECTOR_SUBPARTS (lhs_type))
3801         {
3802           error ("vectors with different element number found "
3803                  "in vector permute expression");
3804           debug_generic_expr (lhs_type);
3805           debug_generic_expr (rhs1_type);
3806           debug_generic_expr (rhs2_type);
3807           debug_generic_expr (rhs3_type);
3808           return true;
3809         }
3810
3811       if (TREE_CODE (TREE_TYPE (rhs3_type)) != INTEGER_TYPE
3812           || GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs3_type)))
3813              != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1_type))))
3814         {
3815           error ("invalid mask type in vector permute expression");
3816           debug_generic_expr (lhs_type);
3817           debug_generic_expr (rhs1_type);
3818           debug_generic_expr (rhs2_type);
3819           debug_generic_expr (rhs3_type);
3820           return true;
3821         }
3822
3823       return false;
3824
3825     case DOT_PROD_EXPR:
3826     case REALIGN_LOAD_EXPR:
3827       /* FIXME.  */
3828       return false;
3829
3830     default:
3831       gcc_unreachable ();
3832     }
3833   return false;
3834 }
3835
3836 /* Verify a gimple assignment statement STMT with a single rhs.
3837    Returns true if anything is wrong.  */
3838
3839 static bool
3840 verify_gimple_assign_single (gimple stmt)
3841 {
3842   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3843   tree lhs = gimple_assign_lhs (stmt);
3844   tree lhs_type = TREE_TYPE (lhs);
3845   tree rhs1 = gimple_assign_rhs1 (stmt);
3846   tree rhs1_type = TREE_TYPE (rhs1);
3847   bool res = false;
3848
3849   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3850     {
3851       error ("non-trivial conversion at assignment");
3852       debug_generic_expr (lhs_type);
3853       debug_generic_expr (rhs1_type);
3854       return true;
3855     }
3856
3857   if (handled_component_p (lhs))
3858     res |= verify_types_in_gimple_reference (lhs, true);
3859
3860   /* Special codes we cannot handle via their class.  */
3861   switch (rhs_code)
3862     {
3863     case ADDR_EXPR:
3864       {
3865         tree op = TREE_OPERAND (rhs1, 0);
3866         if (!is_gimple_addressable (op))
3867           {
3868             error ("invalid operand in unary expression");
3869             return true;
3870           }
3871
3872         /* Technically there is no longer a need for matching types, but
3873            gimple hygiene asks for this check.  In LTO we can end up
3874            combining incompatible units and thus end up with addresses
3875            of globals that change their type to a common one.  */
3876         if (!in_lto_p
3877             && !types_compatible_p (TREE_TYPE (op),
3878                                     TREE_TYPE (TREE_TYPE (rhs1)))
3879             && !one_pointer_to_useless_type_conversion_p (TREE_TYPE (rhs1),
3880                                                           TREE_TYPE (op)))
3881           {
3882             error ("type mismatch in address expression");
3883             debug_generic_stmt (TREE_TYPE (rhs1));
3884             debug_generic_stmt (TREE_TYPE (op));
3885             return true;
3886           }
3887
3888         return verify_types_in_gimple_reference (op, true);
3889       }
3890
3891     /* tcc_reference  */
3892     case INDIRECT_REF:
3893       error ("INDIRECT_REF in gimple IL");
3894       return true;
3895
3896     case COMPONENT_REF:
3897     case BIT_FIELD_REF:
3898     case ARRAY_REF:
3899     case ARRAY_RANGE_REF:
3900     case VIEW_CONVERT_EXPR:
3901     case REALPART_EXPR:
3902     case IMAGPART_EXPR:
3903     case TARGET_MEM_REF:
3904     case MEM_REF:
3905       if (!is_gimple_reg (lhs)
3906           && is_gimple_reg_type (TREE_TYPE (lhs)))
3907         {
3908           error ("invalid rhs for gimple memory store");
3909           debug_generic_stmt (lhs);
3910           debug_generic_stmt (rhs1);
3911           return true;
3912         }
3913       return res || verify_types_in_gimple_reference (rhs1, false);
3914
3915     /* tcc_constant  */
3916     case SSA_NAME:
3917     case INTEGER_CST:
3918     case REAL_CST:
3919     case FIXED_CST:
3920     case COMPLEX_CST:
3921     case VECTOR_CST:
3922     case STRING_CST:
3923       return res;
3924
3925     /* tcc_declaration  */
3926     case CONST_DECL:
3927       return res;
3928     case VAR_DECL:
3929     case PARM_DECL:
3930       if (!is_gimple_reg (lhs)
3931           && !is_gimple_reg (rhs1)
3932           && is_gimple_reg_type (TREE_TYPE (lhs)))
3933         {
3934           error ("invalid rhs for gimple memory store");
3935           debug_generic_stmt (lhs);
3936           debug_generic_stmt (rhs1);
3937           return true;
3938         }
3939       return res;
3940
3941     case CONSTRUCTOR:
3942     case OBJ_TYPE_REF:
3943     case ASSERT_EXPR:
3944     case WITH_SIZE_EXPR:
3945       /* FIXME.  */
3946       return res;
3947
3948     default:;
3949     }
3950
3951   return res;
3952 }
3953
3954 /* Verify the contents of a GIMPLE_ASSIGN STMT.  Returns true when there
3955    is a problem, otherwise false.  */
3956
3957 static bool
3958 verify_gimple_assign (gimple stmt)
3959 {
3960   switch (gimple_assign_rhs_class (stmt))
3961     {
3962     case GIMPLE_SINGLE_RHS:
3963       return verify_gimple_assign_single (stmt);
3964
3965     case GIMPLE_UNARY_RHS:
3966       return verify_gimple_assign_unary (stmt);
3967
3968     case GIMPLE_BINARY_RHS:
3969       return verify_gimple_assign_binary (stmt);
3970
3971     case GIMPLE_TERNARY_RHS:
3972       return verify_gimple_assign_ternary (stmt);
3973
3974     default:
3975       gcc_unreachable ();
3976     }
3977 }
3978
3979 /* Verify the contents of a GIMPLE_RETURN STMT.  Returns true when there
3980    is a problem, otherwise false.  */
3981
3982 static bool
3983 verify_gimple_return (gimple stmt)
3984 {
3985   tree op = gimple_return_retval (stmt);
3986   tree restype = TREE_TYPE (TREE_TYPE (cfun->decl));
3987
3988   /* We cannot test for present return values as we do not fix up missing
3989      return values from the original source.  */
3990   if (op == NULL)
3991     return false;
3992
3993   if (!is_gimple_val (op)
3994       && TREE_CODE (op) != RESULT_DECL)
3995     {
3996       error ("invalid operand in return statement");
3997       debug_generic_stmt (op);
3998       return true;
3999     }
4000
4001   if ((TREE_CODE (op) == RESULT_DECL
4002        && DECL_BY_REFERENCE (op))
4003       || (TREE_CODE (op) == SSA_NAME
4004           && TREE_CODE (SSA_NAME_VAR (op)) == RESULT_DECL
4005           && DECL_BY_REFERENCE (SSA_NAME_VAR (op))))
4006     op = TREE_TYPE (op);
4007
4008   if (!useless_type_conversion_p (restype, TREE_TYPE (op)))
4009     {
4010       error ("invalid conversion in return statement");
4011       debug_generic_stmt (restype);
4012       debug_generic_stmt (TREE_TYPE (op));
4013       return true;
4014     }
4015
4016   return false;
4017 }
4018
4019
4020 /* Verify the contents of a GIMPLE_GOTO STMT.  Returns true when there
4021    is a problem, otherwise false.  */
4022
4023 static bool
4024 verify_gimple_goto (gimple stmt)
4025 {
4026   tree dest = gimple_goto_dest (stmt);
4027
4028   /* ???  We have two canonical forms of direct goto destinations, a
4029      bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL.  */
4030   if (TREE_CODE (dest) != LABEL_DECL
4031       && (!is_gimple_val (dest)
4032           || !POINTER_TYPE_P (TREE_TYPE (dest))))
4033     {
4034       error ("goto destination is neither a label nor a pointer");
4035       return true;
4036     }
4037
4038   return false;
4039 }
4040
4041 /* Verify the contents of a GIMPLE_SWITCH STMT.  Returns true when there
4042    is a problem, otherwise false.  */
4043
4044 static bool
4045 verify_gimple_switch (gimple stmt)
4046 {
4047   if (!is_gimple_val (gimple_switch_index (stmt)))
4048     {
4049       error ("invalid operand to switch statement");
4050       debug_generic_stmt (gimple_switch_index (stmt));
4051       return true;
4052     }
4053
4054   return false;
4055 }
4056
4057
4058 /* Verify a gimple debug statement STMT.
4059    Returns true if anything is wrong.  */
4060
4061 static bool
4062 verify_gimple_debug (gimple stmt ATTRIBUTE_UNUSED)
4063 {
4064   /* There isn't much that could be wrong in a gimple debug stmt.  A
4065      gimple debug bind stmt, for example, maps a tree, that's usually
4066      a VAR_DECL or a PARM_DECL, but that could also be some scalarized
4067      component or member of an aggregate type, to another tree, that
4068      can be an arbitrary expression.  These stmts expand into debug
4069      insns, and are converted to debug notes by var-tracking.c.  */
4070   return false;
4071 }
4072
4073 /* Verify a gimple label statement STMT.
4074    Returns true if anything is wrong.  */
4075
4076 static bool
4077 verify_gimple_label (gimple stmt)
4078 {
4079   tree decl = gimple_label_label (stmt);
4080   int uid;
4081   bool err = false;
4082
4083   if (TREE_CODE (decl) != LABEL_DECL)
4084     return true;
4085
4086   uid = LABEL_DECL_UID (decl);
4087   if (cfun->cfg
4088       && (uid == -1
4089           || VEC_index (basic_block,
4090                         label_to_block_map, uid) != gimple_bb (stmt)))
4091     {
4092       error ("incorrect entry in label_to_block_map");
4093       err |= true;
4094     }
4095
4096   uid = EH_LANDING_PAD_NR (decl);
4097   if (uid)
4098     {
4099       eh_landing_pad lp = get_eh_landing_pad_from_number (uid);
4100       if (decl != lp->post_landing_pad)
4101         {
4102           error ("incorrect setting of landing pad number");
4103           err |= true;
4104         }
4105     }
4106
4107   return err;
4108 }
4109
4110 /* Verify the GIMPLE statement STMT.  Returns true if there is an
4111    error, otherwise false.  */
4112
4113 static bool
4114 verify_gimple_stmt (gimple stmt)
4115 {
4116   switch (gimple_code (stmt))
4117     {
4118     case GIMPLE_ASSIGN:
4119       return verify_gimple_assign (stmt);
4120
4121     case GIMPLE_LABEL:
4122       return verify_gimple_label (stmt);
4123
4124     case GIMPLE_CALL:
4125       return verify_gimple_call (stmt);
4126
4127     case GIMPLE_COND:
4128       if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
4129         {
4130           error ("invalid comparison code in gimple cond");
4131           return true;
4132         }
4133       if (!(!gimple_cond_true_label (stmt)
4134             || TREE_CODE (gimple_cond_true_label (stmt)) == LABEL_DECL)
4135           || !(!gimple_cond_false_label (stmt)
4136                || TREE_CODE (gimple_cond_false_label (stmt)) == LABEL_DECL))
4137         {
4138           error ("invalid labels in gimple cond");
4139           return true;
4140         }
4141
4142       return verify_gimple_comparison (boolean_type_node,
4143                                        gimple_cond_lhs (stmt),
4144                                        gimple_cond_rhs (stmt));
4145
4146     case GIMPLE_GOTO:
4147       return verify_gimple_goto (stmt);
4148
4149     case GIMPLE_SWITCH:
4150       return verify_gimple_switch (stmt);
4151
4152     case GIMPLE_RETURN:
4153       return verify_gimple_return (stmt);
4154
4155     case GIMPLE_ASM:
4156       return false;
4157
4158     /* Tuples that do not have tree operands.  */
4159     case GIMPLE_NOP:
4160     case GIMPLE_PREDICT:
4161     case GIMPLE_RESX:
4162     case GIMPLE_EH_DISPATCH:
4163     case GIMPLE_EH_MUST_NOT_THROW:
4164       return false;
4165
4166     CASE_GIMPLE_OMP:
4167       /* OpenMP directives are validated by the FE and never operated
4168          on by the optimizers.  Furthermore, GIMPLE_OMP_FOR may contain
4169          non-gimple expressions when the main index variable has had
4170          its address taken.  This does not affect the loop itself
4171          because the header of an GIMPLE_OMP_FOR is merely used to determine
4172          how to setup the parallel iteration.  */
4173       return false;
4174
4175     case GIMPLE_DEBUG:
4176       return verify_gimple_debug (stmt);
4177
4178     default:
4179       gcc_unreachable ();
4180     }
4181 }
4182
4183 /* Verify the contents of a GIMPLE_PHI.  Returns true if there is a problem,
4184    and false otherwise.  */
4185
4186 static bool
4187 verify_gimple_phi (gimple phi)
4188 {
4189   bool err = false;
4190   unsigned i;
4191   tree phi_result = gimple_phi_result (phi);
4192   bool virtual_p;
4193
4194   if (!phi_result)
4195     {
4196       error ("invalid PHI result");
4197       return true;
4198     }
4199
4200   virtual_p = !is_gimple_reg (phi_result);
4201   if (TREE_CODE (phi_result) != SSA_NAME
4202       || (virtual_p
4203           && SSA_NAME_VAR (phi_result) != gimple_vop (cfun)))
4204     {
4205       error ("invalid PHI result");
4206       err = true;
4207     }
4208
4209   for (i = 0; i < gimple_phi_num_args (phi); i++)
4210     {
4211       tree t = gimple_phi_arg_def (phi, i);
4212
4213       if (!t)
4214         {
4215           error ("missing PHI def");
4216           err |= true;
4217           continue;
4218         }
4219       /* Addressable variables do have SSA_NAMEs but they
4220          are not considered gimple values.  */
4221       else if ((TREE_CODE (t) == SSA_NAME
4222                 && virtual_p != !is_gimple_reg (t))
4223                || (virtual_p
4224                    && (TREE_CODE (t) != SSA_NAME
4225                        || SSA_NAME_VAR (t) != gimple_vop (cfun)))
4226                || (!virtual_p
4227                    && !is_gimple_val (t)))
4228         {
4229           error ("invalid PHI argument");
4230           debug_generic_expr (t);
4231           err |= true;
4232         }
4233 #ifdef ENABLE_TYPES_CHECKING
4234       if (!useless_type_conversion_p (TREE_TYPE (phi_result), TREE_TYPE (t)))
4235         {
4236           error ("incompatible types in PHI argument %u", i);
4237           debug_generic_stmt (TREE_TYPE (phi_result));
4238           debug_generic_stmt (TREE_TYPE (t));
4239           err |= true;
4240         }
4241 #endif
4242     }
4243
4244   return err;
4245 }
4246
4247 /* Verify the GIMPLE statements inside the sequence STMTS.  */
4248
4249 static bool
4250 verify_gimple_in_seq_2 (gimple_seq stmts)
4251 {
4252   gimple_stmt_iterator ittr;
4253   bool err = false;
4254
4255   for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr))
4256     {
4257       gimple stmt = gsi_stmt (ittr);
4258
4259       switch (gimple_code (stmt))
4260         {
4261         case GIMPLE_BIND:
4262           err |= verify_gimple_in_seq_2 (gimple_bind_body (stmt));
4263           break;
4264
4265         case GIMPLE_TRY:
4266           err |= verify_gimple_in_seq_2 (gimple_try_eval (stmt));
4267           err |= verify_gimple_in_seq_2 (gimple_try_cleanup (stmt));
4268           break;
4269
4270         case GIMPLE_EH_FILTER:
4271           err |= verify_gimple_in_seq_2 (gimple_eh_filter_failure (stmt));
4272           break;
4273
4274         case GIMPLE_CATCH:
4275           err |= verify_gimple_in_seq_2 (gimple_catch_handler (stmt));
4276           break;
4277
4278         default:
4279           {
4280             bool err2 = verify_gimple_stmt (stmt);
4281             if (err2)
4282               debug_gimple_stmt (stmt);
4283             err |= err2;
4284           }
4285         }
4286     }
4287
4288   return err;
4289 }
4290
4291
4292 /* Verify the GIMPLE statements inside the statement list STMTS.  */
4293
4294 DEBUG_FUNCTION void
4295 verify_gimple_in_seq (gimple_seq stmts)
4296 {
4297   timevar_push (TV_TREE_STMT_VERIFY);
4298   if (verify_gimple_in_seq_2 (stmts))
4299     internal_error ("verify_gimple failed");
4300   timevar_pop (TV_TREE_STMT_VERIFY);
4301 }
4302
4303 /* Return true when the T can be shared.  */
4304
4305 bool
4306 tree_node_can_be_shared (tree t)
4307 {
4308   if (IS_TYPE_OR_DECL_P (t)
4309       || is_gimple_min_invariant (t)
4310       || TREE_CODE (t) == SSA_NAME
4311       || t == error_mark_node
4312       || TREE_CODE (t) == IDENTIFIER_NODE)
4313     return true;
4314
4315   if (TREE_CODE (t) == CASE_LABEL_EXPR)
4316     return true;
4317
4318   while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
4319            && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
4320          || TREE_CODE (t) == COMPONENT_REF
4321          || TREE_CODE (t) == REALPART_EXPR
4322          || TREE_CODE (t) == IMAGPART_EXPR)
4323     t = TREE_OPERAND (t, 0);
4324
4325   if (DECL_P (t))
4326     return true;
4327
4328   return false;
4329 }
4330
4331 /* Called via walk_gimple_stmt.  Verify tree sharing.  */
4332
4333 static tree
4334 verify_node_sharing (tree *tp, int *walk_subtrees, void *data)
4335 {
4336   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
4337   struct pointer_set_t *visited = (struct pointer_set_t *) wi->info;
4338
4339   if (tree_node_can_be_shared (*tp))
4340     {
4341       *walk_subtrees = false;
4342       return NULL;
4343     }
4344
4345   if (pointer_set_insert (visited, *tp))
4346     return *tp;
4347
4348   return NULL;
4349 }
4350
4351 static bool eh_error_found;
4352 static int
4353 verify_eh_throw_stmt_node (void **slot, void *data)
4354 {
4355   struct throw_stmt_node *node = (struct throw_stmt_node *)*slot;
4356   struct pointer_set_t *visited = (struct pointer_set_t *) data;
4357
4358   if (!pointer_set_contains (visited, node->stmt))
4359     {
4360       error ("dead STMT in EH table");
4361       debug_gimple_stmt (node->stmt);
4362       eh_error_found = true;
4363     }
4364   return 1;
4365 }
4366
4367 /* Verify the GIMPLE statements in the CFG of FN.  */
4368
4369 DEBUG_FUNCTION void
4370 verify_gimple_in_cfg (struct function *fn)
4371 {
4372   basic_block bb;
4373   bool err = false;
4374   struct pointer_set_t *visited, *visited_stmts;
4375
4376   timevar_push (TV_TREE_STMT_VERIFY);
4377   visited = pointer_set_create ();
4378   visited_stmts = pointer_set_create ();
4379
4380   FOR_EACH_BB_FN (bb, fn)
4381     {
4382       gimple_stmt_iterator gsi;
4383
4384       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4385         {
4386           gimple phi = gsi_stmt (gsi);
4387           bool err2 = false;
4388           unsigned i;
4389
4390           pointer_set_insert (visited_stmts, phi);
4391
4392           if (gimple_bb (phi) != bb)
4393             {
4394               error ("gimple_bb (phi) is set to a wrong basic block");
4395               err2 = true;
4396             }
4397
4398           err2 |= verify_gimple_phi (phi);
4399
4400           for (i = 0; i < gimple_phi_num_args (phi); i++)
4401             {
4402               tree arg = gimple_phi_arg_def (phi, i);
4403               tree addr = walk_tree (&arg, verify_node_sharing, visited, NULL);
4404               if (addr)
4405                 {
4406                   error ("incorrect sharing of tree nodes");
4407                   debug_generic_expr (addr);
4408                   err2 |= true;
4409                 }
4410             }
4411
4412           if (err2)
4413             debug_gimple_stmt (phi);
4414           err |= err2;
4415         }
4416
4417       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4418         {
4419           gimple stmt = gsi_stmt (gsi);
4420           bool err2 = false;
4421           struct walk_stmt_info wi;
4422           tree addr;
4423           int lp_nr;
4424
4425           pointer_set_insert (visited_stmts, stmt);
4426
4427           if (gimple_bb (stmt) != bb)
4428             {
4429               error ("gimple_bb (stmt) is set to a wrong basic block");
4430               err2 = true;
4431             }
4432
4433           err2 |= verify_gimple_stmt (stmt);
4434
4435           memset (&wi, 0, sizeof (wi));
4436           wi.info = (void *) visited;
4437           addr = walk_gimple_op (stmt, verify_node_sharing, &wi);
4438           if (addr)
4439             {
4440               error ("incorrect sharing of tree nodes");
4441               debug_generic_expr (addr);
4442               err2 |= true;
4443             }
4444
4445           /* ???  Instead of not checking these stmts at all the walker
4446              should know its context via wi.  */
4447           if (!is_gimple_debug (stmt)
4448               && !is_gimple_omp (stmt))
4449             {
4450               memset (&wi, 0, sizeof (wi));
4451               addr = walk_gimple_op (stmt, verify_expr, &wi);
4452               if (addr)
4453                 {
4454                   debug_generic_expr (addr);
4455                   inform (gimple_location (stmt), "in statement");
4456                   err2 |= true;
4457                 }
4458             }
4459
4460           /* If the statement is marked as part of an EH region, then it is
4461              expected that the statement could throw.  Verify that when we
4462              have optimizations that simplify statements such that we prove
4463              that they cannot throw, that we update other data structures
4464              to match.  */
4465           lp_nr = lookup_stmt_eh_lp (stmt);
4466           if (lp_nr != 0)
4467             {
4468               if (!stmt_could_throw_p (stmt))
4469                 {
4470                   error ("statement marked for throw, but doesn%'t");
4471                   err2 |= true;
4472                 }
4473               else if (lp_nr > 0
4474                        && !gsi_one_before_end_p (gsi)
4475                        && stmt_can_throw_internal (stmt))
4476                 {
4477                   error ("statement marked for throw in middle of block");
4478                   err2 |= true;
4479                 }
4480             }
4481
4482           if (err2)
4483             debug_gimple_stmt (stmt);
4484           err |= err2;
4485         }
4486     }
4487
4488   eh_error_found = false;
4489   if (get_eh_throw_stmt_table (cfun))
4490     htab_traverse (get_eh_throw_stmt_table (cfun),
4491                    verify_eh_throw_stmt_node,
4492                    visited_stmts);
4493
4494   if (err || eh_error_found)
4495     internal_error ("verify_gimple failed");
4496
4497   pointer_set_destroy (visited);
4498   pointer_set_destroy (visited_stmts);
4499   verify_histograms ();
4500   timevar_pop (TV_TREE_STMT_VERIFY);
4501 }
4502
4503
4504 /* Verifies that the flow information is OK.  */
4505
4506 static int
4507 gimple_verify_flow_info (void)
4508 {
4509   int err = 0;
4510   basic_block bb;
4511   gimple_stmt_iterator gsi;
4512   gimple stmt;
4513   edge e;
4514   edge_iterator ei;
4515
4516   if (ENTRY_BLOCK_PTR->il.gimple)
4517     {
4518       error ("ENTRY_BLOCK has IL associated with it");
4519       err = 1;
4520     }
4521
4522   if (EXIT_BLOCK_PTR->il.gimple)
4523     {
4524       error ("EXIT_BLOCK has IL associated with it");
4525       err = 1;
4526     }
4527
4528   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
4529     if (e->flags & EDGE_FALLTHRU)
4530       {
4531         error ("fallthru to exit from bb %d", e->src->index);
4532         err = 1;
4533       }
4534
4535   FOR_EACH_BB (bb)
4536     {
4537       bool found_ctrl_stmt = false;
4538
4539       stmt = NULL;
4540
4541       /* Skip labels on the start of basic block.  */
4542       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4543         {
4544           tree label;
4545           gimple prev_stmt = stmt;
4546
4547           stmt = gsi_stmt (gsi);
4548
4549           if (gimple_code (stmt) != GIMPLE_LABEL)
4550             break;
4551
4552           label = gimple_label_label (stmt);
4553           if (prev_stmt && DECL_NONLOCAL (label))
4554             {
4555               error ("nonlocal label ");
4556               print_generic_expr (stderr, label, 0);
4557               fprintf (stderr, " is not first in a sequence of labels in bb %d",
4558                        bb->index);
4559               err = 1;
4560             }
4561
4562           if (prev_stmt && EH_LANDING_PAD_NR (label) != 0)
4563             {
4564               error ("EH landing pad 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 (label_to_block (label) != bb)
4572             {
4573               error ("label ");
4574               print_generic_expr (stderr, label, 0);
4575               fprintf (stderr, " to block does not match in bb %d",
4576                        bb->index);
4577               err = 1;
4578             }
4579
4580           if (decl_function_context (label) != current_function_decl)
4581             {
4582               error ("label ");
4583               print_generic_expr (stderr, label, 0);
4584               fprintf (stderr, " has incorrect context in bb %d",
4585                        bb->index);
4586               err = 1;
4587             }
4588         }
4589
4590       /* Verify that body of basic block BB is free of control flow.  */
4591       for (; !gsi_end_p (gsi); gsi_next (&gsi))
4592         {
4593           gimple stmt = gsi_stmt (gsi);
4594
4595           if (found_ctrl_stmt)
4596             {
4597               error ("control flow in the middle of basic block %d",
4598                      bb->index);
4599               err = 1;
4600             }
4601
4602           if (stmt_ends_bb_p (stmt))
4603             found_ctrl_stmt = true;
4604
4605           if (gimple_code (stmt) == GIMPLE_LABEL)
4606             {
4607               error ("label ");
4608               print_generic_expr (stderr, gimple_label_label (stmt), 0);
4609               fprintf (stderr, " in the middle of basic block %d", bb->index);
4610               err = 1;
4611             }
4612         }
4613
4614       gsi = gsi_last_bb (bb);
4615       if (gsi_end_p (gsi))
4616         continue;
4617
4618       stmt = gsi_stmt (gsi);
4619
4620       if (gimple_code (stmt) == GIMPLE_LABEL)
4621         continue;
4622
4623       err |= verify_eh_edges (stmt);
4624
4625       if (is_ctrl_stmt (stmt))
4626         {
4627           FOR_EACH_EDGE (e, ei, bb->succs)
4628             if (e->flags & EDGE_FALLTHRU)
4629               {
4630                 error ("fallthru edge after a control statement in bb %d",
4631                        bb->index);
4632                 err = 1;
4633               }
4634         }
4635
4636       if (gimple_code (stmt) != GIMPLE_COND)
4637         {
4638           /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set
4639              after anything else but if statement.  */
4640           FOR_EACH_EDGE (e, ei, bb->succs)
4641             if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
4642               {
4643                 error ("true/false edge after a non-GIMPLE_COND in bb %d",
4644                        bb->index);
4645                 err = 1;
4646               }
4647         }
4648
4649       switch (gimple_code (stmt))
4650         {
4651         case GIMPLE_COND:
4652           {
4653             edge true_edge;
4654             edge false_edge;
4655
4656             extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
4657
4658             if (!true_edge
4659                 || !false_edge
4660                 || !(true_edge->flags & EDGE_TRUE_VALUE)
4661                 || !(false_edge->flags & EDGE_FALSE_VALUE)
4662                 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4663                 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL))
4664                 || EDGE_COUNT (bb->succs) >= 3)
4665               {
4666                 error ("wrong outgoing edge flags at end of bb %d",
4667                        bb->index);
4668                 err = 1;
4669               }
4670           }
4671           break;
4672
4673         case GIMPLE_GOTO:
4674           if (simple_goto_p (stmt))
4675             {
4676               error ("explicit goto at end of bb %d", bb->index);
4677               err = 1;
4678             }
4679           else
4680             {
4681               /* FIXME.  We should double check that the labels in the
4682                  destination blocks have their address taken.  */
4683               FOR_EACH_EDGE (e, ei, bb->succs)
4684                 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE
4685                                  | EDGE_FALSE_VALUE))
4686                     || !(e->flags & EDGE_ABNORMAL))
4687                   {
4688                     error ("wrong outgoing edge flags at end of bb %d",
4689                            bb->index);
4690                     err = 1;
4691                   }
4692             }
4693           break;
4694
4695         case GIMPLE_CALL:
4696           if (!gimple_call_builtin_p (stmt, BUILT_IN_RETURN))
4697             break;
4698           /* ... fallthru ... */
4699         case GIMPLE_RETURN:
4700           if (!single_succ_p (bb)
4701               || (single_succ_edge (bb)->flags
4702                   & (EDGE_FALLTHRU | EDGE_ABNORMAL
4703                      | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4704             {
4705               error ("wrong outgoing edge flags at end of bb %d", bb->index);
4706               err = 1;
4707             }
4708           if (single_succ (bb) != EXIT_BLOCK_PTR)
4709             {
4710               error ("return edge does not point to exit in bb %d",
4711                      bb->index);
4712               err = 1;
4713             }
4714           break;
4715
4716         case GIMPLE_SWITCH:
4717           {
4718             tree prev;
4719             edge e;
4720             size_t i, n;
4721
4722             n = gimple_switch_num_labels (stmt);
4723
4724             /* Mark all the destination basic blocks.  */
4725             for (i = 0; i < n; ++i)
4726               {
4727                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4728                 basic_block label_bb = label_to_block (lab);
4729                 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1);
4730                 label_bb->aux = (void *)1;
4731               }
4732
4733             /* Verify that the case labels are sorted.  */
4734             prev = gimple_switch_label (stmt, 0);
4735             for (i = 1; i < n; ++i)
4736               {
4737                 tree c = gimple_switch_label (stmt, i);
4738                 if (!CASE_LOW (c))
4739                   {
4740                     error ("found default case not at the start of "
4741                            "case vector");
4742                     err = 1;
4743                     continue;
4744                   }
4745                 if (CASE_LOW (prev)
4746                     && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
4747                   {
4748                     error ("case labels not sorted: ");
4749                     print_generic_expr (stderr, prev, 0);
4750                     fprintf (stderr," is greater than ");
4751                     print_generic_expr (stderr, c, 0);
4752                     fprintf (stderr," but comes before it.\n");
4753                     err = 1;
4754                   }
4755                 prev = c;
4756               }
4757             /* VRP will remove the default case if it can prove it will
4758                never be executed.  So do not verify there always exists
4759                a default case here.  */
4760
4761             FOR_EACH_EDGE (e, ei, bb->succs)
4762               {
4763                 if (!e->dest->aux)
4764                   {
4765                     error ("extra outgoing edge %d->%d",
4766                            bb->index, e->dest->index);
4767                     err = 1;
4768                   }
4769
4770                 e->dest->aux = (void *)2;
4771                 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL
4772                                  | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
4773                   {
4774                     error ("wrong outgoing edge flags at end of bb %d",
4775                            bb->index);
4776                     err = 1;
4777                   }
4778               }
4779
4780             /* Check that we have all of them.  */
4781             for (i = 0; i < n; ++i)
4782               {
4783                 tree lab = CASE_LABEL (gimple_switch_label (stmt, i));
4784                 basic_block label_bb = label_to_block (lab);
4785
4786                 if (label_bb->aux != (void *)2)
4787                   {
4788                     error ("missing edge %i->%i", bb->index, label_bb->index);
4789                     err = 1;
4790                   }
4791               }
4792
4793             FOR_EACH_EDGE (e, ei, bb->succs)
4794               e->dest->aux = (void *)0;
4795           }
4796           break;
4797
4798         case GIMPLE_EH_DISPATCH:
4799           err |= verify_eh_dispatch_edge (stmt);
4800           break;
4801
4802         default:
4803           break;
4804         }
4805     }
4806
4807   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
4808     verify_dominators (CDI_DOMINATORS);
4809
4810   return err;
4811 }
4812
4813
4814 /* Updates phi nodes after creating a forwarder block joined
4815    by edge FALLTHRU.  */
4816
4817 static void
4818 gimple_make_forwarder_block (edge fallthru)
4819 {
4820   edge e;
4821   edge_iterator ei;
4822   basic_block dummy, bb;
4823   tree var;
4824   gimple_stmt_iterator gsi;
4825
4826   dummy = fallthru->src;
4827   bb = fallthru->dest;
4828
4829   if (single_pred_p (bb))
4830     return;
4831
4832   /* If we redirected a branch we must create new PHI nodes at the
4833      start of BB.  */
4834   for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi))
4835     {
4836       gimple phi, new_phi;
4837
4838       phi = gsi_stmt (gsi);
4839       var = gimple_phi_result (phi);
4840       new_phi = create_phi_node (var, bb);
4841       SSA_NAME_DEF_STMT (var) = new_phi;
4842       gimple_phi_set_result (phi, make_ssa_name (SSA_NAME_VAR (var), phi));
4843       add_phi_arg (new_phi, gimple_phi_result (phi), fallthru,
4844                    UNKNOWN_LOCATION);
4845     }
4846
4847   /* Add the arguments we have stored on edges.  */
4848   FOR_EACH_EDGE (e, ei, bb->preds)
4849     {
4850       if (e == fallthru)
4851         continue;
4852
4853       flush_pending_stmts (e);
4854     }
4855 }
4856
4857
4858 /* Return a non-special label in the head of basic block BLOCK.
4859    Create one if it doesn't exist.  */
4860
4861 tree
4862 gimple_block_label (basic_block bb)
4863 {
4864   gimple_stmt_iterator i, s = gsi_start_bb (bb);
4865   bool first = true;
4866   tree label;
4867   gimple stmt;
4868
4869   for (i = s; !gsi_end_p (i); first = false, gsi_next (&i))
4870     {
4871       stmt = gsi_stmt (i);
4872       if (gimple_code (stmt) != GIMPLE_LABEL)
4873         break;
4874       label = gimple_label_label (stmt);
4875       if (!DECL_NONLOCAL (label))
4876         {
4877           if (!first)
4878             gsi_move_before (&i, &s);
4879           return label;
4880         }
4881     }
4882
4883   label = create_artificial_label (UNKNOWN_LOCATION);
4884   stmt = gimple_build_label (label);
4885   gsi_insert_before (&s, stmt, GSI_NEW_STMT);
4886   return label;
4887 }
4888
4889
4890 /* Attempt to perform edge redirection by replacing a possibly complex
4891    jump instruction by a goto or by removing the jump completely.
4892    This can apply only if all edges now point to the same block.  The
4893    parameters and return values are equivalent to
4894    redirect_edge_and_branch.  */
4895
4896 static edge
4897 gimple_try_redirect_by_replacing_jump (edge e, basic_block target)
4898 {
4899   basic_block src = e->src;
4900   gimple_stmt_iterator i;
4901   gimple stmt;
4902
4903   /* We can replace or remove a complex jump only when we have exactly
4904      two edges.  */
4905   if (EDGE_COUNT (src->succs) != 2
4906       /* Verify that all targets will be TARGET.  Specifically, the
4907          edge that is not E must also go to TARGET.  */
4908       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
4909     return NULL;
4910
4911   i = gsi_last_bb (src);
4912   if (gsi_end_p (i))
4913     return NULL;
4914
4915   stmt = gsi_stmt (i);
4916
4917   if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH)
4918     {
4919       gsi_remove (&i, true);
4920       e = ssa_redirect_edge (e, target);
4921       e->flags = EDGE_FALLTHRU;
4922       return e;
4923     }
4924
4925   return NULL;
4926 }
4927
4928
4929 /* Redirect E to DEST.  Return NULL on failure.  Otherwise, return the
4930    edge representing the redirected branch.  */
4931
4932 static edge
4933 gimple_redirect_edge_and_branch (edge e, basic_block dest)
4934 {
4935   basic_block bb = e->src;
4936   gimple_stmt_iterator gsi;
4937   edge ret;
4938   gimple stmt;
4939
4940   if (e->flags & EDGE_ABNORMAL)
4941     return NULL;
4942
4943   if (e->dest == dest)
4944     return NULL;
4945
4946   if (e->flags & EDGE_EH)
4947     return redirect_eh_edge (e, dest);
4948
4949   if (e->src != ENTRY_BLOCK_PTR)
4950     {
4951       ret = gimple_try_redirect_by_replacing_jump (e, dest);
4952       if (ret)
4953         return ret;
4954     }
4955
4956   gsi = gsi_last_bb (bb);
4957   stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi);
4958
4959   switch (stmt ? gimple_code (stmt) : GIMPLE_ERROR_MARK)
4960     {
4961     case GIMPLE_COND:
4962       /* For COND_EXPR, we only need to redirect the edge.  */
4963       break;
4964
4965     case GIMPLE_GOTO:
4966       /* No non-abnormal edges should lead from a non-simple goto, and
4967          simple ones should be represented implicitly.  */
4968       gcc_unreachable ();
4969
4970     case GIMPLE_SWITCH:
4971       {
4972         tree label = gimple_block_label (dest);
4973         tree cases = get_cases_for_edge (e, stmt);
4974
4975         /* If we have a list of cases associated with E, then use it
4976            as it's a lot faster than walking the entire case vector.  */
4977         if (cases)
4978           {
4979             edge e2 = find_edge (e->src, dest);
4980             tree last, first;
4981
4982             first = cases;
4983             while (cases)
4984               {
4985                 last = cases;
4986                 CASE_LABEL (cases) = label;
4987                 cases = CASE_CHAIN (cases);
4988               }
4989
4990             /* If there was already an edge in the CFG, then we need
4991                to move all the cases associated with E to E2.  */
4992             if (e2)
4993               {
4994                 tree cases2 = get_cases_for_edge (e2, stmt);
4995
4996                 CASE_CHAIN (last) = CASE_CHAIN (cases2);
4997                 CASE_CHAIN (cases2) = first;
4998               }
4999             bitmap_set_bit (touched_switch_bbs, gimple_bb (stmt)->index);
5000           }
5001         else
5002           {
5003             size_t i, n = gimple_switch_num_labels (stmt);
5004
5005             for (i = 0; i < n; i++)
5006               {
5007                 tree elt = gimple_switch_label (stmt, i);
5008                 if (label_to_block (CASE_LABEL (elt)) == e->dest)
5009                   CASE_LABEL (elt) = label;
5010               }
5011           }
5012       }
5013       break;
5014
5015     case GIMPLE_ASM:
5016       {
5017         int i, n = gimple_asm_nlabels (stmt);
5018         tree label = NULL;
5019
5020         for (i = 0; i < n; ++i)
5021           {
5022             tree cons = gimple_asm_label_op (stmt, i);
5023             if (label_to_block (TREE_VALUE (cons)) == e->dest)
5024               {
5025                 if (!label)
5026                   label = gimple_block_label (dest);
5027                 TREE_VALUE (cons) = label;
5028               }
5029           }
5030
5031         /* If we didn't find any label matching the former edge in the
5032            asm labels, we must be redirecting the fallthrough
5033            edge.  */
5034         gcc_assert (label || (e->flags & EDGE_FALLTHRU));
5035       }
5036       break;
5037
5038     case GIMPLE_RETURN:
5039       gsi_remove (&gsi, true);
5040       e->flags |= EDGE_FALLTHRU;
5041       break;
5042
5043     case GIMPLE_OMP_RETURN:
5044     case GIMPLE_OMP_CONTINUE:
5045     case GIMPLE_OMP_SECTIONS_SWITCH:
5046     case GIMPLE_OMP_FOR:
5047       /* The edges from OMP constructs can be simply redirected.  */
5048       break;
5049
5050     case GIMPLE_EH_DISPATCH:
5051       if (!(e->flags & EDGE_FALLTHRU))
5052         redirect_eh_dispatch_edge (stmt, e, dest);
5053       break;
5054
5055     default:
5056       /* Otherwise it must be a fallthru edge, and we don't need to
5057          do anything besides redirecting it.  */
5058       gcc_assert (e->flags & EDGE_FALLTHRU);
5059       break;
5060     }
5061
5062   /* Update/insert PHI nodes as necessary.  */
5063
5064   /* Now update the edges in the CFG.  */
5065   e = ssa_redirect_edge (e, dest);
5066
5067   return e;
5068 }
5069
5070 /* Returns true if it is possible to remove edge E by redirecting
5071    it to the destination of the other edge from E->src.  */
5072
5073 static bool
5074 gimple_can_remove_branch_p (const_edge e)
5075 {
5076   if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
5077     return false;
5078
5079   return true;
5080 }
5081
5082 /* Simple wrapper, as we can always redirect fallthru edges.  */
5083
5084 static basic_block
5085 gimple_redirect_edge_and_branch_force (edge e, basic_block dest)
5086 {
5087   e = gimple_redirect_edge_and_branch (e, dest);
5088   gcc_assert (e);
5089
5090   return NULL;
5091 }
5092
5093
5094 /* Splits basic block BB after statement STMT (but at least after the
5095    labels).  If STMT is NULL, BB is split just after the labels.  */
5096
5097 static basic_block
5098 gimple_split_block (basic_block bb, void *stmt)
5099 {
5100   gimple_stmt_iterator gsi;
5101   gimple_stmt_iterator gsi_tgt;
5102   gimple act;
5103   gimple_seq list;
5104   basic_block new_bb;
5105   edge e;
5106   edge_iterator ei;
5107
5108   new_bb = create_empty_bb (bb);
5109
5110   /* Redirect the outgoing edges.  */
5111   new_bb->succs = bb->succs;
5112   bb->succs = NULL;
5113   FOR_EACH_EDGE (e, ei, new_bb->succs)
5114     e->src = new_bb;
5115
5116   if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
5117     stmt = NULL;
5118
5119   /* Move everything from GSI to the new basic block.  */
5120   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5121     {
5122       act = gsi_stmt (gsi);
5123       if (gimple_code (act) == GIMPLE_LABEL)
5124         continue;
5125
5126       if (!stmt)
5127         break;
5128
5129       if (stmt == act)
5130         {
5131           gsi_next (&gsi);
5132           break;
5133         }
5134     }
5135
5136   if (gsi_end_p (gsi))
5137     return new_bb;
5138
5139   /* Split the statement list - avoid re-creating new containers as this
5140      brings ugly quadratic memory consumption in the inliner.
5141      (We are still quadratic since we need to update stmt BB pointers,
5142      sadly.)  */
5143   list = gsi_split_seq_before (&gsi);
5144   set_bb_seq (new_bb, list);
5145   for (gsi_tgt = gsi_start (list);
5146        !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt))
5147     gimple_set_bb (gsi_stmt (gsi_tgt), new_bb);
5148
5149   return new_bb;
5150 }
5151
5152
5153 /* Moves basic block BB after block AFTER.  */
5154
5155 static bool
5156 gimple_move_block_after (basic_block bb, basic_block after)
5157 {
5158   if (bb->prev_bb == after)
5159     return true;
5160
5161   unlink_block (bb);
5162   link_block (bb, after);
5163
5164   return true;
5165 }
5166
5167
5168 /* Return true if basic_block can be duplicated.  */
5169
5170 static bool
5171 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED)
5172 {
5173   return true;
5174 }
5175
5176 /* Create a duplicate of the basic block BB.  NOTE: This does not
5177    preserve SSA form.  */
5178
5179 static basic_block
5180 gimple_duplicate_bb (basic_block bb)
5181 {
5182   basic_block new_bb;
5183   gimple_stmt_iterator gsi, gsi_tgt;
5184   gimple_seq phis = phi_nodes (bb);
5185   gimple phi, stmt, copy;
5186
5187   new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
5188
5189   /* Copy the PHI nodes.  We ignore PHI node arguments here because
5190      the incoming edges have not been setup yet.  */
5191   for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
5192     {
5193       phi = gsi_stmt (gsi);
5194       copy = create_phi_node (gimple_phi_result (phi), new_bb);
5195       create_new_def_for (gimple_phi_result (copy), copy,
5196                           gimple_phi_result_ptr (copy));
5197     }
5198
5199   gsi_tgt = gsi_start_bb (new_bb);
5200   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
5201     {
5202       def_operand_p def_p;
5203       ssa_op_iter op_iter;
5204       tree lhs;
5205
5206       stmt = gsi_stmt (gsi);
5207       if (gimple_code (stmt) == GIMPLE_LABEL)
5208         continue;
5209
5210       /* Create a new copy of STMT and duplicate STMT's virtual
5211          operands.  */
5212       copy = gimple_copy (stmt);
5213       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
5214
5215       maybe_duplicate_eh_stmt (copy, stmt);
5216       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
5217
5218       /* When copying around a stmt writing into a local non-user
5219          aggregate, make sure it won't share stack slot with other
5220          vars.  */
5221       lhs = gimple_get_lhs (stmt);
5222       if (lhs && TREE_CODE (lhs) != SSA_NAME)
5223         {
5224           tree base = get_base_address (lhs);
5225           if (base
5226               && (TREE_CODE (base) == VAR_DECL
5227                   || TREE_CODE (base) == RESULT_DECL)
5228               && DECL_IGNORED_P (base)
5229               && !TREE_STATIC (base)
5230               && !DECL_EXTERNAL (base)
5231               && (TREE_CODE (base) != VAR_DECL
5232                   || !DECL_HAS_VALUE_EXPR_P (base)))
5233             DECL_NONSHAREABLE (base) = 1;
5234         }
5235
5236       /* Create new names for all the definitions created by COPY and
5237          add replacement mappings for each new name.  */
5238       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
5239         create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p);
5240     }
5241
5242   return new_bb;
5243 }
5244
5245 /* Adds phi node arguments for edge E_COPY after basic block duplication.  */
5246
5247 static void
5248 add_phi_args_after_copy_edge (edge e_copy)
5249 {
5250   basic_block bb, bb_copy = e_copy->src, dest;
5251   edge e;
5252   edge_iterator ei;
5253   gimple phi, phi_copy;
5254   tree def;
5255   gimple_stmt_iterator psi, psi_copy;
5256
5257   if (gimple_seq_empty_p (phi_nodes (e_copy->dest)))
5258     return;
5259
5260   bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy;
5261
5262   if (e_copy->dest->flags & BB_DUPLICATED)
5263     dest = get_bb_original (e_copy->dest);
5264   else
5265     dest = e_copy->dest;
5266
5267   e = find_edge (bb, dest);
5268   if (!e)
5269     {
5270       /* During loop unrolling the target of the latch edge is copied.
5271          In this case we are not looking for edge to dest, but to
5272          duplicated block whose original was dest.  */
5273       FOR_EACH_EDGE (e, ei, bb->succs)
5274         {
5275           if ((e->dest->flags & BB_DUPLICATED)
5276               && get_bb_original (e->dest) == dest)
5277             break;
5278         }
5279
5280       gcc_assert (e != NULL);
5281     }
5282
5283   for (psi = gsi_start_phis (e->dest),
5284        psi_copy = gsi_start_phis (e_copy->dest);
5285        !gsi_end_p (psi);
5286        gsi_next (&psi), gsi_next (&psi_copy))
5287     {
5288       phi = gsi_stmt (psi);
5289       phi_copy = gsi_stmt (psi_copy);
5290       def = PHI_ARG_DEF_FROM_EDGE (phi, e);
5291       add_phi_arg (phi_copy, def, e_copy,
5292                    gimple_phi_arg_location_from_edge (phi, e));
5293     }
5294 }
5295
5296
5297 /* Basic block BB_COPY was created by code duplication.  Add phi node
5298    arguments for edges going out of BB_COPY.  The blocks that were
5299    duplicated have BB_DUPLICATED set.  */
5300
5301 void
5302 add_phi_args_after_copy_bb (basic_block bb_copy)
5303 {
5304   edge e_copy;
5305   edge_iterator ei;
5306
5307   FOR_EACH_EDGE (e_copy, ei, bb_copy->succs)
5308     {
5309       add_phi_args_after_copy_edge (e_copy);
5310     }
5311 }
5312
5313 /* Blocks in REGION_COPY array of length N_REGION were created by
5314    duplication of basic blocks.  Add phi node arguments for edges
5315    going from these blocks.  If E_COPY is not NULL, also add
5316    phi node arguments for its destination.*/
5317
5318 void
5319 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region,
5320                          edge e_copy)
5321 {
5322   unsigned i;
5323
5324   for (i = 0; i < n_region; i++)
5325     region_copy[i]->flags |= BB_DUPLICATED;
5326
5327   for (i = 0; i < n_region; i++)
5328     add_phi_args_after_copy_bb (region_copy[i]);
5329   if (e_copy)
5330     add_phi_args_after_copy_edge (e_copy);
5331
5332   for (i = 0; i < n_region; i++)
5333     region_copy[i]->flags &= ~BB_DUPLICATED;
5334 }
5335
5336 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single
5337    important exit edge EXIT.  By important we mean that no SSA name defined
5338    inside region is live over the other exit edges of the region.  All entry
5339    edges to the region must go to ENTRY->dest.  The edge ENTRY is redirected
5340    to the duplicate of the region.  SSA form, dominance and loop information
5341    is updated.  The new basic blocks are stored to REGION_COPY in the same
5342    order as they had in REGION, provided that REGION_COPY is not NULL.
5343    The function returns false if it is unable to copy the region,
5344    true otherwise.  */
5345
5346 bool
5347 gimple_duplicate_sese_region (edge entry, edge exit,
5348                             basic_block *region, unsigned n_region,
5349                             basic_block *region_copy)
5350 {
5351   unsigned i;
5352   bool free_region_copy = false, copying_header = false;
5353   struct loop *loop = entry->dest->loop_father;
5354   edge exit_copy;
5355   VEC (basic_block, heap) *doms;
5356   edge redirected;
5357   int total_freq = 0, entry_freq = 0;
5358   gcov_type total_count = 0, entry_count = 0;
5359
5360   if (!can_copy_bbs_p (region, n_region))
5361     return false;
5362
5363   /* Some sanity checking.  Note that we do not check for all possible
5364      missuses of the functions.  I.e. if you ask to copy something weird,
5365      it will work, but the state of structures probably will not be
5366      correct.  */
5367   for (i = 0; i < n_region; i++)
5368     {
5369       /* We do not handle subloops, i.e. all the blocks must belong to the
5370          same loop.  */
5371       if (region[i]->loop_father != loop)
5372         return false;
5373
5374       if (region[i] != entry->dest
5375           && region[i] == loop->header)
5376         return false;
5377     }
5378
5379   set_loop_copy (loop, loop);
5380
5381   /* In case the function is used for loop header copying (which is the primary
5382      use), ensure that EXIT and its copy will be new latch and entry edges.  */
5383   if (loop->header == entry->dest)
5384     {
5385       copying_header = true;
5386       set_loop_copy (loop, loop_outer (loop));
5387
5388       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
5389         return false;
5390
5391       for (i = 0; i < n_region; i++)
5392         if (region[i] != exit->src
5393             && dominated_by_p (CDI_DOMINATORS, region[i], exit->src))
5394           return false;
5395     }
5396
5397   if (!region_copy)
5398     {
5399       region_copy = XNEWVEC (basic_block, n_region);
5400       free_region_copy = true;
5401     }
5402
5403   gcc_assert (!need_ssa_update_p (cfun));
5404
5405   /* Record blocks outside the region that are dominated by something
5406      inside.  */
5407   doms = NULL;
5408   initialize_original_copy_tables ();
5409
5410   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5411
5412   if (entry->dest->count)
5413     {
5414       total_count = entry->dest->count;
5415       entry_count = entry->count;
5416       /* Fix up corner cases, to avoid division by zero or creation of negative
5417          frequencies.  */
5418       if (entry_count > total_count)
5419         entry_count = total_count;
5420     }
5421   else
5422     {
5423       total_freq = entry->dest->frequency;
5424       entry_freq = EDGE_FREQUENCY (entry);
5425       /* Fix up corner cases, to avoid division by zero or creation of negative
5426          frequencies.  */
5427       if (total_freq == 0)
5428         total_freq = 1;
5429       else if (entry_freq > total_freq)
5430         entry_freq = total_freq;
5431     }
5432
5433   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
5434             split_edge_bb_loc (entry));
5435   if (total_count)
5436     {
5437       scale_bbs_frequencies_gcov_type (region, n_region,
5438                                        total_count - entry_count,
5439                                        total_count);
5440       scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count,
5441                                        total_count);
5442     }
5443   else
5444     {
5445       scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq,
5446                                  total_freq);
5447       scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq);
5448     }
5449
5450   if (copying_header)
5451     {
5452       loop->header = exit->dest;
5453       loop->latch = exit->src;
5454     }
5455
5456   /* Redirect the entry and add the phi node arguments.  */
5457   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
5458   gcc_assert (redirected != NULL);
5459   flush_pending_stmts (entry);
5460
5461   /* Concerning updating of dominators:  We must recount dominators
5462      for entry block and its copy.  Anything that is outside of the
5463      region, but was dominated by something inside needs recounting as
5464      well.  */
5465   set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src);
5466   VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest));
5467   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5468   VEC_free (basic_block, heap, doms);
5469
5470   /* Add the other PHI node arguments.  */
5471   add_phi_args_after_copy (region_copy, n_region, NULL);
5472
5473   /* Update the SSA web.  */
5474   update_ssa (TODO_update_ssa);
5475
5476   if (free_region_copy)
5477     free (region_copy);
5478
5479   free_original_copy_tables ();
5480   return true;
5481 }
5482
5483 /* Duplicates REGION consisting of N_REGION blocks.  The new blocks
5484    are stored to REGION_COPY in the same order in that they appear
5485    in REGION, if REGION_COPY is not NULL.  ENTRY is the entry to
5486    the region, EXIT an exit from it.  The condition guarding EXIT
5487    is moved to ENTRY.  Returns true if duplication succeeds, false
5488    otherwise.
5489
5490    For example,
5491
5492    some_code;
5493    if (cond)
5494      A;
5495    else
5496      B;
5497
5498    is transformed to
5499
5500    if (cond)
5501      {
5502        some_code;
5503        A;
5504      }
5505    else
5506      {
5507        some_code;
5508        B;
5509      }
5510 */
5511
5512 bool
5513 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED,
5514                           basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED,
5515                           basic_block *region_copy ATTRIBUTE_UNUSED)
5516 {
5517   unsigned i;
5518   bool free_region_copy = false;
5519   struct loop *loop = exit->dest->loop_father;
5520   struct loop *orig_loop = entry->dest->loop_father;
5521   basic_block switch_bb, entry_bb, nentry_bb;
5522   VEC (basic_block, heap) *doms;
5523   int total_freq = 0, exit_freq = 0;
5524   gcov_type total_count = 0, exit_count = 0;
5525   edge exits[2], nexits[2], e;
5526   gimple_stmt_iterator gsi;
5527   gimple cond_stmt;
5528   edge sorig, snew;
5529   basic_block exit_bb;
5530   gimple_stmt_iterator psi;
5531   gimple phi;
5532   tree def;
5533
5534   gcc_assert (EDGE_COUNT (exit->src->succs) == 2);
5535   exits[0] = exit;
5536   exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
5537
5538   if (!can_copy_bbs_p (region, n_region))
5539     return false;
5540
5541   initialize_original_copy_tables ();
5542   set_loop_copy (orig_loop, loop);
5543   duplicate_subloops (orig_loop, loop);
5544
5545   if (!region_copy)
5546     {
5547       region_copy = XNEWVEC (basic_block, n_region);
5548       free_region_copy = true;
5549     }
5550
5551   gcc_assert (!need_ssa_update_p (cfun));
5552
5553   /* Record blocks outside the region that are dominated by something
5554      inside.  */
5555   doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region);
5556
5557   if (exit->src->count)
5558     {
5559       total_count = exit->src->count;
5560       exit_count = exit->count;
5561       /* Fix up corner cases, to avoid division by zero or creation of negative
5562          frequencies.  */
5563       if (exit_count > total_count)
5564         exit_count = total_count;
5565     }
5566   else
5567     {
5568       total_freq = exit->src->frequency;
5569       exit_freq = EDGE_FREQUENCY (exit);
5570       /* Fix up corner cases, to avoid division by zero or creation of negative
5571          frequencies.  */
5572       if (total_freq == 0)
5573         total_freq = 1;
5574       if (exit_freq > total_freq)
5575         exit_freq = total_freq;
5576     }
5577
5578   copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop,
5579             split_edge_bb_loc (exit));
5580   if (total_count)
5581     {
5582       scale_bbs_frequencies_gcov_type (region, n_region,
5583                                        total_count - exit_count,
5584                                        total_count);
5585       scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count,
5586                                        total_count);
5587     }
5588   else
5589     {
5590       scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq,
5591                                  total_freq);
5592       scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq);
5593     }
5594
5595   /* Create the switch block, and put the exit condition to it.  */
5596   entry_bb = entry->dest;
5597   nentry_bb = get_bb_copy (entry_bb);
5598   if (!last_stmt (entry->src)
5599       || !stmt_ends_bb_p (last_stmt (entry->src)))
5600     switch_bb = entry->src;
5601   else
5602     switch_bb = split_edge (entry);
5603   set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb);
5604
5605   gsi = gsi_last_bb (switch_bb);
5606   cond_stmt = last_stmt (exit->src);
5607   gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND);
5608   cond_stmt = gimple_copy (cond_stmt);
5609
5610   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
5611
5612   sorig = single_succ_edge (switch_bb);
5613   sorig->flags = exits[1]->flags;
5614   snew = make_edge (switch_bb, nentry_bb, exits[0]->flags);
5615
5616   /* Register the new edge from SWITCH_BB in loop exit lists.  */
5617   rescan_loop_exit (snew, true, false);
5618
5619   /* Add the PHI node arguments.  */
5620   add_phi_args_after_copy (region_copy, n_region, snew);
5621
5622   /* Get rid of now superfluous conditions and associated edges (and phi node
5623      arguments).  */
5624   exit_bb = exit->dest;
5625
5626   e = redirect_edge_and_branch (exits[0], exits[1]->dest);
5627   PENDING_STMT (e) = NULL;
5628
5629   /* The latch of ORIG_LOOP was copied, and so was the backedge
5630      to the original header.  We redirect this backedge to EXIT_BB.  */
5631   for (i = 0; i < n_region; i++)
5632     if (get_bb_original (region_copy[i]) == orig_loop->latch)
5633       {
5634         gcc_assert (single_succ_edge (region_copy[i]));
5635         e = redirect_edge_and_branch (single_succ_edge (region_copy[i]), exit_bb);
5636         PENDING_STMT (e) = NULL;
5637         for (psi = gsi_start_phis (exit_bb);
5638              !gsi_end_p (psi);
5639              gsi_next (&psi))
5640           {
5641             phi = gsi_stmt (psi);
5642             def = PHI_ARG_DEF (phi, nexits[0]->dest_idx);
5643             add_phi_arg (phi, def, e, gimple_phi_arg_location_from_edge (phi, e));
5644           }
5645       }
5646   e = redirect_edge_and_branch (nexits[0], nexits[1]->dest);
5647   PENDING_STMT (e) = NULL;
5648
5649   /* Anything that is outside of the region, but was dominated by something
5650      inside needs to update dominance info.  */
5651   iterate_fix_dominators (CDI_DOMINATORS, doms, false);
5652   VEC_free (basic_block, heap, doms);
5653   /* Update the SSA web.  */
5654   update_ssa (TODO_update_ssa);
5655
5656   if (free_region_copy)
5657     free (region_copy);
5658
5659   free_original_copy_tables ();
5660   return true;
5661 }
5662
5663 /* Add all the blocks dominated by ENTRY to the array BBS_P.  Stop
5664    adding blocks when the dominator traversal reaches EXIT.  This
5665    function silently assumes that ENTRY strictly dominates EXIT.  */
5666
5667 void
5668 gather_blocks_in_sese_region (basic_block entry, basic_block exit,
5669                               VEC(basic_block,heap) **bbs_p)
5670 {
5671   basic_block son;
5672
5673   for (son = first_dom_son (CDI_DOMINATORS, entry);
5674        son;
5675        son = next_dom_son (CDI_DOMINATORS, son))
5676     {
5677       VEC_safe_push (basic_block, heap, *bbs_p, son);
5678       if (son != exit)
5679         gather_blocks_in_sese_region (son, exit, bbs_p);
5680     }
5681 }
5682
5683 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT).
5684    The duplicates are recorded in VARS_MAP.  */
5685
5686 static void
5687 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map,
5688                            tree to_context)
5689 {
5690   tree t = *tp, new_t;
5691   struct function *f = DECL_STRUCT_FUNCTION (to_context);
5692   void **loc;
5693
5694   if (DECL_CONTEXT (t) == to_context)
5695     return;
5696
5697   loc = pointer_map_contains (vars_map, t);
5698
5699   if (!loc)
5700     {
5701       loc = pointer_map_insert (vars_map, t);
5702
5703       if (SSA_VAR_P (t))
5704         {
5705           new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t));
5706           add_local_decl (f, new_t);
5707         }
5708       else
5709         {
5710           gcc_assert (TREE_CODE (t) == CONST_DECL);
5711           new_t = copy_node (t);
5712         }
5713       DECL_CONTEXT (new_t) = to_context;
5714
5715       *loc = new_t;
5716     }
5717   else
5718     new_t = (tree) *loc;
5719
5720   *tp = new_t;
5721 }
5722
5723
5724 /* Creates an ssa name in TO_CONTEXT equivalent to NAME.
5725    VARS_MAP maps old ssa names and var_decls to the new ones.  */
5726
5727 static tree
5728 replace_ssa_name (tree name, struct pointer_map_t *vars_map,
5729                   tree to_context)
5730 {
5731   void **loc;
5732   tree new_name, decl = SSA_NAME_VAR (name);
5733
5734   gcc_assert (is_gimple_reg (name));
5735
5736   loc = pointer_map_contains (vars_map, name);
5737
5738   if (!loc)
5739     {
5740       replace_by_duplicate_decl (&decl, vars_map, to_context);
5741
5742       push_cfun (DECL_STRUCT_FUNCTION (to_context));
5743       if (gimple_in_ssa_p (cfun))
5744         add_referenced_var (decl);
5745
5746       new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name));
5747       if (SSA_NAME_IS_DEFAULT_DEF (name))
5748         set_default_def (decl, new_name);
5749       pop_cfun ();
5750
5751       loc = pointer_map_insert (vars_map, name);
5752       *loc = new_name;
5753     }
5754   else
5755     new_name = (tree) *loc;
5756
5757   return new_name;
5758 }
5759
5760 struct move_stmt_d
5761 {
5762   tree orig_block;
5763   tree new_block;
5764   tree from_context;
5765   tree to_context;
5766   struct pointer_map_t *vars_map;
5767   htab_t new_label_map;
5768   struct pointer_map_t *eh_map;
5769   bool remap_decls_p;
5770 };
5771
5772 /* Helper for move_block_to_fn.  Set TREE_BLOCK in every expression
5773    contained in *TP if it has been ORIG_BLOCK previously and change the
5774    DECL_CONTEXT of every local variable referenced in *TP.  */
5775
5776 static tree
5777 move_stmt_op (tree *tp, int *walk_subtrees, void *data)
5778 {
5779   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
5780   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5781   tree t = *tp;
5782
5783   if (EXPR_P (t))
5784     /* We should never have TREE_BLOCK set on non-statements.  */
5785     gcc_assert (!TREE_BLOCK (t));
5786
5787   else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME)
5788     {
5789       if (TREE_CODE (t) == SSA_NAME)
5790         *tp = replace_ssa_name (t, p->vars_map, p->to_context);
5791       else if (TREE_CODE (t) == LABEL_DECL)
5792         {
5793           if (p->new_label_map)
5794             {
5795               struct tree_map in, *out;
5796               in.base.from = t;
5797               out = (struct tree_map *)
5798                 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t));
5799               if (out)
5800                 *tp = t = out->to;
5801             }
5802
5803           DECL_CONTEXT (t) = p->to_context;
5804         }
5805       else if (p->remap_decls_p)
5806         {
5807           /* Replace T with its duplicate.  T should no longer appear in the
5808              parent function, so this looks wasteful; however, it may appear
5809              in referenced_vars, and more importantly, as virtual operands of
5810              statements, and in alias lists of other variables.  It would be
5811              quite difficult to expunge it from all those places.  ??? It might
5812              suffice to do this for addressable variables.  */
5813           if ((TREE_CODE (t) == VAR_DECL
5814                && !is_global_var (t))
5815               || TREE_CODE (t) == CONST_DECL)
5816             replace_by_duplicate_decl (tp, p->vars_map, p->to_context);
5817
5818           if (SSA_VAR_P (t)
5819               && gimple_in_ssa_p (cfun))
5820             {
5821               push_cfun (DECL_STRUCT_FUNCTION (p->to_context));
5822               add_referenced_var (*tp);
5823               pop_cfun ();
5824             }
5825         }
5826       *walk_subtrees = 0;
5827     }
5828   else if (TYPE_P (t))
5829     *walk_subtrees = 0;
5830
5831   return NULL_TREE;
5832 }
5833
5834 /* Helper for move_stmt_r.  Given an EH region number for the source
5835    function, map that to the duplicate EH regio number in the dest.  */
5836
5837 static int
5838 move_stmt_eh_region_nr (int old_nr, struct move_stmt_d *p)
5839 {
5840   eh_region old_r, new_r;
5841   void **slot;
5842
5843   old_r = get_eh_region_from_number (old_nr);
5844   slot = pointer_map_contains (p->eh_map, old_r);
5845   new_r = (eh_region) *slot;
5846
5847   return new_r->index;
5848 }
5849
5850 /* Similar, but operate on INTEGER_CSTs.  */
5851
5852 static tree
5853 move_stmt_eh_region_tree_nr (tree old_t_nr, struct move_stmt_d *p)
5854 {
5855   int old_nr, new_nr;
5856
5857   old_nr = tree_low_cst (old_t_nr, 0);
5858   new_nr = move_stmt_eh_region_nr (old_nr, p);
5859
5860   return build_int_cst (integer_type_node, new_nr);
5861 }
5862
5863 /* Like move_stmt_op, but for gimple statements.
5864
5865    Helper for move_block_to_fn.  Set GIMPLE_BLOCK in every expression
5866    contained in the current statement in *GSI_P and change the
5867    DECL_CONTEXT of every local variable referenced in the current
5868    statement.  */
5869
5870 static tree
5871 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p,
5872              struct walk_stmt_info *wi)
5873 {
5874   struct move_stmt_d *p = (struct move_stmt_d *) wi->info;
5875   gimple stmt = gsi_stmt (*gsi_p);
5876   tree block = gimple_block (stmt);
5877
5878   if (p->orig_block == NULL_TREE
5879       || block == p->orig_block
5880       || block == NULL_TREE)
5881     gimple_set_block (stmt, p->new_block);
5882 #ifdef ENABLE_CHECKING
5883   else if (block != p->new_block)
5884     {
5885       while (block && block != p->orig_block)
5886         block = BLOCK_SUPERCONTEXT (block);
5887       gcc_assert (block);
5888     }
5889 #endif
5890
5891   switch (gimple_code (stmt))
5892     {
5893     case GIMPLE_CALL:
5894       /* Remap the region numbers for __builtin_eh_{pointer,filter}.  */
5895       {
5896         tree r, fndecl = gimple_call_fndecl (stmt);
5897         if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
5898           switch (DECL_FUNCTION_CODE (fndecl))
5899             {
5900             case BUILT_IN_EH_COPY_VALUES:
5901               r = gimple_call_arg (stmt, 1);
5902               r = move_stmt_eh_region_tree_nr (r, p);
5903               gimple_call_set_arg (stmt, 1, r);
5904               /* FALLTHRU */
5905
5906             case BUILT_IN_EH_POINTER:
5907             case BUILT_IN_EH_FILTER:
5908               r = gimple_call_arg (stmt, 0);
5909               r = move_stmt_eh_region_tree_nr (r, p);
5910               gimple_call_set_arg (stmt, 0, r);
5911               break;
5912
5913             default:
5914               break;
5915             }
5916       }
5917       break;
5918
5919     case GIMPLE_RESX:
5920       {
5921         int r = gimple_resx_region (stmt);
5922         r = move_stmt_eh_region_nr (r, p);
5923         gimple_resx_set_region (stmt, r);
5924       }
5925       break;
5926
5927     case GIMPLE_EH_DISPATCH:
5928       {
5929         int r = gimple_eh_dispatch_region (stmt);
5930         r = move_stmt_eh_region_nr (r, p);
5931         gimple_eh_dispatch_set_region (stmt, r);
5932       }
5933       break;
5934
5935     case GIMPLE_OMP_RETURN:
5936     case GIMPLE_OMP_CONTINUE:
5937       break;
5938     default:
5939       if (is_gimple_omp (stmt))
5940         {
5941           /* Do not remap variables inside OMP directives.  Variables
5942              referenced in clauses and directive header belong to the
5943              parent function and should not be moved into the child
5944              function.  */
5945           bool save_remap_decls_p = p->remap_decls_p;
5946           p->remap_decls_p = false;
5947           *handled_ops_p = true;
5948
5949           walk_gimple_seq (gimple_omp_body (stmt), move_stmt_r,
5950                            move_stmt_op, wi);
5951
5952           p->remap_decls_p = save_remap_decls_p;
5953         }
5954       break;
5955     }
5956
5957   return NULL_TREE;
5958 }
5959
5960 /* Move basic block BB from function CFUN to function DEST_FN.  The
5961    block is moved out of the original linked list and placed after
5962    block AFTER in the new list.  Also, the block is removed from the
5963    original array of blocks and placed in DEST_FN's array of blocks.
5964    If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is
5965    updated to reflect the moved edges.
5966
5967    The local variables are remapped to new instances, VARS_MAP is used
5968    to record the mapping.  */
5969
5970 static void
5971 move_block_to_fn (struct function *dest_cfun, basic_block bb,
5972                   basic_block after, bool update_edge_count_p,
5973                   struct move_stmt_d *d)
5974 {
5975   struct control_flow_graph *cfg;
5976   edge_iterator ei;
5977   edge e;
5978   gimple_stmt_iterator si;
5979   unsigned old_len, new_len;
5980
5981   /* Remove BB from dominance structures.  */
5982   delete_from_dominance_info (CDI_DOMINATORS, bb);
5983   if (current_loops)
5984     remove_bb_from_loops (bb);
5985
5986   /* Link BB to the new linked list.  */
5987   move_block_after (bb, after);
5988
5989   /* Update the edge count in the corresponding flowgraphs.  */
5990   if (update_edge_count_p)
5991     FOR_EACH_EDGE (e, ei, bb->succs)
5992       {
5993         cfun->cfg->x_n_edges--;
5994         dest_cfun->cfg->x_n_edges++;
5995       }
5996
5997   /* Remove BB from the original basic block array.  */
5998   VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL);
5999   cfun->cfg->x_n_basic_blocks--;
6000
6001   /* Grow DEST_CFUN's basic block array if needed.  */
6002   cfg = dest_cfun->cfg;
6003   cfg->x_n_basic_blocks++;
6004   if (bb->index >= cfg->x_last_basic_block)
6005     cfg->x_last_basic_block = bb->index + 1;
6006
6007   old_len = VEC_length (basic_block, cfg->x_basic_block_info);
6008   if ((unsigned) cfg->x_last_basic_block >= old_len)
6009     {
6010       new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4;
6011       VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info,
6012                              new_len);
6013     }
6014
6015   VEC_replace (basic_block, cfg->x_basic_block_info,
6016                bb->index, bb);
6017
6018   /* Remap the variables in phi nodes.  */
6019   for (si = gsi_start_phis (bb); !gsi_end_p (si); )
6020     {
6021       gimple phi = gsi_stmt (si);
6022       use_operand_p use;
6023       tree op = PHI_RESULT (phi);
6024       ssa_op_iter oi;
6025
6026       if (!is_gimple_reg (op))
6027         {
6028           /* Remove the phi nodes for virtual operands (alias analysis will be
6029              run for the new function, anyway).  */
6030           remove_phi_node (&si, true);
6031           continue;
6032         }
6033
6034       SET_PHI_RESULT (phi,
6035                       replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6036       FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
6037         {
6038           op = USE_FROM_PTR (use);
6039           if (TREE_CODE (op) == SSA_NAME)
6040             SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl));
6041         }
6042
6043       gsi_next (&si);
6044     }
6045
6046   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6047     {
6048       gimple stmt = gsi_stmt (si);
6049       struct walk_stmt_info wi;
6050
6051       memset (&wi, 0, sizeof (wi));
6052       wi.info = d;
6053       walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi);
6054
6055       if (gimple_code (stmt) == GIMPLE_LABEL)
6056         {
6057           tree label = gimple_label_label (stmt);
6058           int uid = LABEL_DECL_UID (label);
6059
6060           gcc_assert (uid > -1);
6061
6062           old_len = VEC_length (basic_block, cfg->x_label_to_block_map);
6063           if (old_len <= (unsigned) uid)
6064             {
6065               new_len = 3 * uid / 2 + 1;
6066               VEC_safe_grow_cleared (basic_block, gc,
6067                                      cfg->x_label_to_block_map, new_len);
6068             }
6069
6070           VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb);
6071           VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL);
6072
6073           gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl);
6074
6075           if (uid >= dest_cfun->cfg->last_label_uid)
6076             dest_cfun->cfg->last_label_uid = uid + 1;
6077         }
6078
6079       maybe_duplicate_eh_stmt_fn (dest_cfun, stmt, cfun, stmt, d->eh_map, 0);
6080       remove_stmt_from_eh_lp_fn (cfun, stmt);
6081
6082       gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt);
6083       gimple_remove_stmt_histograms (cfun, stmt);
6084
6085       /* We cannot leave any operands allocated from the operand caches of
6086          the current function.  */
6087       free_stmt_operands (stmt);
6088       push_cfun (dest_cfun);
6089       update_stmt (stmt);
6090       pop_cfun ();
6091     }
6092
6093   FOR_EACH_EDGE (e, ei, bb->succs)
6094     if (e->goto_locus)
6095       {
6096         tree block = e->goto_block;
6097         if (d->orig_block == NULL_TREE
6098             || block == d->orig_block)
6099           e->goto_block = d->new_block;
6100 #ifdef ENABLE_CHECKING
6101         else if (block != d->new_block)
6102           {
6103             while (block && block != d->orig_block)
6104               block = BLOCK_SUPERCONTEXT (block);
6105             gcc_assert (block);
6106           }
6107 #endif
6108       }
6109 }
6110
6111 /* Examine the statements in BB (which is in SRC_CFUN); find and return
6112    the outermost EH region.  Use REGION as the incoming base EH region.  */
6113
6114 static eh_region
6115 find_outermost_region_in_block (struct function *src_cfun,
6116                                 basic_block bb, eh_region region)
6117 {
6118   gimple_stmt_iterator si;
6119
6120   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
6121     {
6122       gimple stmt = gsi_stmt (si);
6123       eh_region stmt_region;
6124       int lp_nr;
6125
6126       lp_nr = lookup_stmt_eh_lp_fn (src_cfun, stmt);
6127       stmt_region = get_eh_region_from_lp_number_fn (src_cfun, lp_nr);
6128       if (stmt_region)
6129         {
6130           if (region == NULL)
6131             region = stmt_region;
6132           else if (stmt_region != region)
6133             {
6134               region = eh_region_outermost (src_cfun, stmt_region, region);
6135               gcc_assert (region != NULL);
6136             }
6137         }
6138     }
6139
6140   return region;
6141 }
6142
6143 static tree
6144 new_label_mapper (tree decl, void *data)
6145 {
6146   htab_t hash = (htab_t) data;
6147   struct tree_map *m;
6148   void **slot;
6149
6150   gcc_assert (TREE_CODE (decl) == LABEL_DECL);
6151
6152   m = XNEW (struct tree_map);
6153   m->hash = DECL_UID (decl);
6154   m->base.from = decl;
6155   m->to = create_artificial_label (UNKNOWN_LOCATION);
6156   LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl);
6157   if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid)
6158     cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1;
6159
6160   slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT);
6161   gcc_assert (*slot == NULL);
6162
6163   *slot = m;
6164
6165   return m->to;
6166 }
6167
6168 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including
6169    subblocks.  */
6170
6171 static void
6172 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map,
6173                                   tree to_context)
6174 {
6175   tree *tp, t;
6176
6177   for (tp = &BLOCK_VARS (block); *tp; tp = &DECL_CHAIN (*tp))
6178     {
6179       t = *tp;
6180       if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL)
6181         continue;
6182       replace_by_duplicate_decl (&t, vars_map, to_context);
6183       if (t != *tp)
6184         {
6185           if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp))
6186             {
6187               SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp));
6188               DECL_HAS_VALUE_EXPR_P (t) = 1;
6189             }
6190           DECL_CHAIN (t) = DECL_CHAIN (*tp);
6191           *tp = t;
6192         }
6193     }
6194
6195   for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block))
6196     replace_block_vars_by_duplicates (block, vars_map, to_context);
6197 }
6198
6199 /* Move a single-entry, single-exit region delimited by ENTRY_BB and
6200    EXIT_BB to function DEST_CFUN.  The whole region is replaced by a
6201    single basic block in the original CFG and the new basic block is
6202    returned.  DEST_CFUN must not have a CFG yet.
6203
6204    Note that the region need not be a pure SESE region.  Blocks inside
6205    the region may contain calls to abort/exit.  The only restriction
6206    is that ENTRY_BB should be the only entry point and it must
6207    dominate EXIT_BB.
6208
6209    Change TREE_BLOCK of all statements in ORIG_BLOCK to the new
6210    functions outermost BLOCK, move all subblocks of ORIG_BLOCK
6211    to the new function.
6212
6213    All local variables referenced in the region are assumed to be in
6214    the corresponding BLOCK_VARS and unexpanded variable lists
6215    associated with DEST_CFUN.  */
6216
6217 basic_block
6218 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb,
6219                         basic_block exit_bb, tree orig_block)
6220 {
6221   VEC(basic_block,heap) *bbs, *dom_bbs;
6222   basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb);
6223   basic_block after, bb, *entry_pred, *exit_succ, abb;
6224   struct function *saved_cfun = cfun;
6225   int *entry_flag, *exit_flag;
6226   unsigned *entry_prob, *exit_prob;
6227   unsigned i, num_entry_edges, num_exit_edges;
6228   edge e;
6229   edge_iterator ei;
6230   htab_t new_label_map;
6231   struct pointer_map_t *vars_map, *eh_map;
6232   struct loop *loop = entry_bb->loop_father;
6233   struct move_stmt_d d;
6234
6235   /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE
6236      region.  */
6237   gcc_assert (entry_bb != exit_bb
6238               && (!exit_bb
6239                   || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)));
6240
6241   /* Collect all the blocks in the region.  Manually add ENTRY_BB
6242      because it won't be added by dfs_enumerate_from.  */
6243   bbs = NULL;
6244   VEC_safe_push (basic_block, heap, bbs, entry_bb);
6245   gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs);
6246
6247   /* The blocks that used to be dominated by something in BBS will now be
6248      dominated by the new block.  */
6249   dom_bbs = get_dominated_by_region (CDI_DOMINATORS,
6250                                      VEC_address (basic_block, bbs),
6251                                      VEC_length (basic_block, bbs));
6252
6253   /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG.  We need to remember
6254      the predecessor edges to ENTRY_BB and the successor edges to
6255      EXIT_BB so that we can re-attach them to the new basic block that
6256      will replace the region.  */
6257   num_entry_edges = EDGE_COUNT (entry_bb->preds);
6258   entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block));
6259   entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int));
6260   entry_prob = XNEWVEC (unsigned, num_entry_edges);
6261   i = 0;
6262   for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;)
6263     {
6264       entry_prob[i] = e->probability;
6265       entry_flag[i] = e->flags;
6266       entry_pred[i++] = e->src;
6267       remove_edge (e);
6268     }
6269
6270   if (exit_bb)
6271     {
6272       num_exit_edges = EDGE_COUNT (exit_bb->succs);
6273       exit_succ = (basic_block *) xcalloc (num_exit_edges,
6274                                            sizeof (basic_block));
6275       exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int));
6276       exit_prob = XNEWVEC (unsigned, num_exit_edges);
6277       i = 0;
6278       for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;)
6279         {
6280           exit_prob[i] = e->probability;
6281           exit_flag[i] = e->flags;
6282           exit_succ[i++] = e->dest;
6283           remove_edge (e);
6284         }
6285     }
6286   else
6287     {
6288       num_exit_edges = 0;
6289       exit_succ = NULL;
6290       exit_flag = NULL;
6291       exit_prob = NULL;
6292     }
6293
6294   /* Switch context to the child function to initialize DEST_FN's CFG.  */
6295   gcc_assert (dest_cfun->cfg == NULL);
6296   push_cfun (dest_cfun);
6297
6298   init_empty_tree_cfg ();
6299
6300   /* Initialize EH information for the new function.  */
6301   eh_map = NULL;
6302   new_label_map = NULL;
6303   if (saved_cfun->eh)
6304     {
6305       eh_region region = NULL;
6306
6307       FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
6308         region = find_outermost_region_in_block (saved_cfun, bb, region);
6309
6310       init_eh_for_function ();
6311       if (region != NULL)
6312         {
6313           new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free);
6314           eh_map = duplicate_eh_regions (saved_cfun, region, 0,
6315                                          new_label_mapper, new_label_map);
6316         }
6317     }
6318
6319   pop_cfun ();
6320
6321   /* Move blocks from BBS into DEST_CFUN.  */
6322   gcc_assert (VEC_length (basic_block, bbs) >= 2);
6323   after = dest_cfun->cfg->x_entry_block_ptr;
6324   vars_map = pointer_map_create ();
6325
6326   memset (&d, 0, sizeof (d));
6327   d.orig_block = orig_block;
6328   d.new_block = DECL_INITIAL (dest_cfun->decl);
6329   d.from_context = cfun->decl;
6330   d.to_context = dest_cfun->decl;
6331   d.vars_map = vars_map;
6332   d.new_label_map = new_label_map;
6333   d.eh_map = eh_map;
6334   d.remap_decls_p = true;
6335
6336   FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
6337     {
6338       /* No need to update edge counts on the last block.  It has
6339          already been updated earlier when we detached the region from
6340          the original CFG.  */
6341       move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d);
6342       after = bb;
6343     }
6344
6345   /* Rewire BLOCK_SUBBLOCKS of orig_block.  */
6346   if (orig_block)
6347     {
6348       tree block;
6349       gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6350                   == NULL_TREE);
6351       BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl))
6352         = BLOCK_SUBBLOCKS (orig_block);
6353       for (block = BLOCK_SUBBLOCKS (orig_block);
6354            block; block = BLOCK_CHAIN (block))
6355         BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl);
6356       BLOCK_SUBBLOCKS (orig_block) = NULL_TREE;
6357     }
6358
6359   replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl),
6360                                     vars_map, dest_cfun->decl);
6361
6362   if (new_label_map)
6363     htab_delete (new_label_map);
6364   if (eh_map)
6365     pointer_map_destroy (eh_map);
6366   pointer_map_destroy (vars_map);
6367
6368   /* Rewire the entry and exit blocks.  The successor to the entry
6369      block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in
6370      the child function.  Similarly, the predecessor of DEST_FN's
6371      EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR.  We
6372      need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the
6373      various CFG manipulation function get to the right CFG.
6374
6375      FIXME, this is silly.  The CFG ought to become a parameter to
6376      these helpers.  */
6377   push_cfun (dest_cfun);
6378   make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU);
6379   if (exit_bb)
6380     make_edge (exit_bb,  EXIT_BLOCK_PTR, 0);
6381   pop_cfun ();
6382
6383   /* Back in the original function, the SESE region has disappeared,
6384      create a new basic block in its place.  */
6385   bb = create_empty_bb (entry_pred[0]);
6386   if (current_loops)
6387     add_bb_to_loop (bb, loop);
6388   for (i = 0; i < num_entry_edges; i++)
6389     {
6390       e = make_edge (entry_pred[i], bb, entry_flag[i]);
6391       e->probability = entry_prob[i];
6392     }
6393
6394   for (i = 0; i < num_exit_edges; i++)
6395     {
6396       e = make_edge (bb, exit_succ[i], exit_flag[i]);
6397       e->probability = exit_prob[i];
6398     }
6399
6400   set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry);
6401   FOR_EACH_VEC_ELT (basic_block, dom_bbs, i, abb)
6402     set_immediate_dominator (CDI_DOMINATORS, abb, bb);
6403   VEC_free (basic_block, heap, dom_bbs);
6404
6405   if (exit_bb)
6406     {
6407       free (exit_prob);
6408       free (exit_flag);
6409       free (exit_succ);
6410     }
6411   free (entry_prob);
6412   free (entry_flag);
6413   free (entry_pred);
6414   VEC_free (basic_block, heap, bbs);
6415
6416   return bb;
6417 }
6418
6419
6420 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree-pass.h)
6421    */
6422
6423 void
6424 dump_function_to_file (tree fn, FILE *file, int flags)
6425 {
6426   tree arg, var;
6427   struct function *dsf;
6428   bool ignore_topmost_bind = false, any_var = false;
6429   basic_block bb;
6430   tree chain;
6431
6432   fprintf (file, "%s (", lang_hooks.decl_printable_name (fn, 2));
6433
6434   arg = DECL_ARGUMENTS (fn);
6435   while (arg)
6436     {
6437       print_generic_expr (file, TREE_TYPE (arg), dump_flags);
6438       fprintf (file, " ");
6439       print_generic_expr (file, arg, dump_flags);
6440       if (flags & TDF_VERBOSE)
6441         print_node (file, "", arg, 4);
6442       if (DECL_CHAIN (arg))
6443         fprintf (file, ", ");
6444       arg = DECL_CHAIN (arg);
6445     }
6446   fprintf (file, ")\n");
6447
6448   if (flags & TDF_VERBOSE)
6449     print_node (file, "", fn, 2);
6450
6451   dsf = DECL_STRUCT_FUNCTION (fn);
6452   if (dsf && (flags & TDF_EH))
6453     dump_eh_tree (file, dsf);
6454
6455   if (flags & TDF_RAW && !gimple_has_body_p (fn))
6456     {
6457       dump_node (fn, TDF_SLIM | flags, file);
6458       return;
6459     }
6460
6461   /* Switch CFUN to point to FN.  */
6462   push_cfun (DECL_STRUCT_FUNCTION (fn));
6463
6464   /* When GIMPLE is lowered, the variables are no longer available in
6465      BIND_EXPRs, so display them separately.  */
6466   if (cfun && cfun->decl == fn && !VEC_empty (tree, cfun->local_decls))
6467     {
6468       unsigned ix;
6469       ignore_topmost_bind = true;
6470
6471       fprintf (file, "{\n");
6472       FOR_EACH_LOCAL_DECL (cfun, ix, var)
6473         {
6474           print_generic_decl (file, var, flags);
6475           if (flags & TDF_VERBOSE)
6476             print_node (file, "", var, 4);
6477           fprintf (file, "\n");
6478
6479           any_var = true;
6480         }
6481     }
6482
6483   if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info)
6484     {
6485       /* If the CFG has been built, emit a CFG-based dump.  */
6486       check_bb_profile (ENTRY_BLOCK_PTR, file);
6487       if (!ignore_topmost_bind)
6488         fprintf (file, "{\n");
6489
6490       if (any_var && n_basic_blocks)
6491         fprintf (file, "\n");
6492
6493       FOR_EACH_BB (bb)
6494         gimple_dump_bb (bb, file, 2, flags);
6495
6496       fprintf (file, "}\n");
6497       check_bb_profile (EXIT_BLOCK_PTR, file);
6498     }
6499   else if (DECL_SAVED_TREE (fn) == NULL)
6500     {
6501       /* The function is now in GIMPLE form but the CFG has not been
6502          built yet.  Emit the single sequence of GIMPLE statements
6503          that make up its body.  */
6504       gimple_seq body = gimple_body (fn);
6505
6506       if (gimple_seq_first_stmt (body)
6507           && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body)
6508           && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND)
6509         print_gimple_seq (file, body, 0, flags);
6510       else
6511         {
6512           if (!ignore_topmost_bind)
6513             fprintf (file, "{\n");
6514
6515           if (any_var)
6516             fprintf (file, "\n");
6517
6518           print_gimple_seq (file, body, 2, flags);
6519           fprintf (file, "}\n");
6520         }
6521     }
6522   else
6523     {
6524       int indent;
6525
6526       /* Make a tree based dump.  */
6527       chain = DECL_SAVED_TREE (fn);
6528
6529       if (chain && TREE_CODE (chain) == BIND_EXPR)
6530         {
6531           if (ignore_topmost_bind)
6532             {
6533               chain = BIND_EXPR_BODY (chain);
6534               indent = 2;
6535             }
6536           else
6537             indent = 0;
6538         }
6539       else
6540         {
6541           if (!ignore_topmost_bind)
6542             fprintf (file, "{\n");
6543           indent = 2;
6544         }
6545
6546       if (any_var)
6547         fprintf (file, "\n");
6548
6549       print_generic_stmt_indented (file, chain, flags, indent);
6550       if (ignore_topmost_bind)
6551         fprintf (file, "}\n");
6552     }
6553
6554   if (flags & TDF_ENUMERATE_LOCALS)
6555     dump_enumerated_decls (file, flags);
6556   fprintf (file, "\n\n");
6557
6558   /* Restore CFUN.  */
6559   pop_cfun ();
6560 }
6561
6562
6563 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h)  */
6564
6565 DEBUG_FUNCTION void
6566 debug_function (tree fn, int flags)
6567 {
6568   dump_function_to_file (fn, stderr, flags);
6569 }
6570
6571
6572 /* Print on FILE the indexes for the predecessors of basic_block BB.  */
6573
6574 static void
6575 print_pred_bbs (FILE *file, basic_block bb)
6576 {
6577   edge e;
6578   edge_iterator ei;
6579
6580   FOR_EACH_EDGE (e, ei, bb->preds)
6581     fprintf (file, "bb_%d ", e->src->index);
6582 }
6583
6584
6585 /* Print on FILE the indexes for the successors of basic_block BB.  */
6586
6587 static void
6588 print_succ_bbs (FILE *file, basic_block bb)
6589 {
6590   edge e;
6591   edge_iterator ei;
6592
6593   FOR_EACH_EDGE (e, ei, bb->succs)
6594     fprintf (file, "bb_%d ", e->dest->index);
6595 }
6596
6597 /* Print to FILE the basic block BB following the VERBOSITY level.  */
6598
6599 void
6600 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity)
6601 {
6602   char *s_indent = (char *) alloca ((size_t) indent + 1);
6603   memset ((void *) s_indent, ' ', (size_t) indent);
6604   s_indent[indent] = '\0';
6605
6606   /* Print basic_block's header.  */
6607   if (verbosity >= 2)
6608     {
6609       fprintf (file, "%s  bb_%d (preds = {", s_indent, bb->index);
6610       print_pred_bbs (file, bb);
6611       fprintf (file, "}, succs = {");
6612       print_succ_bbs (file, bb);
6613       fprintf (file, "})\n");
6614     }
6615
6616   /* Print basic_block's body.  */
6617   if (verbosity >= 3)
6618     {
6619       fprintf (file, "%s  {\n", s_indent);
6620       gimple_dump_bb (bb, file, indent + 4, TDF_VOPS|TDF_MEMSYMS);
6621       fprintf (file, "%s  }\n", s_indent);
6622     }
6623 }
6624
6625 static void print_loop_and_siblings (FILE *, struct loop *, int, int);
6626
6627 /* Pretty print LOOP on FILE, indented INDENT spaces.  Following
6628    VERBOSITY level this outputs the contents of the loop, or just its
6629    structure.  */
6630
6631 static void
6632 print_loop (FILE *file, struct loop *loop, int indent, int verbosity)
6633 {
6634   char *s_indent;
6635   basic_block bb;
6636
6637   if (loop == NULL)
6638     return;
6639
6640   s_indent = (char *) alloca ((size_t) indent + 1);
6641   memset ((void *) s_indent, ' ', (size_t) indent);
6642   s_indent[indent] = '\0';
6643
6644   /* Print loop's header.  */
6645   fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent,
6646            loop->num, loop->header->index, loop->latch->index);
6647   fprintf (file, ", niter = ");
6648   print_generic_expr (file, loop->nb_iterations, 0);
6649
6650   if (loop->any_upper_bound)
6651     {
6652       fprintf (file, ", upper_bound = ");
6653       dump_double_int (file, loop->nb_iterations_upper_bound, true);
6654     }
6655
6656   if (loop->any_estimate)
6657     {
6658       fprintf (file, ", estimate = ");
6659       dump_double_int (file, loop->nb_iterations_estimate, true);
6660     }
6661   fprintf (file, ")\n");
6662
6663   /* Print loop's body.  */
6664   if (verbosity >= 1)
6665     {
6666       fprintf (file, "%s{\n", s_indent);
6667       FOR_EACH_BB (bb)
6668         if (bb->loop_father == loop)
6669           print_loops_bb (file, bb, indent, verbosity);
6670
6671       print_loop_and_siblings (file, loop->inner, indent + 2, verbosity);
6672       fprintf (file, "%s}\n", s_indent);
6673     }
6674 }
6675
6676 /* Print the LOOP and its sibling loops on FILE, indented INDENT
6677    spaces.  Following VERBOSITY level this outputs the contents of the
6678    loop, or just its structure.  */
6679
6680 static void
6681 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity)
6682 {
6683   if (loop == NULL)
6684     return;
6685
6686   print_loop (file, loop, indent, verbosity);
6687   print_loop_and_siblings (file, loop->next, indent, verbosity);
6688 }
6689
6690 /* Follow a CFG edge from the entry point of the program, and on entry
6691    of a loop, pretty print the loop structure on FILE.  */
6692
6693 void
6694 print_loops (FILE *file, int verbosity)
6695 {
6696   basic_block bb;
6697
6698   bb = ENTRY_BLOCK_PTR;
6699   if (bb && bb->loop_father)
6700     print_loop_and_siblings (file, bb->loop_father, 0, verbosity);
6701 }
6702
6703
6704 /* Debugging loops structure at tree level, at some VERBOSITY level.  */
6705
6706 DEBUG_FUNCTION void
6707 debug_loops (int verbosity)
6708 {
6709   print_loops (stderr, verbosity);
6710 }
6711
6712 /* Print on stderr the code of LOOP, at some VERBOSITY level.  */
6713
6714 DEBUG_FUNCTION void
6715 debug_loop (struct loop *loop, int verbosity)
6716 {
6717   print_loop (stderr, loop, 0, verbosity);
6718 }
6719
6720 /* Print on stderr the code of loop number NUM, at some VERBOSITY
6721    level.  */
6722
6723 DEBUG_FUNCTION void
6724 debug_loop_num (unsigned num, int verbosity)
6725 {
6726   debug_loop (get_loop (num), verbosity);
6727 }
6728
6729 /* Return true if BB ends with a call, possibly followed by some
6730    instructions that must stay with the call.  Return false,
6731    otherwise.  */
6732
6733 static bool
6734 gimple_block_ends_with_call_p (basic_block bb)
6735 {
6736   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
6737   return !gsi_end_p (gsi) && is_gimple_call (gsi_stmt (gsi));
6738 }
6739
6740
6741 /* Return true if BB ends with a conditional branch.  Return false,
6742    otherwise.  */
6743
6744 static bool
6745 gimple_block_ends_with_condjump_p (const_basic_block bb)
6746 {
6747   gimple stmt = last_stmt (CONST_CAST_BB (bb));
6748   return (stmt && gimple_code (stmt) == GIMPLE_COND);
6749 }
6750
6751
6752 /* Return true if we need to add fake edge to exit at statement T.
6753    Helper function for gimple_flow_call_edges_add.  */
6754
6755 static bool
6756 need_fake_edge_p (gimple t)
6757 {
6758   tree fndecl = NULL_TREE;
6759   int call_flags = 0;
6760
6761   /* NORETURN and LONGJMP calls already have an edge to exit.
6762      CONST and PURE calls do not need one.
6763      We don't currently check for CONST and PURE here, although
6764      it would be a good idea, because those attributes are
6765      figured out from the RTL in mark_constant_function, and
6766      the counter incrementation code from -fprofile-arcs
6767      leads to different results from -fbranch-probabilities.  */
6768   if (is_gimple_call (t))
6769     {
6770       fndecl = gimple_call_fndecl (t);
6771       call_flags = gimple_call_flags (t);
6772     }
6773
6774   if (is_gimple_call (t)
6775       && fndecl
6776       && DECL_BUILT_IN (fndecl)
6777       && (call_flags & ECF_NOTHROW)
6778       && !(call_flags & ECF_RETURNS_TWICE)
6779       /* fork() doesn't really return twice, but the effect of
6780          wrapping it in __gcov_fork() which calls __gcov_flush()
6781          and clears the counters before forking has the same
6782          effect as returning twice.  Force a fake edge.  */
6783       && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL
6784            && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK))
6785     return false;
6786
6787   if (is_gimple_call (t)
6788       && !(call_flags & ECF_NORETURN))
6789     return true;
6790
6791   if (gimple_code (t) == GIMPLE_ASM
6792        && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t)))
6793     return true;
6794
6795   return false;
6796 }
6797
6798
6799 /* Add fake edges to the function exit for any non constant and non
6800    noreturn calls, volatile inline assembly in the bitmap of blocks
6801    specified by BLOCKS or to the whole CFG if BLOCKS is zero.  Return
6802    the number of blocks that were split.
6803
6804    The goal is to expose cases in which entering a basic block does
6805    not imply that all subsequent instructions must be executed.  */
6806
6807 static int
6808 gimple_flow_call_edges_add (sbitmap blocks)
6809 {
6810   int i;
6811   int blocks_split = 0;
6812   int last_bb = last_basic_block;
6813   bool check_last_block = false;
6814
6815   if (n_basic_blocks == NUM_FIXED_BLOCKS)
6816     return 0;
6817
6818   if (! blocks)
6819     check_last_block = true;
6820   else
6821     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
6822
6823   /* In the last basic block, before epilogue generation, there will be
6824      a fallthru edge to EXIT.  Special care is required if the last insn
6825      of the last basic block is a call because make_edge folds duplicate
6826      edges, which would result in the fallthru edge also being marked
6827      fake, which would result in the fallthru edge being removed by
6828      remove_fake_edges, which would result in an invalid CFG.
6829
6830      Moreover, we can't elide the outgoing fake edge, since the block
6831      profiler needs to take this into account in order to solve the minimal
6832      spanning tree in the case that the call doesn't return.
6833
6834      Handle this by adding a dummy instruction in a new last basic block.  */
6835   if (check_last_block)
6836     {
6837       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
6838       gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
6839       gimple t = NULL;
6840
6841       if (!gsi_end_p (gsi))
6842         t = gsi_stmt (gsi);
6843
6844       if (t && need_fake_edge_p (t))
6845         {
6846           edge e;
6847
6848           e = find_edge (bb, EXIT_BLOCK_PTR);
6849           if (e)
6850             {
6851               gsi_insert_on_edge (e, gimple_build_nop ());
6852               gsi_commit_edge_inserts ();
6853             }
6854         }
6855     }
6856
6857   /* Now add fake edges to the function exit for any non constant
6858      calls since there is no way that we can determine if they will
6859      return or not...  */
6860   for (i = 0; i < last_bb; i++)
6861     {
6862       basic_block bb = BASIC_BLOCK (i);
6863       gimple_stmt_iterator gsi;
6864       gimple stmt, last_stmt;
6865
6866       if (!bb)
6867         continue;
6868
6869       if (blocks && !TEST_BIT (blocks, i))
6870         continue;
6871
6872       gsi = gsi_last_nondebug_bb (bb);
6873       if (!gsi_end_p (gsi))
6874         {
6875           last_stmt = gsi_stmt (gsi);
6876           do
6877             {
6878               stmt = gsi_stmt (gsi);
6879               if (need_fake_edge_p (stmt))
6880                 {
6881                   edge e;
6882
6883                   /* The handling above of the final block before the
6884                      epilogue should be enough to verify that there is
6885                      no edge to the exit block in CFG already.
6886                      Calling make_edge in such case would cause us to
6887                      mark that edge as fake and remove it later.  */
6888 #ifdef ENABLE_CHECKING
6889                   if (stmt == last_stmt)
6890                     {
6891                       e = find_edge (bb, EXIT_BLOCK_PTR);
6892                       gcc_assert (e == NULL);
6893                     }
6894 #endif
6895
6896                   /* Note that the following may create a new basic block
6897                      and renumber the existing basic blocks.  */
6898                   if (stmt != last_stmt)
6899                     {
6900                       e = split_block (bb, stmt);
6901                       if (e)
6902                         blocks_split++;
6903                     }
6904                   make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
6905                 }
6906               gsi_prev (&gsi);
6907             }
6908           while (!gsi_end_p (gsi));
6909         }
6910     }
6911
6912   if (blocks_split)
6913     verify_flow_info ();
6914
6915   return blocks_split;
6916 }
6917
6918 /* Removes edge E and all the blocks dominated by it, and updates dominance
6919    information.  The IL in E->src needs to be updated separately.
6920    If dominance info is not available, only the edge E is removed.*/
6921
6922 void
6923 remove_edge_and_dominated_blocks (edge e)
6924 {
6925   VEC (basic_block, heap) *bbs_to_remove = NULL;
6926   VEC (basic_block, heap) *bbs_to_fix_dom = NULL;
6927   bitmap df, df_idom;
6928   edge f;
6929   edge_iterator ei;
6930   bool none_removed = false;
6931   unsigned i;
6932   basic_block bb, dbb;
6933   bitmap_iterator bi;
6934
6935   if (!dom_info_available_p (CDI_DOMINATORS))
6936     {
6937       remove_edge (e);
6938       return;
6939     }
6940
6941   /* No updating is needed for edges to exit.  */
6942   if (e->dest == EXIT_BLOCK_PTR)
6943     {
6944       if (cfgcleanup_altered_bbs)
6945         bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
6946       remove_edge (e);
6947       return;
6948     }
6949
6950   /* First, we find the basic blocks to remove.  If E->dest has a predecessor
6951      that is not dominated by E->dest, then this set is empty.  Otherwise,
6952      all the basic blocks dominated by E->dest are removed.
6953
6954      Also, to DF_IDOM we store the immediate dominators of the blocks in
6955      the dominance frontier of E (i.e., of the successors of the
6956      removed blocks, if there are any, and of E->dest otherwise).  */
6957   FOR_EACH_EDGE (f, ei, e->dest->preds)
6958     {
6959       if (f == e)
6960         continue;
6961
6962       if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest))
6963         {
6964           none_removed = true;
6965           break;
6966         }
6967     }
6968
6969   df = BITMAP_ALLOC (NULL);
6970   df_idom = BITMAP_ALLOC (NULL);
6971
6972   if (none_removed)
6973     bitmap_set_bit (df_idom,
6974                     get_immediate_dominator (CDI_DOMINATORS, e->dest)->index);
6975   else
6976     {
6977       bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest);
6978       FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb)
6979         {
6980           FOR_EACH_EDGE (f, ei, bb->succs)
6981             {
6982               if (f->dest != EXIT_BLOCK_PTR)
6983                 bitmap_set_bit (df, f->dest->index);
6984             }
6985         }
6986       FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb)
6987         bitmap_clear_bit (df, bb->index);
6988
6989       EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi)
6990         {
6991           bb = BASIC_BLOCK (i);
6992           bitmap_set_bit (df_idom,
6993                           get_immediate_dominator (CDI_DOMINATORS, bb)->index);
6994         }
6995     }
6996
6997   if (cfgcleanup_altered_bbs)
6998     {
6999       /* Record the set of the altered basic blocks.  */
7000       bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index);
7001       bitmap_ior_into (cfgcleanup_altered_bbs, df);
7002     }
7003
7004   /* Remove E and the cancelled blocks.  */
7005   if (none_removed)
7006     remove_edge (e);
7007   else
7008     {
7009       /* Walk backwards so as to get a chance to substitute all
7010          released DEFs into debug stmts.  See
7011          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
7012          details.  */
7013       for (i = VEC_length (basic_block, bbs_to_remove); i-- > 0; )
7014         delete_basic_block (VEC_index (basic_block, bbs_to_remove, i));
7015     }
7016
7017   /* Update the dominance information.  The immediate dominator may change only
7018      for blocks whose immediate dominator belongs to DF_IDOM:
7019
7020      Suppose that idom(X) = Y before removal of E and idom(X) != Y after the
7021      removal.  Let Z the arbitrary block such that idom(Z) = Y and
7022      Z dominates X after the removal.  Before removal, there exists a path P
7023      from Y to X that avoids Z.  Let F be the last edge on P that is
7024      removed, and let W = F->dest.  Before removal, idom(W) = Y (since Y
7025      dominates W, and because of P, Z does not dominate W), and W belongs to
7026      the dominance frontier of E.  Therefore, Y belongs to DF_IDOM.  */
7027   EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi)
7028     {
7029       bb = BASIC_BLOCK (i);
7030       for (dbb = first_dom_son (CDI_DOMINATORS, bb);
7031            dbb;
7032            dbb = next_dom_son (CDI_DOMINATORS, dbb))
7033         VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb);
7034     }
7035
7036   iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
7037
7038   BITMAP_FREE (df);
7039   BITMAP_FREE (df_idom);
7040   VEC_free (basic_block, heap, bbs_to_remove);
7041   VEC_free (basic_block, heap, bbs_to_fix_dom);
7042 }
7043
7044 /* Purge dead EH edges from basic block BB.  */
7045
7046 bool
7047 gimple_purge_dead_eh_edges (basic_block bb)
7048 {
7049   bool changed = false;
7050   edge e;
7051   edge_iterator ei;
7052   gimple stmt = last_stmt (bb);
7053
7054   if (stmt && stmt_can_throw_internal (stmt))
7055     return false;
7056
7057   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7058     {
7059       if (e->flags & EDGE_EH)
7060         {
7061           remove_edge_and_dominated_blocks (e);
7062           changed = true;
7063         }
7064       else
7065         ei_next (&ei);
7066     }
7067
7068   return changed;
7069 }
7070
7071 /* Purge dead EH edges from basic block listed in BLOCKS.  */
7072
7073 bool
7074 gimple_purge_all_dead_eh_edges (const_bitmap blocks)
7075 {
7076   bool changed = false;
7077   unsigned i;
7078   bitmap_iterator bi;
7079
7080   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7081     {
7082       basic_block bb = BASIC_BLOCK (i);
7083
7084       /* Earlier gimple_purge_dead_eh_edges could have removed
7085          this basic block already.  */
7086       gcc_assert (bb || changed);
7087       if (bb != NULL)
7088         changed |= gimple_purge_dead_eh_edges (bb);
7089     }
7090
7091   return changed;
7092 }
7093
7094 /* Purge dead abnormal call edges from basic block BB.  */
7095
7096 bool
7097 gimple_purge_dead_abnormal_call_edges (basic_block bb)
7098 {
7099   bool changed = false;
7100   edge e;
7101   edge_iterator ei;
7102   gimple stmt = last_stmt (bb);
7103
7104   if (!cfun->has_nonlocal_label)
7105     return false;
7106
7107   if (stmt && stmt_can_make_abnormal_goto (stmt))
7108     return false;
7109
7110   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
7111     {
7112       if (e->flags & EDGE_ABNORMAL)
7113         {
7114           remove_edge_and_dominated_blocks (e);
7115           changed = true;
7116         }
7117       else
7118         ei_next (&ei);
7119     }
7120
7121   return changed;
7122 }
7123
7124 /* Purge dead abnormal call edges from basic block listed in BLOCKS.  */
7125
7126 bool
7127 gimple_purge_all_dead_abnormal_call_edges (const_bitmap blocks)
7128 {
7129   bool changed = false;
7130   unsigned i;
7131   bitmap_iterator bi;
7132
7133   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
7134     {
7135       basic_block bb = BASIC_BLOCK (i);
7136
7137       /* Earlier gimple_purge_dead_abnormal_call_edges could have removed
7138          this basic block already.  */
7139       gcc_assert (bb || changed);
7140       if (bb != NULL)
7141         changed |= gimple_purge_dead_abnormal_call_edges (bb);
7142     }
7143
7144   return changed;
7145 }
7146
7147 /* This function is called whenever a new edge is created or
7148    redirected.  */
7149
7150 static void
7151 gimple_execute_on_growing_pred (edge e)
7152 {
7153   basic_block bb = e->dest;
7154
7155   if (!gimple_seq_empty_p (phi_nodes (bb)))
7156     reserve_phi_args_for_new_edge (bb);
7157 }
7158
7159 /* This function is called immediately before edge E is removed from
7160    the edge vector E->dest->preds.  */
7161
7162 static void
7163 gimple_execute_on_shrinking_pred (edge e)
7164 {
7165   if (!gimple_seq_empty_p (phi_nodes (e->dest)))
7166     remove_phi_args (e);
7167 }
7168
7169 /*---------------------------------------------------------------------------
7170   Helper functions for Loop versioning
7171   ---------------------------------------------------------------------------*/
7172
7173 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
7174    of 'first'. Both of them are dominated by 'new_head' basic block. When
7175    'new_head' was created by 'second's incoming edge it received phi arguments
7176    on the edge by split_edge(). Later, additional edge 'e' was created to
7177    connect 'new_head' and 'first'. Now this routine adds phi args on this
7178    additional edge 'e' that new_head to second edge received as part of edge
7179    splitting.  */
7180
7181 static void
7182 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second,
7183                                   basic_block new_head, edge e)
7184 {
7185   gimple phi1, phi2;
7186   gimple_stmt_iterator psi1, psi2;
7187   tree def;
7188   edge e2 = find_edge (new_head, second);
7189
7190   /* Because NEW_HEAD has been created by splitting SECOND's incoming
7191      edge, we should always have an edge from NEW_HEAD to SECOND.  */
7192   gcc_assert (e2 != NULL);
7193
7194   /* Browse all 'second' basic block phi nodes and add phi args to
7195      edge 'e' for 'first' head. PHI args are always in correct order.  */
7196
7197   for (psi2 = gsi_start_phis (second),
7198        psi1 = gsi_start_phis (first);
7199        !gsi_end_p (psi2) && !gsi_end_p (psi1);
7200        gsi_next (&psi2),  gsi_next (&psi1))
7201     {
7202       phi1 = gsi_stmt (psi1);
7203       phi2 = gsi_stmt (psi2);
7204       def = PHI_ARG_DEF (phi2, e2->dest_idx);
7205       add_phi_arg (phi1, def, e, gimple_phi_arg_location_from_edge (phi2, e2));
7206     }
7207 }
7208
7209
7210 /* Adds a if else statement to COND_BB with condition COND_EXPR.
7211    SECOND_HEAD is the destination of the THEN and FIRST_HEAD is
7212    the destination of the ELSE part.  */
7213
7214 static void
7215 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED,
7216                                basic_block second_head ATTRIBUTE_UNUSED,
7217                                basic_block cond_bb, void *cond_e)
7218 {
7219   gimple_stmt_iterator gsi;
7220   gimple new_cond_expr;
7221   tree cond_expr = (tree) cond_e;
7222   edge e0;
7223
7224   /* Build new conditional expr */
7225   new_cond_expr = gimple_build_cond_from_tree (cond_expr,
7226                                                NULL_TREE, NULL_TREE);
7227
7228   /* Add new cond in cond_bb.  */
7229   gsi = gsi_last_bb (cond_bb);
7230   gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT);
7231
7232   /* Adjust edges appropriately to connect new head with first head
7233      as well as second head.  */
7234   e0 = single_succ_edge (cond_bb);
7235   e0->flags &= ~EDGE_FALLTHRU;
7236   e0->flags |= EDGE_FALSE_VALUE;
7237 }
7238
7239 struct cfg_hooks gimple_cfg_hooks = {
7240   "gimple",
7241   gimple_verify_flow_info,
7242   gimple_dump_bb,               /* dump_bb  */
7243   create_bb,                    /* create_basic_block  */
7244   gimple_redirect_edge_and_branch, /* redirect_edge_and_branch  */
7245   gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force  */
7246   gimple_can_remove_branch_p,   /* can_remove_branch_p  */
7247   remove_bb,                    /* delete_basic_block  */
7248   gimple_split_block,           /* split_block  */
7249   gimple_move_block_after,      /* move_block_after  */
7250   gimple_can_merge_blocks_p,    /* can_merge_blocks_p  */
7251   gimple_merge_blocks,          /* merge_blocks  */
7252   gimple_predict_edge,          /* predict_edge  */
7253   gimple_predicted_by_p,        /* predicted_by_p  */
7254   gimple_can_duplicate_bb_p,    /* can_duplicate_block_p  */
7255   gimple_duplicate_bb,          /* duplicate_block  */
7256   gimple_split_edge,            /* split_edge  */
7257   gimple_make_forwarder_block,  /* make_forward_block  */
7258   NULL,                         /* tidy_fallthru_edge  */
7259   NULL,                         /* force_nonfallthru */
7260   gimple_block_ends_with_call_p,/* block_ends_with_call_p */
7261   gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */
7262   gimple_flow_call_edges_add,   /* flow_call_edges_add */
7263   gimple_execute_on_growing_pred,       /* execute_on_growing_pred */
7264   gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */
7265   gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */
7266   gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
7267   gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/
7268   extract_true_false_edges_from_block, /* extract_cond_bb_edges */
7269   flush_pending_stmts           /* flush_pending_stmts */
7270 };
7271
7272
7273 /* Split all critical edges.  */
7274
7275 static unsigned int
7276 split_critical_edges (void)
7277 {
7278   basic_block bb;
7279   edge e;
7280   edge_iterator ei;
7281
7282   /* split_edge can redirect edges out of SWITCH_EXPRs, which can get
7283      expensive.  So we want to enable recording of edge to CASE_LABEL_EXPR
7284      mappings around the calls to split_edge.  */
7285   start_recording_case_labels ();
7286   FOR_ALL_BB (bb)
7287     {
7288       FOR_EACH_EDGE (e, ei, bb->succs)
7289         {
7290           if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL))
7291             split_edge (e);
7292           /* PRE inserts statements to edges and expects that
7293              since split_critical_edges was done beforehand, committing edge
7294              insertions will not split more edges.  In addition to critical
7295              edges we must split edges that have multiple successors and
7296              end by control flow statements, such as RESX.
7297              Go ahead and split them too.  This matches the logic in
7298              gimple_find_edge_insert_loc.  */
7299           else if ((!single_pred_p (e->dest)
7300                     || !gimple_seq_empty_p (phi_nodes (e->dest))
7301                     || e->dest == EXIT_BLOCK_PTR)
7302                    && e->src != ENTRY_BLOCK_PTR
7303                    && !(e->flags & EDGE_ABNORMAL))
7304             {
7305               gimple_stmt_iterator gsi;
7306
7307               gsi = gsi_last_bb (e->src);
7308               if (!gsi_end_p (gsi)
7309                   && stmt_ends_bb_p (gsi_stmt (gsi))
7310                   && (gimple_code (gsi_stmt (gsi)) != GIMPLE_RETURN
7311                       && !gimple_call_builtin_p (gsi_stmt (gsi),
7312                                                  BUILT_IN_RETURN)))
7313                 split_edge (e);
7314             }
7315         }
7316     }
7317   end_recording_case_labels ();
7318   return 0;
7319 }
7320
7321 struct gimple_opt_pass pass_split_crit_edges =
7322 {
7323  {
7324   GIMPLE_PASS,
7325   "crited",                          /* name */
7326   NULL,                          /* gate */
7327   split_critical_edges,          /* execute */
7328   NULL,                          /* sub */
7329   NULL,                          /* next */
7330   0,                             /* static_pass_number */
7331   TV_TREE_SPLIT_EDGES,           /* tv_id */
7332   PROP_cfg,                      /* properties required */
7333   PROP_no_crit_edges,            /* properties_provided */
7334   0,                             /* properties_destroyed */
7335   0,                             /* todo_flags_start */
7336   TODO_verify_flow               /* todo_flags_finish */
7337  }
7338 };
7339
7340
7341 /* Build a ternary operation and gimplify it.  Emit code before GSI.
7342    Return the gimple_val holding the result.  */
7343
7344 tree
7345 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code,
7346                  tree type, tree a, tree b, tree c)
7347 {
7348   tree ret;
7349   location_t loc = gimple_location (gsi_stmt (*gsi));
7350
7351   ret = fold_build3_loc (loc, code, type, a, b, c);
7352   STRIP_NOPS (ret);
7353
7354   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7355                                    GSI_SAME_STMT);
7356 }
7357
7358 /* Build a binary operation and gimplify it.  Emit code before GSI.
7359    Return the gimple_val holding the result.  */
7360
7361 tree
7362 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code,
7363                  tree type, tree a, tree b)
7364 {
7365   tree ret;
7366
7367   ret = fold_build2_loc (gimple_location (gsi_stmt (*gsi)), code, type, a, b);
7368   STRIP_NOPS (ret);
7369
7370   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7371                                    GSI_SAME_STMT);
7372 }
7373
7374 /* Build a unary operation and gimplify it.  Emit code before GSI.
7375    Return the gimple_val holding the result.  */
7376
7377 tree
7378 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type,
7379                  tree a)
7380 {
7381   tree ret;
7382
7383   ret = fold_build1_loc (gimple_location (gsi_stmt (*gsi)), code, type, a);
7384   STRIP_NOPS (ret);
7385
7386   return force_gimple_operand_gsi (gsi, ret, true, NULL, true,
7387                                    GSI_SAME_STMT);
7388 }
7389
7390
7391 \f
7392 /* Emit return warnings.  */
7393
7394 static unsigned int
7395 execute_warn_function_return (void)
7396 {
7397   source_location location;
7398   gimple last;
7399   edge e;
7400   edge_iterator ei;
7401
7402   /* If we have a path to EXIT, then we do return.  */
7403   if (TREE_THIS_VOLATILE (cfun->decl)
7404       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0)
7405     {
7406       location = UNKNOWN_LOCATION;
7407       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7408         {
7409           last = last_stmt (e->src);
7410           if ((gimple_code (last) == GIMPLE_RETURN
7411                || gimple_call_builtin_p (last, BUILT_IN_RETURN))
7412               && (location = gimple_location (last)) != UNKNOWN_LOCATION)
7413             break;
7414         }
7415       if (location == UNKNOWN_LOCATION)
7416         location = cfun->function_end_locus;
7417       warning_at (location, 0, "%<noreturn%> function does return");
7418     }
7419
7420   /* If we see "return;" in some basic block, then we do reach the end
7421      without returning a value.  */
7422   else if (warn_return_type
7423            && !TREE_NO_WARNING (cfun->decl)
7424            && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0
7425            && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl))))
7426     {
7427       FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
7428         {
7429           gimple last = last_stmt (e->src);
7430           if (gimple_code (last) == GIMPLE_RETURN
7431               && gimple_return_retval (last) == NULL
7432               && !gimple_no_warning_p (last))
7433             {
7434               location = gimple_location (last);
7435               if (location == UNKNOWN_LOCATION)
7436                   location = cfun->function_end_locus;
7437               warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function");
7438               TREE_NO_WARNING (cfun->decl) = 1;
7439               break;
7440             }
7441         }
7442     }
7443   return 0;
7444 }
7445
7446
7447 /* Given a basic block B which ends with a conditional and has
7448    precisely two successors, determine which of the edges is taken if
7449    the conditional is true and which is taken if the conditional is
7450    false.  Set TRUE_EDGE and FALSE_EDGE appropriately.  */
7451
7452 void
7453 extract_true_false_edges_from_block (basic_block b,
7454                                      edge *true_edge,
7455                                      edge *false_edge)
7456 {
7457   edge e = EDGE_SUCC (b, 0);
7458
7459   if (e->flags & EDGE_TRUE_VALUE)
7460     {
7461       *true_edge = e;
7462       *false_edge = EDGE_SUCC (b, 1);
7463     }
7464   else
7465     {
7466       *false_edge = e;
7467       *true_edge = EDGE_SUCC (b, 1);
7468     }
7469 }
7470
7471 struct gimple_opt_pass pass_warn_function_return =
7472 {
7473  {
7474   GIMPLE_PASS,
7475   "*warn_function_return",              /* name */
7476   NULL,                                 /* gate */
7477   execute_warn_function_return,         /* execute */
7478   NULL,                                 /* sub */
7479   NULL,                                 /* next */
7480   0,                                    /* static_pass_number */
7481   TV_NONE,                              /* tv_id */
7482   PROP_cfg,                             /* properties_required */
7483   0,                                    /* properties_provided */
7484   0,                                    /* properties_destroyed */
7485   0,                                    /* todo_flags_start */
7486   0                                     /* todo_flags_finish */
7487  }
7488 };
7489
7490 /* Emit noreturn warnings.  */
7491
7492 static unsigned int
7493 execute_warn_function_noreturn (void)
7494 {
7495   if (!TREE_THIS_VOLATILE (current_function_decl)
7496       && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0)
7497     warn_function_noreturn (current_function_decl);
7498   return 0;
7499 }
7500
7501 static bool
7502 gate_warn_function_noreturn (void)
7503 {
7504   return warn_suggest_attribute_noreturn;
7505 }
7506
7507 struct gimple_opt_pass pass_warn_function_noreturn =
7508 {
7509  {
7510   GIMPLE_PASS,
7511   "*warn_function_noreturn",            /* name */
7512   gate_warn_function_noreturn,          /* gate */
7513   execute_warn_function_noreturn,       /* execute */
7514   NULL,                                 /* sub */
7515   NULL,                                 /* next */
7516   0,                                    /* static_pass_number */
7517   TV_NONE,                              /* tv_id */
7518   PROP_cfg,                             /* properties_required */
7519   0,                                    /* properties_provided */
7520   0,                                    /* properties_destroyed */
7521   0,                                    /* todo_flags_start */
7522   0                                     /* todo_flags_finish */
7523  }
7524 };
7525
7526
7527 /* Walk a gimplified function and warn for functions whose return value is
7528    ignored and attribute((warn_unused_result)) is set.  This is done before
7529    inlining, so we don't have to worry about that.  */
7530
7531 static void
7532 do_warn_unused_result (gimple_seq seq)
7533 {
7534   tree fdecl, ftype;
7535   gimple_stmt_iterator i;
7536
7537   for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
7538     {
7539       gimple g = gsi_stmt (i);
7540
7541       switch (gimple_code (g))
7542         {
7543         case GIMPLE_BIND:
7544           do_warn_unused_result (gimple_bind_body (g));
7545           break;
7546         case GIMPLE_TRY:
7547           do_warn_unused_result (gimple_try_eval (g));
7548           do_warn_unused_result (gimple_try_cleanup (g));
7549           break;
7550         case GIMPLE_CATCH:
7551           do_warn_unused_result (gimple_catch_handler (g));
7552           break;
7553         case GIMPLE_EH_FILTER:
7554           do_warn_unused_result (gimple_eh_filter_failure (g));
7555           break;
7556
7557         case GIMPLE_CALL:
7558           if (gimple_call_lhs (g))
7559             break;
7560           if (gimple_call_internal_p (g))
7561             break;
7562
7563           /* This is a naked call, as opposed to a GIMPLE_CALL with an
7564              LHS.  All calls whose value is ignored should be
7565              represented like this.  Look for the attribute.  */
7566           fdecl = gimple_call_fndecl (g);
7567           ftype = gimple_call_fntype (g);
7568
7569           if (lookup_attribute ("warn_unused_result", TYPE_ATTRIBUTES (ftype)))
7570             {
7571               location_t loc = gimple_location (g);
7572
7573               if (fdecl)
7574                 warning_at (loc, OPT_Wunused_result,
7575                             "ignoring return value of %qD, "
7576                             "declared with attribute warn_unused_result",
7577                             fdecl);
7578               else
7579                 warning_at (loc, OPT_Wunused_result,
7580                             "ignoring return value of function "
7581                             "declared with attribute warn_unused_result");
7582             }
7583           break;
7584
7585         default:
7586           /* Not a container, not a call, or a call whose value is used.  */
7587           break;
7588         }
7589     }
7590 }
7591
7592 static unsigned int
7593 run_warn_unused_result (void)
7594 {
7595   do_warn_unused_result (gimple_body (current_function_decl));
7596   return 0;
7597 }
7598
7599 static bool
7600 gate_warn_unused_result (void)
7601 {
7602   return flag_warn_unused_result;
7603 }
7604
7605 struct gimple_opt_pass pass_warn_unused_result =
7606 {
7607   {
7608     GIMPLE_PASS,
7609     "*warn_unused_result",              /* name */
7610     gate_warn_unused_result,            /* gate */
7611     run_warn_unused_result,             /* execute */
7612     NULL,                               /* sub */
7613     NULL,                               /* next */
7614     0,                                  /* static_pass_number */
7615     TV_NONE,                            /* tv_id */
7616     PROP_gimple_any,                    /* properties_required */
7617     0,                                  /* properties_provided */
7618     0,                                  /* properties_destroyed */
7619     0,                                  /* todo_flags_start */
7620     0,                                  /* todo_flags_finish */
7621   }
7622 };