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, 2012  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 static bool verify_gimple_transaction (gimple);
 121
 122 /* Flowgraph optimization and cleanup.  */
 123 static void gimple_merge_blocks (basic_block, basic_block);
 124 static bool gimple_can_merge_blocks_p (basic_block, basic_block);
 125 static void remove_bb (basic_block);
 126 static edge find_taken_edge_computed_goto (basic_block, tree);
 127 static edge find_taken_edge_cond_expr (basic_block, tree);
 128 static edge find_taken_edge_switch_expr (basic_block, tree);
 129 static tree find_case_label_for_value (gimple, tree);
 130 static void group_case_labels_stmt (gimple);
 131
 132 void
 133 init_empty_tree_cfg_for_function (struct function *fn)
 134 {
 135   /* Initialize the basic block array.  */
 136   init_flow (fn);
 137   profile_status_for_function (fn) = PROFILE_ABSENT;
 138   n_basic_blocks_for_function (fn) = NUM_FIXED_BLOCKS;
 139   last_basic_block_for_function (fn) = NUM_FIXED_BLOCKS;
 140   basic_block_info_for_function (fn)
 141     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 142   VEC_safe_grow_cleared (basic_block, gc,
 143                          basic_block_info_for_function (fn),
 144                          initial_cfg_capacity);
 145
 146   /* Build a mapping of labels to their associated blocks.  */
 147   label_to_block_map_for_function (fn)
 148     = VEC_alloc (basic_block, gc, initial_cfg_capacity);
 149   VEC_safe_grow_cleared (basic_block, gc,
 150                          label_to_block_map_for_function (fn),
 151                          initial_cfg_capacity);
 152
 153   SET_BASIC_BLOCK_FOR_FUNCTION (fn, ENTRY_BLOCK,
 154                                 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn));
 155   SET_BASIC_BLOCK_FOR_FUNCTION (fn, EXIT_BLOCK,
 156                    EXIT_BLOCK_PTR_FOR_FUNCTION (fn));
 157
 158   ENTRY_BLOCK_PTR_FOR_FUNCTION (fn)->next_bb
 159     = EXIT_BLOCK_PTR_FOR_FUNCTION (fn);
 160   EXIT_BLOCK_PTR_FOR_FUNCTION (fn)->prev_bb
 161     = ENTRY_BLOCK_PTR_FOR_FUNCTION (fn);
 162 }
 163
 164 void
 165 init_empty_tree_cfg (void)
 166 {
 167   init_empty_tree_cfg_for_function (cfun);
 168 }
 169
 170 /*---------------------------------------------------------------------------
 171                               Create basic blocks
 172 ---------------------------------------------------------------------------*/
 173
 174 /* Entry point to the CFG builder for trees.  SEQ is the sequence of
 175    statements to be added to the flowgraph.  */
 176
 177 static void
 178 build_gimple_cfg (gimple_seq seq)
 179 {
 180   /* Register specific gimple functions.  */
 181   gimple_register_cfg_hooks ();
 182
 183   memset ((void *) &cfg_stats, 0, sizeof (cfg_stats));
 184
 185   init_empty_tree_cfg ();
 186
 187   found_computed_goto = 0;
 188   make_blocks (seq);
 189
 190   /* Computed gotos are hell to deal with, especially if there are
 191      lots of them with a large number of destinations.  So we factor
 192      them to a common computed goto location before we build the
 193      edge list.  After we convert back to normal form, we will un-factor
 194      the computed gotos since factoring introduces an unwanted jump.  */
 195   if (found_computed_goto)
 196     factor_computed_gotos ();
 197
 198   /* Make sure there is always at least one block, even if it's empty.  */
 199   if (n_basic_blocks == NUM_FIXED_BLOCKS)
 200     create_empty_bb (ENTRY_BLOCK_PTR);
 201
 202   /* Adjust the size of the array.  */
 203   if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks)
 204     VEC_safe_grow_cleared (basic_block, gc, basic_block_info, n_basic_blocks);
 205
 206   /* To speed up statement iterator walks, we first purge dead labels.  */
 207   cleanup_dead_labels ();
 208
 209   /* Group case nodes to reduce the number of edges.
 210      We do this after cleaning up dead labels because otherwise we miss
 211      a lot of obvious case merging opportunities.  */
 212   group_case_labels ();
 213
 214   /* Create the edges of the flowgraph.  */
 215   discriminator_per_locus = htab_create (13, locus_map_hash, locus_map_eq,
 216                                          free);
 217   make_edges ();
 218   cleanup_dead_labels ();
 219   htab_delete (discriminator_per_locus);
 220
 221   /* Debugging dumps.  */
 222
 223   /* Write the flowgraph to a VCG file.  */
 224   {
 225     int local_dump_flags;
 226     FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags);
 227     if (vcg_file)
 228       {
 229         gimple_cfg2vcg (vcg_file);
 230         dump_end (TDI_vcg, vcg_file);
 231       }
 232   }
 233 }
 234
 235 static unsigned int
 236 execute_build_cfg (void)
 237 {
 238   gimple_seq body = gimple_body (current_function_decl);
 239
 240   build_gimple_cfg (body);
 241   gimple_set_body (current_function_decl, NULL);
 242   if (dump_file && (dump_flags & TDF_DETAILS))
 243     {
 244       fprintf (dump_file, "Scope blocks:\n");
 245       dump_scope_blocks (dump_file, dump_flags);
 246     }
 247   return 0;
 248 }
 249
 250 struct gimple_opt_pass pass_build_cfg =
 251 {
 252  {
 253   GIMPLE_PASS,
 254   "cfg",                                /* name */
 255   NULL,                                 /* gate */
 256   execute_build_cfg,                    /* execute */
 257   NULL,                                 /* sub */
 258   NULL,                                 /* next */
 259   0,                                    /* static_pass_number */
 260   TV_TREE_CFG,                          /* tv_id */
 261   PROP_gimple_leh,                      /* properties_required */
 262   PROP_cfg,                             /* properties_provided */
 263   0,                                    /* properties_destroyed */
 264   0,                                    /* todo_flags_start */
 265   TODO_verify_stmts | TODO_cleanup_cfg  /* todo_flags_finish */
 266  }
 267 };
 268
 269
 270 /* Return true if T is a computed goto.  */
 271
 272 static bool
 273 computed_goto_p (gimple t)
 274 {
 275   return (gimple_code (t) == GIMPLE_GOTO
 276           && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
 277 }
 278
 279
 280 /* Search the CFG for any computed gotos.  If found, factor them to a
 281    common computed goto site.  Also record the location of that site so
 282    that we can un-factor the gotos after we have converted back to
 283    normal form.  */
 284
 285 static void
 286 factor_computed_gotos (void)
 287 {
 288   basic_block bb;
 289   tree factored_label_decl = NULL;
 290   tree var = NULL;
 291   gimple factored_computed_goto_label = NULL;
 292   gimple factored_computed_goto = NULL;
 293
 294   /* We know there are one or more computed gotos in this function.
 295      Examine the last statement in each basic block to see if the block
 296      ends with a computed goto.  */
 297
 298   FOR_EACH_BB (bb)
 299     {
 300       gimple_stmt_iterator gsi = gsi_last_bb (bb);
 301       gimple last;
 302
 303       if (gsi_end_p (gsi))
 304         continue;
 305
 306       last = gsi_stmt (gsi);
 307
 308       /* Ignore the computed goto we create when we factor the original
 309          computed gotos.  */
 310       if (last == factored_computed_goto)
 311         continue;
 312
 313       /* If the last statement is a computed goto, factor it.  */
 314       if (computed_goto_p (last))
 315         {
 316           gimple assignment;
 317
 318           /* The first time we find a computed goto we need to create
 319              the factored goto block and the variable each original
 320              computed goto will use for their goto destination.  */
 321           if (!factored_computed_goto)
 322             {
 323               basic_block new_bb = create_empty_bb (bb);
 324               gimple_stmt_iterator new_gsi = gsi_start_bb (new_bb);
 325
 326               /* Create the destination of the factored goto.  Each original
 327                  computed goto will put its desired destination into this
 328                  variable and jump to the label we create immediately
 329                  below.  */
 330               var = create_tmp_var (ptr_type_node, "gotovar");
 331
 332               /* Build a label for the new block which will contain the
 333                  factored computed goto.  */
 334               factored_label_decl = create_artificial_label (UNKNOWN_LOCATION);
 335               factored_computed_goto_label
 336                 = gimple_build_label (factored_label_decl);
 337               gsi_insert_after (&new_gsi, factored_computed_goto_label,
 338                                 GSI_NEW_STMT);
 339
 340               /* Build our new computed goto.  */
 341               factored_computed_goto = gimple_build_goto (var);
 342               gsi_insert_after (&new_gsi, factored_computed_goto, GSI_NEW_STMT);
 343             }
 344
 345           /* Copy the original computed goto's destination into VAR.  */
 346           assignment = gimple_build_assign (var, gimple_goto_dest (last));
 347           gsi_insert_before (&gsi, assignment, GSI_SAME_STMT);
 348
 349           /* And re-vector the computed goto to the new destination.  */
 350           gimple_goto_set_dest (last, factored_label_decl);
 351         }
 352     }
 353 }
 354
 355
 356 /* Build a flowgraph for the sequence of stmts SEQ.  */
 357
 358 static void
 359 make_blocks (gimple_seq seq)
 360 {
 361   gimple_stmt_iterator i = gsi_start (seq);
 362   gimple stmt = NULL;
 363   bool start_new_block = true;
 364   bool first_stmt_of_seq = true;
 365   basic_block bb = ENTRY_BLOCK_PTR;
 366
 367   while (!gsi_end_p (i))
 368     {
 369       gimple prev_stmt;
 370
 371       prev_stmt = stmt;
 372       stmt = gsi_stmt (i);
 373
 374       /* If the statement starts a new basic block or if we have determined
 375          in a previous pass that we need to create a new block for STMT, do
 376          so now.  */
 377       if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt))
 378         {
 379           if (!first_stmt_of_seq)
 380             seq = gsi_split_seq_before (&i);
 381           bb = create_basic_block (seq, NULL, bb);
 382           start_new_block = false;
 383         }
 384
 385       /* Now add STMT to BB and create the subgraphs for special statement
 386          codes.  */
 387       gimple_set_bb (stmt, bb);
 388
 389       if (computed_goto_p (stmt))
 390         found_computed_goto = true;
 391
 392       /* If STMT is a basic block terminator, set START_NEW_BLOCK for the
 393          next iteration.  */
 394       if (stmt_ends_bb_p (stmt))
 395         {
 396           /* If the stmt can make abnormal goto use a new temporary
 397              for the assignment to the LHS.  This makes sure the old value
 398              of the LHS is available on the abnormal edge.  Otherwise
 399              we will end up with overlapping life-ranges for abnormal
 400              SSA names.  */
 401           if (gimple_has_lhs (stmt)
 402               && stmt_can_make_abnormal_goto (stmt)
 403               && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt))))
 404             {
 405               tree lhs = gimple_get_lhs (stmt);
 406               tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL);
 407               gimple s = gimple_build_assign (lhs, tmp);
 408               gimple_set_location (s, gimple_location (stmt));
 409               gimple_set_block (s, gimple_block (stmt));
 410               gimple_set_lhs (stmt, tmp);
 411               if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE
 412                   || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE)
 413                 DECL_GIMPLE_REG_P (tmp) = 1;
 414               gsi_insert_after (&i, s, GSI_SAME_STMT);
 415             }
 416           start_new_block = true;
 417         }
 418
 419       gsi_next (&i);
 420       first_stmt_of_seq = false;
 421     }
 422 }
 423
 424
 425 /* Create and return a new empty basic block after bb AFTER.  */
 426
 427 static basic_block
 428 create_bb (void *h, void *e, basic_block after)
 429 {
 430   basic_block bb;
 431
 432   gcc_assert (!e);
 433
 434   /* Create and initialize a new basic block.  Since alloc_block uses
 435      GC allocation that clears memory to allocate a basic block, we do
 436      not have to clear the newly allocated basic block here.  */
 437   bb = alloc_block ();
 438
 439   bb->index = last_basic_block;
 440   bb->flags = BB_NEW;
 441   bb->il.gimple = ggc_alloc_cleared_gimple_bb_info ();
 442   set_bb_seq (bb, h ? (gimple_seq) h : gimple_seq_alloc ());
 443
 444   /* Add the new block to the linked list of blocks.  */
 445   link_block (bb, after);
 446
 447   /* Grow the basic block array if needed.  */
 448   if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info))
 449     {
 450       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
 451       VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
 452     }
 453
 454   /* Add the newly created block to the array.  */
 455   SET_BASIC_BLOCK (last_basic_block, bb);
 456
 457   n_basic_blocks++;
 458   last_basic_block++;
 459
 460   return bb;
 461 }
 462
 463
 464 /*---------------------------------------------------------------------------
 465                                  Edge creation
 466 ---------------------------------------------------------------------------*/
 467
 468 /* Fold COND_EXPR_COND of each COND_EXPR.  */
 469
 470 void
 471 fold_cond_expr_cond (void)
 472 {
 473   basic_block bb;
 474
 475   FOR_EACH_BB (bb)
 476     {
 477       gimple stmt = last_stmt (bb);
 478
 479       if (stmt && gimple_code (stmt) == GIMPLE_COND)
 480         {
 481           location_t loc = gimple_location (stmt);
 482           tree cond;
 483           bool zerop, onep;
 484
 485           fold_defer_overflow_warnings ();
 486           cond = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node,
 487                               gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
 488           if (cond)
 489             {
 490               zerop = integer_zerop (cond);
 491               onep = integer_onep (cond);
 492             }
 493           else
 494             zerop = onep = false;
 495
 496           fold_undefer_overflow_warnings (zerop || onep,
 497                                           stmt,
 498                                           WARN_STRICT_OVERFLOW_CONDITIONAL);
 499           if (zerop)
 500             gimple_cond_make_false (stmt);
 501           else if (onep)
 502             gimple_cond_make_true (stmt);
 503         }
 504     }
 505 }
 506
 507 /* Join all the blocks in the flowgraph.  */
 508
 509 static void
 510 make_edges (void)
 511 {
 512   basic_block bb;
 513   struct omp_region *cur_region = NULL;
 514
 515   /* Create an edge from entry to the first block with executable
 516      statements in it.  */
 517   make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU);
 518
 519   /* Traverse the basic block array placing edges.  */
 520   FOR_EACH_BB (bb)
 521     {
 522       gimple last = last_stmt (bb);
 523       bool fallthru;
 524
 525       if (last)
 526         {
 527           enum gimple_code code = gimple_code (last);
 528           switch (code)
 529             {
 530             case GIMPLE_GOTO:
 531               make_goto_expr_edges (bb);
 532               fallthru = false;
 533               break;
 534             case GIMPLE_RETURN:
 535               make_edge (bb, EXIT_BLOCK_PTR, 0);
 536               fallthru = false;
 537               break;
 538             case GIMPLE_COND:
 539               make_cond_expr_edges (bb);
 540               fallthru = false;
 541               break;
 542             case GIMPLE_SWITCH:
 543               make_gimple_switch_edges (bb);
 544               fallthru = false;
 545               break;
 546             case GIMPLE_RESX:
 547               make_eh_edges (last);
 548               fallthru = false;
 549               break;
 550             case GIMPLE_EH_DISPATCH:
 551               fallthru = make_eh_dispatch_edges (last);
 552               break;
 553
 554             case GIMPLE_CALL:
 555               /* If this function receives a nonlocal goto, then we need to
 556                  make edges from this call site to all the nonlocal goto
 557                  handlers.  */
 558               if (stmt_can_make_abnormal_goto (last))
 559                 make_abnormal_goto_edges (bb, true);
 560
 561               /* If this statement has reachable exception handlers, then
 562                  create abnormal edges to them.  */
 563               make_eh_edges (last);
 564
 565               /* BUILTIN_RETURN is really a return statement.  */
 566               if (gimple_call_builtin_p (last, BUILT_IN_RETURN))
 567                 make_edge (bb, EXIT_BLOCK_PTR, 0), fallthru = false;
 568               /* Some calls are known not to return.  */
 569               else
 570                 fallthru = !(gimple_call_flags (last) & ECF_NORETURN);
 571               break;
 572
 573             case GIMPLE_ASSIGN:
 574                /* A GIMPLE_ASSIGN may throw internally and thus be considered
 575                   control-altering. */
 576               if (is_ctrl_altering_stmt (last))
 577                 make_eh_edges (last);
 578               fallthru = true;
 579               break;
 580
 581             case GIMPLE_ASM:
 582               make_gimple_asm_edges (bb);
 583               fallthru = true;
 584               break;
 585
 586             case GIMPLE_OMP_PARALLEL:
 587             case GIMPLE_OMP_TASK:
 588             case GIMPLE_OMP_FOR:
 589             case GIMPLE_OMP_SINGLE:
 590             case GIMPLE_OMP_MASTER:
 591             case GIMPLE_OMP_ORDERED:
 592             case GIMPLE_OMP_CRITICAL:
 593             case GIMPLE_OMP_SECTION:
 594               cur_region = new_omp_region (bb, code, cur_region);
 595               fallthru = true;
 596               break;
 597
 598             case GIMPLE_OMP_SECTIONS:
 599               cur_region = new_omp_region (bb, code, cur_region);
 600               fallthru = true;
 601               break;
 602
 603             case GIMPLE_OMP_SECTIONS_SWITCH:
 604               fallthru = false;
 605               break;
 606
 607             case GIMPLE_OMP_ATOMIC_LOAD:
 608             case GIMPLE_OMP_ATOMIC_STORE:
 609                fallthru = true;
 610                break;
 611
 612             case GIMPLE_OMP_RETURN:
 613               /* In the case of a GIMPLE_OMP_SECTION, the edge will go
 614                  somewhere other than the next block.  This will be
 615                  created later.  */
 616               cur_region->exit = bb;
 617               fallthru = cur_region->type != GIMPLE_OMP_SECTION;
 618               cur_region = cur_region->outer;
 619               break;
 620
 621             case GIMPLE_OMP_CONTINUE:
 622               cur_region->cont = bb;
 623               switch (cur_region->type)
 624                 {
 625                 case GIMPLE_OMP_FOR:
 626                   /* Mark all GIMPLE_OMP_FOR and GIMPLE_OMP_CONTINUE
 627                      succs edges as abnormal to prevent splitting
 628                      them.  */
 629                   single_succ_edge (cur_region->entry)->flags |= EDGE_ABNORMAL;
 630                   /* Make the loopback edge.  */
 631                   make_edge (bb, single_succ (cur_region->entry),
 632                              EDGE_ABNORMAL);
 633
 634                   /* Create an edge from GIMPLE_OMP_FOR to exit, which
 635                      corresponds to the case that the body of the loop
 636                      is not executed at all.  */
 637                   make_edge (cur_region->entry, bb->next_bb, EDGE_ABNORMAL);
 638                   make_edge (bb, bb->next_bb, EDGE_FALLTHRU | EDGE_ABNORMAL);
 639                   fallthru = false;
 640                   break;
 641
 642                 case GIMPLE_OMP_SECTIONS:
 643                   /* Wire up the edges into and out of the nested sections.  */
 644                   {
 645                     basic_block switch_bb = single_succ (cur_region->entry);
 646
 647                     struct omp_region *i;
 648                     for (i = cur_region->inner; i ; i = i->next)
 649                       {
 650                         gcc_assert (i->type == GIMPLE_OMP_SECTION);
 651                         make_edge (switch_bb, i->entry, 0);
 652                         make_edge (i->exit, bb, EDGE_FALLTHRU);
 653                       }
 654
 655                     /* Make the loopback edge to the block with
 656                        GIMPLE_OMP_SECTIONS_SWITCH.  */
 657                     make_edge (bb, switch_bb, 0);
 658
 659                     /* Make the edge from the switch to exit.  */
 660                     make_edge (switch_bb, bb->next_bb, 0);
 661                     fallthru = false;
 662                   }
 663                   break;
 664
 665                 default:
 666                   gcc_unreachable ();
 667                 }
 668               break;
 669
 670             case GIMPLE_TRANSACTION:
 671               {
 672                 tree abort_label = gimple_transaction_label (last);
 673                 if (abort_label)
 674                   make_edge (bb, label_to_block (abort_label), 0);
 675                 fallthru = true;
 676               }
 677               break;
 678
 679             default:
 680               gcc_assert (!stmt_ends_bb_p (last));
 681               fallthru = true;
 682             }
 683         }
 684       else
 685         fallthru = true;
 686
 687       if (fallthru)
 688         {
 689           make_edge (bb, bb->next_bb, EDGE_FALLTHRU);
 690           if (last)
 691             assign_discriminator (gimple_location (last), bb->next_bb);
 692         }
 693     }
 694
 695   if (root_omp_region)
 696     free_omp_regions ();
 697
 698   /* Fold COND_EXPR_COND of each COND_EXPR.  */
 699   fold_cond_expr_cond ();
 700 }
 701
 702 /* Trivial hash function for a location_t.  ITEM is a pointer to
 703    a hash table entry that maps a location_t to a discriminator.  */
 704
 705 static unsigned int
 706 locus_map_hash (const void *item)
 707 {
 708   return ((const struct locus_discrim_map *) item)->locus;
 709 }
 710
 711 /* Equality function for the locus-to-discriminator map.  VA and VB
 712    point to the two hash table entries to compare.  */
 713
 714 static int
 715 locus_map_eq (const void *va, const void *vb)
 716 {
 717   const struct locus_discrim_map *a = (const struct locus_discrim_map *) va;
 718   const struct locus_discrim_map *b = (const struct locus_discrim_map *) vb;
 719   return a->locus == b->locus;
 720 }
 721
 722 /* Find the next available discriminator value for LOCUS.  The
 723    discriminator distinguishes among several basic blocks that
 724    share a common locus, allowing for more accurate sample-based
 725    profiling.  */
 726
 727 static int
 728 next_discriminator_for_locus (location_t locus)
 729 {
 730   struct locus_discrim_map item;
 731   struct locus_discrim_map **slot;
 732
 733   item.locus = locus;
 734   item.discriminator = 0;
 735   slot = (struct locus_discrim_map **)
 736       htab_find_slot_with_hash (discriminator_per_locus, (void *) &item,
 737                                 (hashval_t) locus, INSERT);
 738   gcc_assert (slot);
 739   if (*slot == HTAB_EMPTY_ENTRY)
 740     {
 741       *slot = XNEW (struct locus_discrim_map);
 742       gcc_assert (*slot);
 743       (*slot)->locus = locus;
 744       (*slot)->discriminator = 0;
 745     }
 746   (*slot)->discriminator++;
 747   return (*slot)->discriminator;
 748 }
 749
 750 /* Return TRUE if LOCUS1 and LOCUS2 refer to the same source line.  */
 751
 752 static bool
 753 same_line_p (location_t locus1, location_t locus2)
 754 {
 755   expanded_location from, to;
 756
 757   if (locus1 == locus2)
 758     return true;
 759
 760   from = expand_location (locus1);
 761   to = expand_location (locus2);
 762
 763   if (from.line != to.line)
 764     return false;
 765   if (from.file == to.file)
 766     return true;
 767   return (from.file != NULL
 768           && to.file != NULL
 769           && filename_cmp (from.file, to.file) == 0);
 770 }
 771
 772 /* Assign a unique discriminator value to block BB if it begins at the same
 773    LOCUS as its predecessor block.  */
 774
 775 static void
 776 assign_discriminator (location_t locus, basic_block bb)
 777 {
 778   gimple first_in_to_bb, last_in_to_bb;
 779
 780   if (locus == 0 || bb->discriminator != 0)
 781     return;
 782
 783   first_in_to_bb = first_non_label_stmt (bb);
 784   last_in_to_bb = last_stmt (bb);
 785   if ((first_in_to_bb && same_line_p (locus, gimple_location (first_in_to_bb)))
 786       || (last_in_to_bb && same_line_p (locus, gimple_location (last_in_to_bb))))
 787     bb->discriminator = next_discriminator_for_locus (locus);
 788 }
 789
 790 /* Create the edges for a GIMPLE_COND starting at block BB.  */
 791
 792 static void
 793 make_cond_expr_edges (basic_block bb)
 794 {
 795   gimple entry = last_stmt (bb);
 796   gimple then_stmt, else_stmt;
 797   basic_block then_bb, else_bb;
 798   tree then_label, else_label;
 799   edge e;
 800   location_t entry_locus;
 801
 802   gcc_assert (entry);
 803   gcc_assert (gimple_code (entry) == GIMPLE_COND);
 804
 805   entry_locus = gimple_location (entry);
 806
 807   /* Entry basic blocks for each component.  */
 808   then_label = gimple_cond_true_label (entry);
 809   else_label = gimple_cond_false_label (entry);
 810   then_bb = label_to_block (then_label);
 811   else_bb = label_to_block (else_label);
 812   then_stmt = first_stmt (then_bb);
 813   else_stmt = first_stmt (else_bb);
 814
 815   e = make_edge (bb, then_bb, EDGE_TRUE_VALUE);
 816   assign_discriminator (entry_locus, then_bb);
 817   e->goto_locus = gimple_location (then_stmt);
 818   if (e->goto_locus)
 819     e->goto_block = gimple_block (then_stmt);
 820   e = make_edge (bb, else_bb, EDGE_FALSE_VALUE);
 821   if (e)
 822     {
 823       assign_discriminator (entry_locus, else_bb);
 824       e->goto_locus = gimple_location (else_stmt);
 825       if (e->goto_locus)
 826         e->goto_block = gimple_block (else_stmt);
 827     }
 828
 829   /* We do not need the labels anymore.  */
 830   gimple_cond_set_true_label (entry, NULL_TREE);
 831   gimple_cond_set_false_label (entry, NULL_TREE);
 832 }
 833
 834
 835 /* Called for each element in the hash table (P) as we delete the
 836    edge to cases hash table.
 837
 838    Clear all the TREE_CHAINs to prevent problems with copying of
 839    SWITCH_EXPRs and structure sharing rules, then free the hash table
 840    element.  */
 841
 842 static bool
 843 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value,
 844                        void *data ATTRIBUTE_UNUSED)
 845 {
 846   tree t, next;
 847
 848   for (t = (tree) *value; t; t = next)
 849     {
 850       next = CASE_CHAIN (t);
 851       CASE_CHAIN (t) = NULL;
 852     }
 853
 854   *value = NULL;
 855   return true;
 856 }
 857
 858 /* Start recording information mapping edges to case labels.  */
 859
 860 void
 861 start_recording_case_labels (void)
 862 {
 863   gcc_assert (edge_to_cases == NULL);
 864   edge_to_cases = pointer_map_create ();
 865   touched_switch_bbs = BITMAP_ALLOC (NULL);
 866 }
 867
 868 /* Return nonzero if we are recording information for case labels.  */
 869
 870 static bool
 871 recording_case_labels_p (void)
 872 {
 873   return (edge_to_cases != NULL);
 874 }
 875
 876 /* Stop recording information mapping edges to case labels and
 877    remove any information we have recorded.  */
 878 void
 879 end_recording_case_labels (void)
 880 {
 881   bitmap_iterator bi;
 882   unsigned i;
 883   pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL);
 884   pointer_map_destroy (edge_to_cases);
 885   edge_to_cases = NULL;
 886   EXECUTE_IF_SET_IN_BITMAP (touched_switch_bbs, 0, i, bi)
 887     {
 888       basic_block bb = BASIC_BLOCK (i);
 889       if (bb)
 890         {
 891           gimple stmt = last_stmt (bb);
 892           if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
 893             group_case_labels_stmt (stmt);
 894         }
 895     }
 896   BITMAP_FREE (touched_switch_bbs);
 897 }
 898
 899 /* If we are inside a {start,end}_recording_cases block, then return
 900    a chain of CASE_LABEL_EXPRs from T which reference E.
 901
 902    Otherwise return NULL.  */
 903
 904 static tree
 905 get_cases_for_edge (edge e, gimple t)
 906 {
 907   void **slot;
 908   size_t i, n;
 909
 910   /* If we are not recording cases, then we do not have CASE_LABEL_EXPR
 911      chains available.  Return NULL so the caller can detect this case.  */
 912   if (!recording_case_labels_p ())
 913     return NULL;
 914
 915   slot = pointer_map_contains (edge_to_cases, e);
 916   if (slot)
 917     return (tree) *slot;
 918
 919   /* If we did not find E in the hash table, then this must be the first
 920      time we have been queried for information about E & T.  Add all the
 921      elements from T to the hash table then perform the query again.  */
 922
 923   n = gimple_switch_num_labels (t);
 924   for (i = 0; i < n; i++)
 925     {
 926       tree elt = gimple_switch_label (t, i);
 927       tree lab = CASE_LABEL (elt);
 928       basic_block label_bb = label_to_block (lab);
 929       edge this_edge = find_edge (e->src, label_bb);
 930
 931       /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create
 932          a new chain.  */
 933       slot = pointer_map_insert (edge_to_cases, this_edge);
 934       CASE_CHAIN (elt) = (tree) *slot;
 935       *slot = elt;
 936     }
 937
 938   return (tree) *pointer_map_contains (edge_to_cases, e);
 939 }
 940
 941 /* Create the edges for a GIMPLE_SWITCH starting at block BB.  */
 942
 943 static void
 944 make_gimple_switch_edges (basic_block bb)
 945 {
 946   gimple entry = last_stmt (bb);
 947   location_t entry_locus;
 948   size_t i, n;
 949
 950   entry_locus = gimple_location (entry);
 951
 952   n = gimple_switch_num_labels (entry);
 953
 954   for (i = 0; i < n; ++i)
 955     {
 956       tree lab = CASE_LABEL (gimple_switch_label (entry, i));
 957       basic_block label_bb = label_to_block (lab);
 958       make_edge (bb, label_bb, 0);
 959       assign_discriminator (entry_locus, label_bb);
 960     }
 961 }
 962
 963
 964 /* Return the basic block holding label DEST.  */
 965
 966 basic_block
 967 label_to_block_fn (struct function *ifun, tree dest)
 968 {
 969   int uid = LABEL_DECL_UID (dest);
 970
 971   /* We would die hard when faced by an undefined label.  Emit a label to
 972      the very first basic block.  This will hopefully make even the dataflow
 973      and undefined variable warnings quite right.  */
 974   if (seen_error () && uid < 0)
 975     {
 976       gimple_stmt_iterator gsi = gsi_start_bb (BASIC_BLOCK (NUM_FIXED_BLOCKS));
 977       gimple stmt;
 978
 979       stmt = gimple_build_label (dest);
 980       gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 981       uid = LABEL_DECL_UID (dest);
 982     }
 983   if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map)
 984       <= (unsigned int) uid)
 985     return NULL;
 986   return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid);
 987 }
 988
 989 /* Create edges for an abnormal goto statement at block BB.  If FOR_CALL
 990    is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR.  */
 991
 992 void
 993 make_abnormal_goto_edges (basic_block bb, bool for_call)
 994 {
 995   basic_block target_bb;
 996   gimple_stmt_iterator gsi;
 997
 998   FOR_EACH_BB (target_bb)
 999     for (gsi = gsi_start_bb (target_bb); !gsi_end_p (gsi); gsi_next (&gsi))
1000       {
1001         gimple label_stmt = gsi_stmt (gsi);
1002         tree target;
1003
1004         if (gimple_code (label_stmt) != GIMPLE_LABEL)
1005           break;
1006
1007         target = gimple_label_label (label_stmt);
1008
1009         /* Make an edge to every label block that has been marked as a
1010            potential target for a computed goto or a non-local goto.  */
1011         if ((FORCED_LABEL (target) && !for_call)
1012             || (DECL_NONLOCAL (target) && for_call))
1013           {
1014             make_edge (bb, target_bb, EDGE_ABNORMAL);
1015             break;
1016           }
1017       }
1018 }
1019
1020 /* Create edges for a goto statement at block BB.  */
1021
1022 static void
1023 make_goto_expr_edges (basic_block bb)
1024 {
1025   gimple_stmt_iterator last = gsi_last_bb (bb);
1026   gimple goto_t = gsi_stmt (last);
1027
1028   /* A simple GOTO creates normal edges.  */
1029   if (simple_goto_p (goto_t))
1030     {
1031       tree dest = gimple_goto_dest (goto_t);
1032       basic_block label_bb = label_to_block (dest);
1033       edge e = make_edge (bb, label_bb, EDGE_FALLTHRU);
1034       e->goto_locus = gimple_location (goto_t);
1035       assign_discriminator (e->goto_locus, label_bb);
1036       if (e->goto_locus)
1037         e->goto_block = gimple_block (goto_t);
1038       gsi_remove (&last, true);
1039       return;
1040     }
1041
1042   /* A computed GOTO creates abnormal edges.  */
1043   make_abnormal_goto_edges (bb, false);
1044 }
1045
1046 /* Create edges for an asm statement with labels at block BB.  */
1047
1048 static void
1049 make_gimple_asm_edges (basic_block bb)
1050 {
1051   gimple stmt = last_stmt (bb);
1052   location_t stmt_loc = gimple_location (stmt);
1053   int i, n = gimple_asm_nlabels (stmt);
1054
1055   for (i = 0; i < n; ++i)
1056     {
1057       tree label = TREE_VALUE (gimple_asm_label_op (stmt, i));
1058       basic_block label_bb = label_to_block (label);
1059       make_edge (bb, label_bb, 0);
1060       assign_discriminator (stmt_loc, label_bb);
1061     }
1062 }
1063
1064 /*---------------------------------------------------------------------------
1065                                Flowgraph analysis
1066 ---------------------------------------------------------------------------*/
1067
1068 /* Cleanup useless labels in basic blocks.  This is something we wish
1069    to do early because it allows us to group case labels before creating
1070    the edges for the CFG, and it speeds up block statement iterators in
1071    all passes later on.
1072    We rerun this pass after CFG is created, to get rid of the labels that
1073    are no longer referenced.  After then we do not run it any more, since
1074    (almost) no new labels should be created.  */
1075
1076 /* A map from basic block index to the leading label of that block.  */
1077 static struct label_record
1078 {
1079   /* The label.  */
1080   tree label;
1081
1082   /* True if the label is referenced from somewhere.  */
1083   bool used;
1084 } *label_for_bb;
1085
1086 /* Given LABEL return the first label in the same basic block.  */
1087
1088 static tree
1089 main_block_label (tree label)
1090 {
1091   basic_block bb = label_to_block (label);
1092   tree main_label = label_for_bb[bb->index].label;
1093
1094   /* label_to_block possibly inserted undefined label into the chain.  */
1095   if (!main_label)
1096     {
1097       label_for_bb[bb->index].label = label;
1098       main_label = label;
1099     }
1100
1101   label_for_bb[bb->index].used = true;
1102   return main_label;
1103 }
1104
1105 /* Clean up redundant labels within the exception tree.  */
1106
1107 static void
1108 cleanup_dead_labels_eh (void)
1109 {
1110   eh_landing_pad lp;
1111   eh_region r;
1112   tree lab;
1113   int i;
1114
1115   if (cfun->eh == NULL)
1116     return;
1117
1118   for (i = 1; VEC_iterate (eh_landing_pad, cfun->eh->lp_array, i, lp); ++i)
1119     if (lp && lp->post_landing_pad)
1120       {
1121         lab = main_block_label (lp->post_landing_pad);
1122         if (lab != lp->post_landing_pad)
1123           {
1124             EH_LANDING_PAD_NR (lp->post_landing_pad) = 0;
1125             EH_LANDING_PAD_NR (lab) = lp->index;
1126           }
1127       }
1128
1129   FOR_ALL_EH_REGION (r)
1130     switch (r->type)
1131       {
1132       case ERT_CLEANUP:
1133       case ERT_MUST_NOT_THROW:
1134         break;
1135
1136       case ERT_TRY:
1137         {
1138           eh_catch c;
1139           for (c = r->u.eh_try.first_catch; c ; c = c->next_catch)
1140             {
1141               lab = c->label;
1142               if (lab)
1143                 c->label = main_block_label (lab);
1144             }
1145         }
1146         break;
1147
1148       case ERT_ALLOWED_EXCEPTIONS:
1149         lab = r->u.allowed.label;
1150         if (lab)
1151           r->u.allowed.label = main_block_label (lab);
1152         break;
1153       }
1154 }
1155
1156
1157 /* Cleanup redundant labels.  This is a three-step process:
1158      1) Find the leading label for each block.
1159      2) Redirect all references to labels to the leading labels.
1160      3) Cleanup all useless labels.  */
1161
1162 void
1163 cleanup_dead_labels (void)
1164 {
1165   basic_block bb;
1166   label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
1167
1168   /* Find a suitable label for each block.  We use the first user-defined
1169      label if there is one, or otherwise just the first label we see.  */
1170   FOR_EACH_BB (bb)
1171     {
1172       gimple_stmt_iterator i;
1173
1174       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
1175         {
1176           tree label;
1177           gimple stmt = gsi_stmt (i);
1178
1179           if (gimple_code (stmt) != GIMPLE_LABEL)
1180             break;
1181
1182           label = gimple_label_label (stmt);
1183
1184           /* If we have not yet seen a label for the current block,
1185              remember this one and see if there are more labels.  */
1186           if (!label_for_bb[bb->index].label)
1187             {
1188               label_for_bb[bb->index].label = label;
1189               continue;
1190             }
1191
1192           /* If we did see a label for the current block already, but it
1193              is an artificially created label, replace it if the current
1194              label is a user defined label.  */
1195           if (!DECL_ARTIFICIAL (label)
1196               && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
1197             {
1198               label_for_bb[bb->index].label = label;
1199               break;
1200             }
1201         }
1202     }
1203
1204   /* Now redirect all jumps/branches to the selected label.
1205      First do so for each block ending in a control statement.  */
1206   FOR_EACH_BB (bb)
1207     {
1208       gimple stmt = last_stmt (bb);
1209       tree label, new_label;
1210
1211       if (!stmt)
1212         continue;
1213
1214       switch (gimple_code (stmt))
1215         {
1216         case GIMPLE_COND:
1217           label = gimple_cond_true_label (stmt);
1218           if (label)
1219             {
1220               new_label = main_block_label (label);
1221               if (new_label != label)
1222                 gimple_cond_set_true_label (stmt, new_label);
1223             }
1224
1225           label = gimple_cond_false_label (stmt);
1226           if (label)
1227             {
1228               new_label = main_block_label (label);
1229               if (new_label != label)
1230                 gimple_cond_set_false_label (stmt, new_label);
1231             }
1232           break;
1233
1234         case GIMPLE_SWITCH:
1235           {
1236             size_t i, n = gimple_switch_num_labels (stmt);
1237
1238             /* Replace all destination labels.  */
1239             for (i = 0; i < n; ++i)
1240               {
1241                 tree case_label = gimple_switch_label (stmt, i);
1242                 label = CASE_LABEL (case_label);
1243                 new_label = main_block_label (label);
1244                 if (new_label != label)
1245                   CASE_LABEL (case_label) = new_label;
1246               }
1247             break;
1248           }
1249
1250         case GIMPLE_ASM:
1251           {
1252             int i, n = gimple_asm_nlabels (stmt);
1253
1254             for (i = 0; i < n; ++i)
1255               {
1256                 tree cons = gimple_asm_label_op (stmt, i);
1257                 tree label = main_block_label (TREE_VALUE (cons));
1258                 TREE_VALUE (cons) = label;
1259               }
1260             break;
1261           }
1262
1263         /* We have to handle gotos until they're removed, and we don't
1264            remove them until after we've created the CFG edges.  */
1265         case GIMPLE_GOTO:
1266           if (!computed_goto_p (stmt))
1267             {
1268               label = gimple_goto_dest (stmt);
1269               new_label = main_block_label (label);
1270               if (new_label != label)
1271                 gimple_goto_set_dest (stmt, new_label);
1272             }
1273           break;
1274
1275         case GIMPLE_TRANSACTION:
1276           {
1277             tree label = gimple_transaction_label (stmt);
1278             if (label)
1279               {
1280                 tree new_label = main_block_label (label);
1281                 if (new_label != label)
1282                   gimple_transaction_set_label (stmt, new_label);
1283               }
1284           }
1285           break;
1286
1287         default:
1288           break;
1289       }
1290     }
1291
1292   /* Do the same for the exception region tree labels.  */
1293   cleanup_dead_labels_eh ();
1294
1295   /* Finally, purge dead labels.  All user-defined labels and labels that
1296      can be the target of non-local gotos and labels which have their
1297      address taken are preserved.  */
1298   FOR_EACH_BB (bb)
1299     {
1300       gimple_stmt_iterator i;
1301       tree label_for_this_bb = label_for_bb[bb->index].label;
1302
1303       if (!label_for_this_bb)
1304         continue;
1305
1306       /* If the main label of the block is unused, we may still remove it.  */
1307       if (!label_for_bb[bb->index].used)
1308         label_for_this_bb = NULL;
1309
1310       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
1311         {
1312           tree label;
1313           gimple stmt = gsi_stmt (i);
1314
1315           if (gimple_code (stmt) != GIMPLE_LABEL)
1316             break;
1317
1318           label = gimple_label_label (stmt);
1319
1320           if (label == label_for_this_bb
1321               || !DECL_ARTIFICIAL (label)
1322               || DECL_NONLOCAL (label)
1323               || FORCED_LABEL (label))
1324             gsi_next (&i);
1325           else
1326             gsi_remove (&i, true);
1327         }
1328     }
1329
1330   free (label_for_bb);
1331 }
1332
1333 /* Scan the sorted vector of cases in STMT (a GIMPLE_SWITCH) and combine
1334    the ones jumping to the same label.
1335    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
1336
1337 static void
1338 group_case_labels_stmt (gimple stmt)
1339 {
1340   int old_size = gimple_switch_num_labels (stmt);
1341   int i, j, new_size = old_size;
1342   tree default_case = NULL_TREE;
1343   tree default_label = NULL_TREE;
1344   bool has_default;
1345
1346   /* The default label is always the first case in a switch
1347      statement after gimplification if it was not optimized
1348      away */
1349   if (!CASE_LOW (gimple_switch_default_label (stmt))
1350       && !CASE_HIGH (gimple_switch_default_label (stmt)))
1351     {
1352       default_case = gimple_switch_default_label (stmt);
1353       default_label = CASE_LABEL (default_case);
1354       has_default = true;
1355     }
1356   else
1357     has_default = false;
1358
1359   /* Look for possible opportunities to merge cases.  */
1360   if (has_default)
1361     i = 1;
1362   else
1363     i = 0;
1364   while (i < old_size)
1365     {
1366       tree base_case, base_label, base_high;
1367       base_case = gimple_switch_label (stmt, i);
1368
1369       gcc_assert (base_case);
1370       base_label = CASE_LABEL (base_case);
1371
1372       /* Discard cases that have the same destination as the
1373          default case.  */
1374       if (base_label == default_label)
1375         {
1376           gimple_switch_set_label (stmt, i, NULL_TREE);
1377           i++;
1378           new_size--;
1379           continue;
1380         }
1381
1382       base_high = CASE_HIGH (base_case)
1383           ? CASE_HIGH (base_case)
1384           : CASE_LOW (base_case);
1385       i++;
1386
1387       /* Try to merge case labels.  Break out when we reach the end
1388          of the label vector or when we cannot merge the next case
1389          label with the current one.  */
1390       while (i < old_size)
1391         {
1392           tree merge_case = gimple_switch_label (stmt, i);
1393           tree merge_label = CASE_LABEL (merge_case);
1394           double_int bhp1 = double_int_add (tree_to_double_int (base_high),
1395                                             double_int_one);
1396
1397           /* Merge the cases if they jump to the same place,
1398              and their ranges are consecutive.  */
1399           if (merge_label == base_label
1400               && double_int_equal_p (tree_to_double_int (CASE_LOW (merge_case)),
1401                                      bhp1))
1402             {
1403               base_high = CASE_HIGH (merge_case) ?
1404                   CASE_HIGH (merge_case) : CASE_LOW (merge_case);
1405               CASE_HIGH (base_case) = base_high;
1406               gimple_switch_set_label (stmt, i, NULL_TREE);
1407               new_size--;
1408               i++;
1409             }
1410           else
1411             break;
1412         }
1413     }
1414
1415   /* Compress the case labels in the label vector, and adjust the
1416      length of the vector.  */
1417   for (i = 0, j = 0; i < new_size; i++)
1418     {
1419       while (! gimple_switch_label (stmt, j))
1420         j++;
1421       gimple_switch_set_label (stmt, i,
1422                                gimple_switch_label (stmt, j++));
1423     }
1424
1425   gcc_assert (new_size <= old_size);
1426   gimple_switch_set_num_labels (stmt, new_size);
1427 }
1428
1429 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
1430    and scan the sorted vector of cases.  Combine the ones jumping to the
1431    same label.  */
1432
1433 void
1434 group_case_labels (void)
1435 {
1436   basic_block bb;
1437
1438   FOR_EACH_BB (bb)
1439     {
1440       gimple stmt = last_stmt (bb);
1441       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
1442         group_case_labels_stmt (stmt);
1443     }
1444 }
1445
1446 /* Checks whether we can merge block B into block A.  */
1447
1448 static bool
1449 gimple_can_merge_blocks_p (basic_block a, basic_block b)
1450 {
1451   gimple stmt;
1452   gimple_stmt_iterator gsi;
1453   gimple_seq phis;
1454
1455   if (!single_succ_p (a))
1456     return false;
1457
1458   if (single_succ_edge (a)->flags & (EDGE_ABNORMAL | EDGE_EH | EDGE_PRESERVE))
1459     return false;
1460
1461   if (single_succ (a) != b)
1462     return false;
1463
1464   if (!single_pred_p (b))
1465     return false;
1466
1467   if (b == EXIT_BLOCK_PTR)
1468     return false;
1469
1470   /* If A ends by a statement causing exceptions or something similar, we
1471      cannot merge the blocks.  */
1472   stmt = last_stmt (a);
1473   if (stmt && stmt_ends_bb_p (stmt))
1474     return false;
1475
1476   /* Do not allow a block with only a non-local label to be merged.  */
1477   if (stmt
1478       && gimple_code (stmt) == GIMPLE_LABEL
1479       && DECL_NONLOCAL (gimple_label_label (stmt)))
1480     return false;
1481
1482   /* Examine the labels at the beginning of B.  */
1483   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
1484     {
1485       tree lab;
1486       stmt = gsi_stmt (gsi);
1487       if (gimple_code (stmt) != GIMPLE_LABEL)
1488         break;
1489       lab = gimple_label_label (stmt);
1490
1491       /* Do not remove user forced labels or for -O0 any user labels.  */
1492       if (!DECL_ARTIFICIAL (lab) && (!optimize || FORCED_LABEL (lab)))
1493         return false;
1494     }
1495
1496   /* Protect the loop latches.  */
1497   if (current_loops && b->loop_father->latch == b)
1498     return false;
1499
1500   /* It must be possible to eliminate all phi nodes in B.  If ssa form
1501      is not up-to-date and a name-mapping is registered, we cannot eliminate
1502      any phis.  Symbols marked for renaming are never a problem though.  */
1503   phis = phi_nodes (b);
1504   if (!gimple_seq_empty_p (phis)
1505       && name_mappings_registered_p ())
1506     return false;
1507
1508   /* When not optimizing, don't merge if we'd lose goto_locus.  */
1509   if (!optimize
1510       && single_succ_edge (a)->goto_locus != UNKNOWN_LOCATION)
1511     {
1512       location_t goto_locus = single_succ_edge (a)->goto_locus;
1513       gimple_stmt_iterator prev, next;
1514       prev = gsi_last_nondebug_bb (a);
1515       next = gsi_after_labels (b);
1516       if (!gsi_end_p (next) && is_gimple_debug (gsi_stmt (next)))
1517         gsi_next_nondebug (&next);
1518       if ((gsi_end_p (prev)
1519            || gimple_location (gsi_stmt (prev)) != goto_locus)
1520           && (gsi_end_p (next)
1521               || gimple_location (gsi_stmt (next)) != goto_locus))
1522         return false;
1523     }
1524
1525   return true;
1526 }
1527
1528 /* Return true if the var whose chain of uses starts at PTR has no
1529    nondebug uses.  */
1530 bool
1531 has_zero_uses_1 (const ssa_use_operand_t *head)
1532 {
1533   const ssa_use_operand_t *ptr;
1534
1535   for (ptr = head->next; ptr != head; ptr = ptr->next)
1536     if (!is_gimple_debug (USE_STMT (ptr)))
1537       return false;
1538
1539   return true;
1540 }
1541
1542 /* Return true if the var whose chain of uses starts at PTR has a
1543    single nondebug use.  Set USE_P and STMT to that single nondebug
1544    use, if so, or to NULL otherwise.  */
1545 bool
1546 single_imm_use_1 (const ssa_use_operand_t *head,
1547                   use_operand_p *use_p, gimple *stmt)
1548 {
1549   ssa_use_operand_t *ptr, *single_use = 0;
1550
1551   for (ptr = head->next; ptr != head; ptr = ptr->next)
1552     if (!is_gimple_debug (USE_STMT (ptr)))
1553       {
1554         if (single_use)
1555           {
1556             single_use = NULL;
1557             break;
1558           }
1559         single_use = ptr;
1560       }
1561
1562   if (use_p)
1563     *use_p = single_use;
1564
1565   if (stmt)
1566     *stmt = single_use ? single_use->loc.stmt : NULL;
1567
1568   return !!single_use;
1569 }
1570
1571 /* Replaces all uses of NAME by VAL.  */
1572
1573 void
1574 replace_uses_by (tree name, tree val)
1575 {
1576   imm_use_iterator imm_iter;
1577   use_operand_p use;
1578   gimple stmt;
1579   edge e;
1580
1581   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name)
1582     {
1583       FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
1584         {
1585           replace_exp (use, val);
1586
1587           if (gimple_code (stmt) == GIMPLE_PHI)
1588             {
1589               e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use));
1590               if (e->flags & EDGE_ABNORMAL)
1591                 {
1592                   /* This can only occur for virtual operands, since
1593                      for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1594                      would prevent replacement.  */
1595                   gcc_checking_assert (!is_gimple_reg (name));
1596                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
1597                 }
1598             }
1599         }
1600
1601       if (gimple_code (stmt) != GIMPLE_PHI)
1602         {
1603           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1604           gimple orig_stmt = stmt;
1605           size_t i;
1606
1607           /* Mark the block if we changed the last stmt in it.  */
1608           if (cfgcleanup_altered_bbs
1609               && stmt_ends_bb_p (stmt))
1610             bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index);
1611
1612           /* FIXME.  It shouldn't be required to keep TREE_CONSTANT
1613              on ADDR_EXPRs up-to-date on GIMPLE.  Propagation will
1614              only change sth from non-invariant to invariant, and only
1615              when propagating constants.  */
1616           if (is_gimple_min_invariant (val))
1617             for (i = 0; i < gimple_num_ops (stmt); i++)
1618               {
1619                 tree op = gimple_op (stmt, i);
1620                 /* Operands may be empty here.  For example, the labels
1621                    of a GIMPLE_COND are nulled out following the creation
1622                    of the corresponding CFG edges.  */
1623                 if (op && TREE_CODE (op) == ADDR_EXPR)
1624                   recompute_tree_invariant_for_addr_expr (op);
1625               }
1626
1627           if (fold_stmt (&gsi))
1628             stmt = gsi_stmt (gsi);
1629
1630           if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
1631             gimple_purge_dead_eh_edges (gimple_bb (stmt));
1632
1633           update_stmt (stmt);
1634         }
1635     }
1636
1637   gcc_checking_assert (has_zero_uses (name));
1638
1639   /* Also update the trees stored in loop structures.  */
1640   if (current_loops)
1641     {
1642       struct loop *loop;
1643       loop_iterator li;
1644
1645       FOR_EACH_LOOP (li, loop, 0)
1646         {
1647           substitute_in_loop_info (loop, name, val);
1648         }
1649     }
1650 }
1651
1652 /* Merge block B into block A.  */
1653
1654 static void
1655 gimple_merge_blocks (basic_block a, basic_block b)
1656 {
1657   gimple_stmt_iterator last, gsi, psi;
1658   gimple_seq phis = phi_nodes (b);
1659
1660   if (dump_file)
1661     fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
1662
1663   /* Remove all single-valued PHI nodes from block B of the form
1664      V_i = PHI <V_j> by propagating V_j to all the uses of V_i.  */
1665   gsi = gsi_last_bb (a);
1666   for (psi = gsi_start (phis); !gsi_end_p (psi); )
1667     {
1668       gimple phi = gsi_stmt (psi);
1669       tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
1670       gimple copy;
1671       bool may_replace_uses = !is_gimple_reg (def)
1672                               || may_propagate_copy (def, use);
1673
1674       /* In case we maintain loop closed ssa form, do not propagate arguments
1675          of loop exit phi nodes.  */
1676       if (current_loops
1677           && loops_state_satisfies_p (LOOP_CLOSED_SSA)
1678           && is_gimple_reg (def)
1679           && TREE_CODE (use) == SSA_NAME
1680           && a->loop_father != b->loop_father)
1681         may_replace_uses = false;
1682
1683       if (!may_replace_uses)
1684         {
1685           gcc_assert (is_gimple_reg (def));
1686
1687           /* Note that just emitting the copies is fine -- there is no problem
1688              with ordering of phi nodes.  This is because A is the single
1689              predecessor of B, therefore results of the phi nodes cannot
1690              appear as arguments of the phi nodes.  */
1691           copy = gimple_build_assign (def, use);
1692           gsi_insert_after (&gsi, copy, GSI_NEW_STMT);
1693           remove_phi_node (&psi, false);
1694         }
1695       else
1696         {
1697           /* If we deal with a PHI for virtual operands, we can simply
1698              propagate these without fussing with folding or updating
1699              the stmt.  */
1700           if (!is_gimple_reg (def))
1701             {
1702               imm_use_iterator iter;
1703               use_operand_p use_p;
1704               gimple stmt;
1705
1706               FOR_EACH_IMM_USE_STMT (stmt, iter, def)
1707                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
1708                   SET_USE (use_p, use);
1709
1710               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
1711                 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use) = 1;
1712             }
1713           else
1714             replace_uses_by (def, use);
1715
1716           remove_phi_node (&psi, true);
1717         }
1718     }
1719
1720   /* Ensure that B follows A.  */
1721   move_block_after (b, a);
1722
1723   gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU);
1724   gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
1725
1726   /* Remove labels from B and set gimple_bb to A for other statements.  */
1727   for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);)
1728     {
1729       gimple stmt = gsi_stmt (gsi);
1730       if (gimple_code (stmt) == GIMPLE_LABEL)
1731         {
1732           tree label = gimple_label_label (stmt);
1733           int lp_nr;
1734
1735           gsi_remove (&gsi, false);
1736
1737           /* Now that we can thread computed gotos, we might have
1738              a situation where we have a forced label in block B
1739              However, the label at the start of block B might still be
1740              used in other ways (think about the runtime checking for
1741              Fortran assigned gotos).  So we can not just delete the
1742              label.  Instead we move the label to the start of block A.  */
1743           if (FORCED_LABEL (label))
1744             {
1745               gimple_stmt_iterator dest_gsi = gsi_start_bb (a);
1746               gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT);
1747             }
1748           /* Other user labels keep around in a form of a debug stmt.  */
1749           else if (!DECL_ARTIFICIAL (label) && MAY_HAVE_DEBUG_STMTS)
1750             {
1751               gimple dbg = gimple_build_debug_bind (label,
1752                                                     integer_zero_node,
1753                                                     stmt);
1754               gimple_debug_bind_reset_value (dbg);
1755               gsi_insert_before (&gsi, dbg, GSI_SAME_STMT);
1756             }
1757
1758           lp_nr = EH_LANDING_PAD_NR (label);
1759           if (lp_nr)
1760             {
1761               eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr);
1762               lp->post_landing_pad = NULL;
1763             }
1764         }
1765       else
1766         {
1767           gimple_set_bb (stmt, a);
1768           gsi_next (&gsi);
1769         }
1770     }
1771
1772   /* Merge the sequences.  */
1773   last = gsi_last_bb (a);
1774   gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT);
1775   set_bb_seq (b, NULL);
1776
1777   if (cfgcleanup_altered_bbs)
1778     bitmap_set_bit (cfgcleanup_altered_bbs, a->index);
1779 }
1780
1781
1782 /* Return the one of two successors of BB that is not reachable by a
1783    complex edge, if there is one.  Else, return BB.  We use
1784    this in optimizations that use post-dominators for their heuristics,
1785    to catch the cases in C++ where function calls are involved.  */
1786
1787 basic_block
1788 single_noncomplex_succ (basic_block bb)
1789 {
1790   edge e0, e1;
1791   if (EDGE_COUNT (bb->succs) != 2)
1792     return bb;
1793
1794   e0 = EDGE_SUCC (bb, 0);
1795   e1 = EDGE_SUCC (bb, 1);
1796   if (e0->flags & EDGE_COMPLEX)
1797     return e1->dest;
1798   if (e1->flags & EDGE_COMPLEX)
1799     return e0->dest;
1800
1801   return bb;
1802 }
1803
1804 /* T is CALL_EXPR.  Set current_function_calls_* flags.  */
1805
1806 void
1807 notice_special_calls (gimple call)
1808 {
1809   int flags = gimple_call_flags (call);
1810
1811   if (flags & ECF_MAY_BE_ALLOCA)
1812     cfun->calls_alloca = true;
1813   if (flags & ECF_RETURNS_TWICE)
1814     cfun->calls_setjmp = true;
1815 }
1816
1817
1818 /* Clear flags set by notice_special_calls.  Used by dead code removal
1819    to update the flags.  */
1820
1821 void
1822 clear_special_calls (void)
1823 {
1824   cfun->calls_alloca = false;
1825   cfun->calls_setjmp = false;
1826 }
1827
1828 /* Remove PHI nodes associated with basic block BB and all edges out of BB.  */
1829
1830 static void
1831 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb)
1832 {
1833   /* Since this block is no longer reachable, we can just delete all
1834      of its PHI nodes.  */
1835   remove_phi_nodes (bb);
1836
1837   /* Remove edges to BB's successors.  */
1838   while (EDGE_COUNT (bb->succs) > 0)
1839     remove_edge (EDGE_SUCC (bb, 0));
1840 }
1841
1842
1843 /* Remove statements of basic block BB.  */
1844
1845 static void
1846 remove_bb (basic_block bb)
1847 {
1848   gimple_stmt_iterator i;
1849
1850   if (dump_file)
1851     {
1852       fprintf (dump_file, "Removing basic block %d\n", bb->index);
1853       if (dump_flags & TDF_DETAILS)
1854         {
1855           dump_bb (bb, dump_file, 0);
1856           fprintf (dump_file, "\n");
1857         }
1858     }
1859
1860   if (current_loops)
1861     {
1862       struct loop *loop = bb->loop_father;
1863
1864       /* If a loop gets removed, clean up the information associated
1865          with it.  */
1866       if (loop->latch == bb
1867           || loop->header == bb)
1868         free_numbers_of_iterations_estimates_loop (loop);
1869     }
1870
1871   /* Remove all the instructions in the block.  */
1872   if (bb_seq (bb) != NULL)
1873     {
1874       /* Walk backwards so as to get a chance to substitute all
1875          released DEFs into debug stmts.  See
1876          eliminate_unnecessary_stmts() in tree-ssa-dce.c for more
1877          details.  */
1878       for (i = gsi_last_bb (bb); !gsi_end_p (i);)
1879         {
1880           gimple stmt = gsi_stmt (i);
1881           if (gimple_code (stmt) == GIMPLE_LABEL
1882               && (FORCED_LABEL (gimple_label_label (stmt))
1883                   || DECL_NONLOCAL (gimple_label_label (stmt))))
1884             {
1885               basic_block new_bb;
1886               gimple_stmt_iterator new_gsi;
1887
1888               /* A non-reachable non-local label may still be referenced.
1889                  But it no longer needs to carry the extra semantics of
1890                  non-locality.  */
1891               if (DECL_NONLOCAL (gimple_label_label (stmt)))
1892                 {
1893                   DECL_NONLOCAL (gimple_label_label (stmt)) = 0;
1894                   FORCED_LABEL (gimple_label_label (stmt)) = 1;
1895                 }
1896
1897               new_bb = bb->prev_bb;
1898               new_gsi = gsi_start_bb (new_bb);
1899               gsi_remove (&i, false);
1900               gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT);
1901             }
1902           else
1903             {
1904               /* Release SSA definitions if we are in SSA.  Note that we
1905                  may be called when not in SSA.  For example,
1906                  final_cleanup calls this function via
1907                  cleanup_tree_cfg.  */
1908               if (gimple_in_ssa_p (cfun))
1909                 release_defs (stmt);
1910
1911               gsi_remove (&i, true);
1912             }
1913
1914           if (gsi_end_p (i))
1915             i = gsi_last_bb (bb);
1916           else
1917             gsi_prev (&i);
1918         }
1919     }
1920
1921   remove_phi_nodes_and_edges_for_unreachable_block (bb);
1922   bb->il.gimple = NULL;
1923 }
1924
1925
1926 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a
1927    predicate VAL, return the edge that will be taken out of the block.
1928    If VAL does not match a unique edge, NULL is returned.  */
1929
1930 edge
1931 find_taken_edge (basic_block bb, tree val)
1932 {
1933   gimple stmt;
1934
1935   stmt = last_stmt (bb);
1936
1937   gcc_assert (stmt);
1938   gcc_assert (is_ctrl_stmt (stmt));
1939
1940   if (val == NULL)
1941     return NULL;
1942
1943   if (!is_gimple_min_invariant (val))
1944     return NULL;
1945
1946   if (gimple_code (stmt) == GIMPLE_COND)
1947     return find_taken_edge_cond_expr (bb, val);
1948
1949   if (gimple_code (stmt) == GIMPLE_SWITCH)
1950     return find_taken_edge_switch_expr (bb, val);
1951
1952   if (computed_goto_p (stmt))
1953     {
1954       /* Only optimize if the argument is a label, if the argument is
1955          not a label then we can not construct a proper CFG.
1956
1957          It may be the case that we only need to allow the LABEL_REF to
1958          appear inside an ADDR_EXPR, but we also allow the LABEL_REF to
1959          appear inside a LABEL_EXPR just to be safe.  */
1960       if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR)
1961           && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL)
1962         return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0));
1963       return NULL;
1964     }
1965
1966   gcc_unreachable ();
1967 }
1968
1969 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR
1970    statement, determine which of the outgoing edges will be taken out of the
1971    block.  Return NULL if either edge may be taken.  */
1972
1973 static edge
1974 find_taken_edge_computed_goto (basic_block bb, tree val)
1975 {
1976   basic_block dest;
1977   edge e = NULL;
1978
1979   dest = label_to_block (val);
1980   if (dest)
1981     {
1982       e = find_edge (bb, dest);
1983       gcc_assert (e != NULL);
1984     }
1985
1986   return e;
1987 }
1988
1989 /* Given a constant value VAL and the entry block BB to a COND_EXPR
1990    statement, determine which of the two edges will be taken out of the
1991    block.  Return NULL if either edge may be taken.  */
1992
1993 static edge
1994 find_taken_edge_cond_expr (basic_block bb, tree val)
1995 {
1996   edge true_edge, false_edge;
1997
1998   extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1999
2000   gcc_assert (TREE_CODE (val) == INTEGER_CST);
2001   return (integer_zerop (val) ? false_edge : true_edge);
2002 }
2003
2004 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR
2005    statement, determine which edge will be taken out of the block.  Return
2006    NULL if any edge may be taken.  */
2007
2008 static edge
2009 find_taken_edge_switch_expr (basic_block bb, tree val)
2010 {
2011   basic_block dest_bb;
2012   edge e;
2013   gimple switch_stmt;
2014   tree taken_case;
2015
2016   switch_stmt = last_stmt (bb);
2017   taken_case = find_case_label_for_value (switch_stmt, val);
2018   dest_bb = label_to_block (CASE_LABEL (taken_case));
2019
2020   e = find_edge (bb, dest_bb);
2021   gcc_assert (e);
2022   return e;
2023 }
2024
2025
2026 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL.
2027    We can make optimal use here of the fact that the case labels are
2028    sorted: We can do a binary search for a case matching VAL.  */
2029
2030 static tree
2031 find_case_label_for_value (gimple switch_stmt, tree val)
2032 {
2033   size_t low, high, n = gimple_switch_num_labels (switch_stmt);
2034   tree default_case = gimple_switch_default_label (switch_stmt);
2035
2036   for (low = 0, high = n; high - low > 1; )
2037     {
2038       size_t i = (high + low) / 2;
2039       tree t = gimple_switch_label (switch_stmt, i);
2040       int cmp;
2041
2042       /* Cache the result of comparing CASE_LOW and val.  */
2043       cmp = tree_int_cst_compare (CASE_LOW (t), val);
2044
2045       if (cmp > 0)
2046         high = i;
2047       else
2048         low = i;
2049
2050       if (CASE_HIGH (t) == NULL)
2051         {
2052           /* A singe-valued case label.  */
2053           if (cmp == 0)
2054             return t;
2055         }
2056       else
2057         {
2058           /* A case range.  We can only handle integer ranges.  */
2059           if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
2060             return t;
2061         }
2062     }
2063
2064   return default_case;
2065 }
2066
2067
2068 /* Dump a basic block on stderr.  */
2069
2070 void
2071 gimple_debug_bb (basic_block bb)
2072 {
2073   gimple_dump_bb (bb, stderr, 0, TDF_VOPS|TDF_MEMSYMS);
2074 }
2075
2076
2077 /* Dump basic block with index N on stderr.  */
2078
2079 basic_block
2080 gimple_debug_bb_n (int n)
2081 {
2082   gimple_debug_bb (BASIC_BLOCK (n));
2083   return BASIC_BLOCK (n);
2084 }
2085
2086
2087 /* Dump the CFG on stderr.
2088
2089    FLAGS are the same used by the tree dumping functions
2090    (see TDF_* in tree-pass.h).  */
2091
2092 void
2093 gimple_debug_cfg (int flags)
2094 {
2095   gimple_dump_cfg (stderr, flags);
2096 }
2097
2098
2099 /* Dump the program showing basic block boundaries on the given FILE.
2100
2101    FLAGS are the same used by the tree dumping functions (see TDF_* in
2102    tree.h).  */
2103
2104 void
2105 gimple_dump_cfg (FILE *file, int flags)
2106 {
2107   if (flags & TDF_DETAILS)
2108     {
2109       dump_function_header (file, current_function_decl, flags);
2110       fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n",
2111                n_basic_blocks, n_edges, last_basic_block);
2112
2113       brief_dump_cfg (file);
2114       fprintf (file, "\n");
2115     }
2116
2117   if (flags & TDF_STATS)
2118     dump_cfg_stats (file);
2119
2120   dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS);
2121 }
2122
2123
2124 /* Dump CFG statistics on FILE.  */
2125
2126 void
2127 dump_cfg_stats (FILE *file)
2128 {
2129   static long max_num_merged_labels = 0;
2130   unsigned long size, total = 0;
2131   long num_edges;
2132   basic_block bb;
2133   const char * const fmt_str   = "%-30s%-13s%12s\n";
2134   const char * const fmt_str_1 = "%-30s%13d%11lu%c\n";
2135   const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n";
2136   const char * const fmt_str_3 = "%-43s%11lu%c\n";
2137   const char *funcname
2138     = lang_hooks.decl_printable_name (current_function_decl, 2);
2139
2140
2141   fprintf (file, "\nCFG Statistics for %s\n\n", funcname);
2142
2143   fprintf (file, "---------------------------------------------------------\n");
2144   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
2145   fprintf (file, fmt_str, "", "  instances  ", "used ");
2146   fprintf (file, "---------------------------------------------------------\n");
2147
2148   size = n_basic_blocks * sizeof (struct basic_block_def);
2149   total += size;
2150   fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks,
2151            SCALE (size), LABEL (size));
2152
2153   num_edges = 0;
2154   FOR_EACH_BB (bb)
2155     num_edges += EDGE_COUNT (bb->succs);
2156   size = num_edges * sizeof (struct edge_def);
2157   total += size;
2158   fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size));
2159
2160   fprintf (file, "---------------------------------------------------------\n");
2161   fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total),
2162            LABEL (total));
2163   fprintf (file, "---------------------------------------------------------\n");
2164   fprintf (file, "\n");
2165
2166   if (cfg_stats.num_merged_labels > max_num_merged_labels)
2167     max_num_merged_labels = cfg_stats.num_merged_labels;
2168
2169   fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n",
2170            cfg_stats.num_merged_labels, max_num_merged_labels);
2171
2172   fprintf (file, "\n");
2173 }
2174
2175
2176 /* Dump CFG statistics on stderr.  Keep extern so that it's always
2177    linked in the final executable.  */
2178
2179 DEBUG_FUNCTION void
2180 debug_cfg_stats (void)
2181 {
2182   dump_cfg_stats (stderr);
2183 }
2184
2185
2186 /* Dump the flowgraph to a .vcg FILE.  */
2187
2188 static void
2189 gimple_cfg2vcg (FILE *file)
2190 {
2191   edge e;
2192   edge_iterator ei;
2193   basic_block bb;
2194   const char *funcname
2195     = lang_hooks.decl_printable_name (current_function_decl, 2);
2196
2197   /* Write the file header.  */
2198   fprintf (file, "graph: { title: \"%s\"\n", funcname);
2199   fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n");
2200   fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n");
2201
2202   /* Write blocks and edges.  */
2203   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2204     {
2205       fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"",
2206                e->dest->index);
2207
2208       if (e->flags & EDGE_FAKE)
2209         fprintf (file, " linestyle: dotted priority: 10");
2210       else
2211         fprintf (file, " linestyle: solid priority: 100");
2212
2213       fprintf (file, " }\n");
2214     }
2215   fputc ('\n', file);
2216
2217   FOR_EACH_BB (bb)
2218     {
2219       enum gimple_code head_code, end_code;
2220       const char *head_name, *end_name;
2221       int head_line = 0;
2222       int end_line = 0;
2223       gimple first = first_stmt (bb);
2224       gimple last = last_stmt (bb);
2225
2226       if (first)
2227         {
2228           head_code = gimple_code (first);
2229           head_name = gimple_code_name[head_code];
2230           head_line = get_lineno (first);
2231         }
2232       else
2233         head_name = "no-statement";
2234
2235       if (last)
2236         {
2237           end_code = gimple_code (last);
2238           end_name = gimple_code_name[end_code];
2239           end_line = get_lineno (last);
2240         }
2241       else
2242         end_name = "no-statement";
2243
2244       fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n",
2245                bb->index, bb->index, head_name, head_line, end_name,
2246                end_line);
2247
2248       FOR_EACH_EDGE (e, ei, bb->succs)
2249         {
2250           if (e->dest == EXIT_BLOCK_PTR)
2251             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index);
2252           else
2253             fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index);
2254
2255           if (e->flags & EDGE_FAKE)
2256             fprintf (file, " priority: 10 linestyle: dotted");
2257           else
2258             fprintf (file, " priority: 100 linestyle: solid");
2259
2260           fprintf (file, " }\n");
2261         }
2262
2263       if (bb->next_bb != EXIT_BLOCK_PTR)
2264         fputc ('\n', file);
2265     }
2266
2267   fputs ("}\n\n", file);
2268 }
2269
2270
2271
2272 /*---------------------------------------------------------------------------
2273                              Miscellaneous helpers
2274 ---------------------------------------------------------------------------*/
2275
2276 /* Return true if T, a GIMPLE_CALL, can make an abnormal transfer of control
2277    flow.  Transfers of control flow associated with EH are excluded.  */
2278
2279 static bool
2280 call_can_make_abnormal_goto (gimple t)
2281 {
2282   /* If the function has no non-local labels, then a call cannot make an
2283      abnormal transfer of control.  */
2284   if (!cfun->has_nonlocal_label)
2285    return false;
2286
2287   /* Likewise if the call has no side effects.  */
2288   if (!gimple_has_side_effects (t))
2289     return false;
2290
2291   /* Likewise if the called function is leaf.  */
2292   if (gimple_call_flags (t) & ECF_LEAF)
2293     return false;
2294
2295   return true;
2296 }
2297
2298
2299 /* Return true if T can make an abnormal transfer of control flow.
2300    Transfers of control flow associated with EH are excluded.  */
2301
2302 bool
2303 stmt_can_make_abnormal_goto (gimple t)
2304 {
2305   if (computed_goto_p (t))
2306     return true;
2307   if (is_gimple_call (t))
2308     return call_can_make_abnormal_goto (t);
2309   return false;
2310 }
2311
2312
2313 /* Return true if T represents a stmt that always transfers control.  */
2314
2315 bool
2316 is_ctrl_stmt (gimple t)
2317 {
2318   switch (gimple_code (t))
2319     {
2320     case GIMPLE_COND:
2321     case GIMPLE_SWITCH:
2322     case GIMPLE_GOTO:
2323     case GIMPLE_RETURN:
2324     case GIMPLE_RESX:
2325       return true;
2326     default:
2327       return false;
2328     }
2329 }
2330
2331
2332 /* Return true if T is a statement that may alter the flow of control
2333    (e.g., a call to a non-returning function).  */
2334
2335 bool
2336 is_ctrl_altering_stmt (gimple t)
2337 {
2338   gcc_assert (t);
2339
2340   switch (gimple_code (t))
2341     {
2342     case GIMPLE_CALL:
2343       {
2344         int flags = gimple_call_flags (t);
2345
2346         /* A call alters control flow if it can make an abnormal goto.  */
2347         if (call_can_make_abnormal_goto (t))
2348           return true;
2349
2350         /* A call also alters control flow if it does not return.  */
2351         if (flags & ECF_NORETURN)
2352           return true;
2353
2354         /* TM ending statements have backedges out of the transaction.
2355            Return true so we split the basic block containing them.
2356            Note that the TM_BUILTIN test is merely an optimization.  */
2357         if ((flags & ECF_TM_BUILTIN)
2358             && is_tm_ending_fndecl (gimple_call_fndecl (t)))
2359           return true;
2360
2361         /* BUILT_IN_RETURN call is same as return statement.  */
2362         if (gimple_call_builtin_p (t, BUILT_IN_RETURN))
2363           return true;
2364       }
2365       break;
2366
2367     case GIMPLE_EH_DISPATCH:
2368       /* EH_DISPATCH branches to the individual catch handlers at
2369          this level of a try or allowed-exceptions region.  It can
2370          fallthru to the next statement as well.  */
2371       return true;
2372
2373     case GIMPLE_ASM:
2374       if (gimple_asm_nlabels (t) > 0)
2375         return true;
2376       break;
2377
2378     CASE_GIMPLE_OMP:
2379       /* OpenMP directives alter control flow.  */
2380       return true;
2381
2382     case GIMPLE_TRANSACTION:
2383       /* A transaction start alters control flow.  */
2384       return true;
2385
2386     default:
2387       break;
2388     }
2389
2390   /* If a statement can throw, it alters control flow.  */
2391   return stmt_can_throw_internal (t);
2392 }
2393
2394
2395 /* Return true if T is a simple local goto.  */
2396
2397 bool
2398 simple_goto_p (gimple t)
2399 {
2400   return (gimple_code (t) == GIMPLE_GOTO
2401           && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL);
2402 }
2403
2404
2405 /* Return true if STMT should start a new basic block.  PREV_STMT is
2406    the statement preceding STMT.  It is used when STMT is a label or a
2407    case label.  Labels should only start a new basic block if their
2408    previous statement wasn't a label.  Otherwise, sequence of labels
2409    would generate unnecessary basic blocks that only contain a single
2410    label.  */
2411
2412 static inline bool
2413 stmt_starts_bb_p (gimple stmt, gimple prev_stmt)
2414 {
2415   if (stmt == NULL)
2416     return false;
2417
2418   /* Labels start a new basic block only if the preceding statement
2419      wasn't a label of the same type.  This prevents the creation of
2420      consecutive blocks that have nothing but a single label.  */
2421   if (gimple_code (stmt) == GIMPLE_LABEL)
2422     {
2423       /* Nonlocal and computed GOTO targets always start a new block.  */
2424       if (DECL_NONLOCAL (gimple_label_label (stmt))
2425           || FORCED_LABEL (gimple_label_label (stmt)))
2426         return true;
2427
2428       if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL)
2429         {
2430           if (DECL_NONLOCAL (gimple_label_label (prev_stmt)))
2431             return true;
2432
2433           cfg_stats.num_merged_labels++;
2434           return false;
2435         }
2436       else
2437         return true;
2438     }
2439
2440   return false;
2441 }
2442
2443
2444 /* Return true if T should end a basic block.  */
2445
2446 bool
2447 stmt_ends_bb_p (gimple t)
2448 {
2449   return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t);
2450 }
2451
2452 /* Remove block annotations and other data structures.  */
2453
2454 void
2455 delete_tree_cfg_annotations (void)
2456 {
2457   label_to_block_map = NULL;
2458 }
2459
2460
2461 /* Return the first statement in basic block BB.  */
2462
2463 gimple
2464 first_stmt (basic_block bb)
2465 {
2466   gimple_stmt_iterator i = gsi_start_bb (bb);
2467   gimple stmt = NULL;
2468
2469   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2470     {
2471       gsi_next (&i);
2472       stmt = NULL;
2473     }
2474   return stmt;
2475 }
2476
2477 /* Return the first non-label statement in basic block BB.  */
2478
2479 static gimple
2480 first_non_label_stmt (basic_block bb)
2481 {
2482   gimple_stmt_iterator i = gsi_start_bb (bb);
2483   while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL)
2484     gsi_next (&i);
2485   return !gsi_end_p (i) ? gsi_stmt (i) : NULL;
2486 }
2487
2488 /* Return the last statement in basic block BB.  */
2489
2490 gimple
2491 last_stmt (basic_block bb)
2492 {
2493   gimple_stmt_iterator i = gsi_last_bb (bb);
2494   gimple stmt = NULL;
2495
2496   while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i))))
2497     {
2498       gsi_prev (&i);
2499       stmt = NULL;
2500     }
2501   return stmt;
2502 }
2503
2504 /* Return the last statement of an otherwise empty block.  Return NULL
2505    if the block is totally empty, or if it contains more than one
2506    statement.  */
2507
2508 gimple
2509 last_and_only_stmt (basic_block bb)
2510 {
2511   gimple_stmt_iterator i = gsi_last_nondebug_bb (bb);
2512   gimple last, prev;
2513
2514   if (gsi_end_p (i))
2515     return NULL;
2516
2517   last = gsi_stmt (i);
2518   gsi_prev_nondebug (&i);
2519   if (gsi_end_p (i))
2520     return last;
2521
2522   /* Empty statements should no longer appear in the instruction stream.
2523      Everything that might have appeared before should be deleted by
2524      remove_useless_stmts, and the optimizers should just gsi_remove
2525      instead of smashing with build_empty_stmt.
2526
2527      Thus the only thing that should appear here in a block containing
2528      one executable statement is a label.  */
2529   prev = gsi_stmt (i);
2530   if (gimple_code (prev) == GIMPLE_LABEL)
2531     return last;
2532   else
2533     return NULL;
2534 }
2535
2536 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE.  */
2537
2538 static void
2539 reinstall_phi_args (edge new_edge, edge old_edge)
2540 {
2541   edge_var_map_vector v;
2542   edge_var_map *vm;
2543   int i;
2544   gimple_stmt_iterator phis;
2545
2546   v = redirect_edge_var_map_vector (old_edge);
2547   if (!v)
2548     return;
2549
2550   for (i = 0, phis = gsi_start_phis (new_edge->dest);
2551        VEC_iterate (edge_var_map, v, i, vm) && !gsi_end_p (phis);
2552        i++, gsi_next (&phis))
2553     {
2554       gimple phi = gsi_stmt (phis);
2555       tree result = redirect_edge_var_map_result (vm);
2556       tree arg = redirect_edge_var_map_def (vm);
2557
2558       gcc_assert (result == gimple_phi_result (phi));
2559
2560       add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm));
2561     }
2562
2563   redirect_edge_var_map_clear (old_edge);
2564 }
2565
2566 /* Returns the basic block after which the new basic block created
2567    by splitting edge EDGE_IN should be placed.  Tries to keep the new block
2568    near its "logical" location.  This is of most help to humans looking
2569    at debugging dumps.  */
2570
2571 static basic_block
2572 split_edge_bb_loc (edge edge_in)
2573 {
2574   basic_block dest = edge_in->dest;
2575   basic_block dest_prev = dest->prev_bb;
2576
2577   if (dest_prev)
2578     {
2579       edge e = find_edge (dest_prev, dest);
2580       if (e && !(e->flags & EDGE_COMPLEX))
2581         return edge_in->src;
2582     }
2583   return dest_prev;
2584 }
2585
2586 /* Split a (typically critical) edge EDGE_IN.  Return the new block.
2587    Abort on abnormal edges.  */
2588
2589 static basic_block
2590 gimple_split_edge (edge edge_in)
2591 {
2592   basic_block new_bb, after_bb, dest;
2593   edge new_edge, e;
2594
2595   /* Abnormal edges cannot be split.  */
2596   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
2597
2598   dest = edge_in->dest;
2599
2600   after_bb = split_edge_bb_loc (edge_in);
2601
2602   new_bb = create_empty_bb (after_bb);
2603   new_bb->frequency = EDGE_FREQUENCY (edge_in);
2604   new_bb->count = edge_in->count;
2605   new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU);
2606   new_edge->probability = REG_BR_PROB_BASE;
2607   new_edge->count = edge_in->count;
2608
2609   e = redirect_edge_and_branch (edge_in, new_bb);
2610   gcc_assert (e == edge_in);
2611   reinstall_phi_args (new_edge, e);
2612
2613   return new_bb;
2614 }
2615
2616
2617 /* Verify properties of the address expression T with base object BASE.  */
2618
2619 static tree
2620 verify_address (tree t, tree base)
2621 {
2622   bool old_constant;
2623   bool old_side_effects;
2624   bool new_constant;
2625   bool new_side_effects;
2626
2627   old_constant = TREE_CONSTANT (t);
2628   old_side_effects = TREE_SIDE_EFFECTS (t);
2629
2630   recompute_tree_invariant_for_addr_expr (t);
2631   new_side_effects = TREE_SIDE_EFFECTS (t);
2632   new_constant = TREE_CONSTANT (t);
2633
2634   if (old_constant != new_constant)
2635     {
2636       error ("constant not recomputed when ADDR_EXPR changed");
2637       return t;
2638     }
2639   if (old_side_effects != new_side_effects)
2640     {
2641       error ("side effects not recomputed when ADDR_EXPR changed");
2642       return t;
2643     }
2644
2645   if (!(TREE_CODE (base) == VAR_DECL
2646         || TREE_CODE (base) == PARM_DECL
2647         || TREE_CODE (base) == RESULT_DECL))
2648     return NULL_TREE;
2649
2650   if (DECL_GIMPLE_REG_P (base))
2651     {
2652       error ("DECL_GIMPLE_REG_P set on a variable with address taken");
2653       return base;
2654     }
2655
2656   return NULL_TREE;
2657 }
2658
2659 /* Callback for walk_tree, check that all elements with address taken are
2660    properly noticed as such.  The DATA is an int* that is 1 if TP was seen
2661    inside a PHI node.  */
2662
2663 static tree
2664 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
2665 {
2666   tree t = *tp, x;
2667
2668   if (TYPE_P (t))
2669     *walk_subtrees = 0;
2670
2671   /* Check operand N for being valid GIMPLE and give error MSG if not.  */
2672 #define CHECK_OP(N, MSG) \
2673   do { if (!is_gimple_val (TREE_OPERAND (t, N)))                \
2674        { error (MSG); return TREE_OPERAND (t, N); }} while (0)
2675
2676   switch (TREE_CODE (t))
2677     {
2678     case SSA_NAME:
2679       if (SSA_NAME_IN_FREE_LIST (t))
2680         {
2681           error ("SSA name in freelist but still referenced");
2682           return *tp;
2683         }
2684       break;
2685
2686     case INDIRECT_REF:
2687       error ("INDIRECT_REF in gimple IL");
2688       return t;
2689
2690     case MEM_REF:
2691       x = TREE_OPERAND (t, 0);
2692       if (!POINTER_TYPE_P (TREE_TYPE (x))
2693           || !is_gimple_mem_ref_addr (x))
2694         {
2695           error ("invalid first operand of MEM_REF");
2696           return x;
2697         }
2698       if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST
2699           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1))))
2700         {
2701           error ("invalid offset operand of MEM_REF");
2702           return TREE_OPERAND (t, 1);
2703         }
2704       if (TREE_CODE (x) == ADDR_EXPR
2705           && (x = verify_address (x, TREE_OPERAND (x, 0))))
2706         return x;
2707       *walk_subtrees = 0;
2708       break;
2709
2710     case ASSERT_EXPR:
2711       x = fold (ASSERT_EXPR_COND (t));
2712       if (x == boolean_false_node)
2713         {
2714           error ("ASSERT_EXPR with an always-false condition");
2715           return *tp;
2716         }
2717       break;
2718
2719     case MODIFY_EXPR:
2720       error ("MODIFY_EXPR not expected while having tuples");
2721       return *tp;
2722
2723     case ADDR_EXPR:
2724       {
2725         tree tem;
2726
2727         gcc_assert (is_gimple_address (t));
2728
2729         /* Skip any references (they will be checked when we recurse down the
2730            tree) and ensure that any variable used as a prefix is marked
2731            addressable.  */
2732         for (x = TREE_OPERAND (t, 0);
2733              handled_component_p (x);
2734              x = TREE_OPERAND (x, 0))
2735           ;
2736
2737         if ((tem = verify_address (t, x)))
2738           return tem;
2739
2740         if (!(TREE_CODE (x) == VAR_DECL
2741               || TREE_CODE (x) == PARM_DECL
2742               || TREE_CODE (x) == RESULT_DECL))
2743           return NULL;
2744
2745         if (!TREE_ADDRESSABLE (x))
2746           {
2747             error ("address taken, but ADDRESSABLE bit not set");
2748             return x;
2749           }
2750
2751         break;
2752       }
2753
2754     case COND_EXPR:
2755       x = COND_EXPR_COND (t);
2756       if (!INTEGRAL_TYPE_P (TREE_TYPE (x)))
2757         {
2758           error ("non-integral used in condition");
2759           return x;
2760         }
2761       if (!is_gimple_condexpr (x))
2762         {
2763           error ("invalid conditional operand");
2764           return x;
2765         }
2766       break;
2767
2768     case NON_LVALUE_EXPR:
2769     case TRUTH_NOT_EXPR:
2770       gcc_unreachable ();
2771
2772     CASE_CONVERT:
2773     case FIX_TRUNC_EXPR:
2774     case FLOAT_EXPR:
2775     case NEGATE_EXPR:
2776     case ABS_EXPR:
2777     case BIT_NOT_EXPR:
2778       CHECK_OP (0, "invalid operand to unary operator");
2779       break;
2780
2781     case REALPART_EXPR:
2782     case IMAGPART_EXPR:
2783     case COMPONENT_REF:
2784     case ARRAY_REF:
2785     case ARRAY_RANGE_REF:
2786     case BIT_FIELD_REF:
2787     case VIEW_CONVERT_EXPR:
2788       /* We have a nest of references.  Verify that each of the operands
2789          that determine where to reference is either a constant or a variable,
2790          verify that the base is valid, and then show we've already checked
2791          the subtrees.  */
2792       while (handled_component_p (t))
2793         {
2794           if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2))
2795             CHECK_OP (2, "invalid COMPONENT_REF offset operator");
2796           else if (TREE_CODE (t) == ARRAY_REF
2797                    || TREE_CODE (t) == ARRAY_RANGE_REF)
2798             {
2799               CHECK_OP (1, "invalid array index");
2800               if (TREE_OPERAND (t, 2))
2801                 CHECK_OP (2, "invalid array lower bound");
2802               if (TREE_OPERAND (t, 3))
2803                 CHECK_OP (3, "invalid array stride");
2804             }
2805           else if (TREE_CODE (t) == BIT_FIELD_REF)
2806             {
2807               if (!host_integerp (TREE_OPERAND (t, 1), 1)
2808                   || !host_integerp (TREE_OPERAND (t, 2), 1))
2809                 {
2810                   error ("invalid position or size operand to BIT_FIELD_REF");
2811                   return t;
2812                 }
2813               else if (INTEGRAL_TYPE_P (TREE_TYPE (t))
2814                        && (TYPE_PRECISION (TREE_TYPE (t))
2815                            != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2816                 {
2817                   error ("integral result type precision does not match "
2818                          "field size of BIT_FIELD_REF");
2819                   return t;
2820                 }
2821               if (!INTEGRAL_TYPE_P (TREE_TYPE (t))
2822                   && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t)))
2823                       != TREE_INT_CST_LOW (TREE_OPERAND (t, 1))))
2824                 {
2825                   error ("mode precision of non-integral result does not "
2826                          "match field size of BIT_FIELD_REF");
2827                   return t;
2828                 }
2829             }
2830
2831           t = TREE_OPERAND (t, 0);
2832         }
2833
2834       if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t))
2835         {
2836           error ("invalid reference prefix");
2837           return t;
2838         }
2839       *walk_subtrees = 0;
2840       break;
2841     case PLUS_EXPR:
2842     case MINUS_EXPR:
2843       /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using
2844          POINTER_PLUS_EXPR. */
2845       if (POINTER_TYPE_P (TREE_TYPE (t)))
2846         {
2847           error ("invalid operand to plus/minus, type is a pointer");
2848           return t;
2849         }
2850       CHECK_OP (0, "invalid operand to binary operator");
2851       CHECK_OP (1, "invalid operand to binary operator");
2852       break;
2853
2854     case POINTER_PLUS_EXPR:
2855       /* Check to make sure the first operand is a pointer or reference type. */
2856       if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0))))
2857         {
2858           error ("invalid operand to pointer plus, first operand is not a pointer");
2859           return t;
2860         }
2861       /* Check to make sure the second operand is a ptrofftype.  */
2862       if (!ptrofftype_p (TREE_TYPE (TREE_OPERAND (t, 1))))
2863         {
2864           error ("invalid operand to pointer plus, second operand is not an "
2865                  "integer type of appropriate width");
2866           return t;
2867         }
2868       /* FALLTHROUGH */
2869     case LT_EXPR:
2870     case LE_EXPR:
2871     case GT_EXPR:
2872     case GE_EXPR:
2873     case EQ_EXPR:
2874     case NE_EXPR:
2875     case UNORDERED_EXPR:
2876     case ORDERED_EXPR:
2877     case UNLT_EXPR:
2878     case UNLE_EXPR:
2879     case UNGT_EXPR:
2880     case UNGE_EXPR:
2881     case UNEQ_EXPR:
2882     case LTGT_EXPR:
2883     case MULT_EXPR:
2884     case TRUNC_DIV_EXPR:
2885     case CEIL_DIV_EXPR:
2886     case FLOOR_DIV_EXPR:
2887     case ROUND_DIV_EXPR:
2888     case TRUNC_MOD_EXPR:
2889     case CEIL_MOD_EXPR:
2890     case FLOOR_MOD_EXPR:
2891     case ROUND_MOD_EXPR:
2892     case RDIV_EXPR:
2893     case EXACT_DIV_EXPR:
2894     case MIN_EXPR:
2895     case MAX_EXPR:
2896     case LSHIFT_EXPR:
2897     case RSHIFT_EXPR:
2898     case LROTATE_EXPR:
2899     case RROTATE_EXPR:
2900     case BIT_IOR_EXPR:
2901     case BIT_XOR_EXPR:
2902     case BIT_AND_EXPR:
2903       CHECK_OP (0, "invalid operand to binary operator");
2904       CHECK_OP (1, "invalid operand to binary operator");
2905       break;
2906
2907     case CONSTRUCTOR:
2908       if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
2909         *walk_subtrees = 0;
2910       break;
2911
2912     case CASE_LABEL_EXPR:
2913       if (CASE_CHAIN (t))
2914         {
2915           error ("invalid CASE_CHAIN");
2916           return t;
2917         }
2918       break;
2919
2920     default:
2921       break;
2922     }
2923   return NULL;
2924
2925 #undef CHECK_OP
2926 }
2927
2928
2929 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference.
2930    Returns true if there is an error, otherwise false.  */
2931
2932 static bool
2933 verify_types_in_gimple_min_lval (tree expr)
2934 {
2935   tree op;
2936
2937   if (is_gimple_id (expr))
2938     return false;
2939
2940   if (TREE_CODE (expr) != TARGET_MEM_REF
2941       && TREE_CODE (expr) != MEM_REF)
2942     {
2943       error ("invalid expression for min lvalue");
2944       return true;
2945     }
2946
2947   /* TARGET_MEM_REFs are strange beasts.  */
2948   if (TREE_CODE (expr) == TARGET_MEM_REF)
2949     return false;
2950
2951   op = TREE_OPERAND (expr, 0);
2952   if (!is_gimple_val (op))
2953     {
2954       error ("invalid operand in indirect reference");
2955       debug_generic_stmt (op);
2956       return true;
2957     }
2958   /* Memory references now generally can involve a value conversion.  */
2959
2960   return false;
2961 }
2962
2963 /* Verify if EXPR is a valid GIMPLE reference expression.  If
2964    REQUIRE_LVALUE is true verifies it is an lvalue.  Returns true
2965    if there is an error, otherwise false.  */
2966
2967 static bool
2968 verify_types_in_gimple_reference (tree expr, bool require_lvalue)
2969 {
2970   while (handled_component_p (expr))
2971     {
2972       tree op = TREE_OPERAND (expr, 0);
2973
2974       if (TREE_CODE (expr) == ARRAY_REF
2975           || TREE_CODE (expr) == ARRAY_RANGE_REF)
2976         {
2977           if (!is_gimple_val (TREE_OPERAND (expr, 1))
2978               || (TREE_OPERAND (expr, 2)
2979                   && !is_gimple_val (TREE_OPERAND (expr, 2)))
2980               || (TREE_OPERAND (expr, 3)
2981                   && !is_gimple_val (TREE_OPERAND (expr, 3))))
2982             {
2983               error ("invalid operands to array reference");
2984               debug_generic_stmt (expr);
2985               return true;
2986             }
2987         }
2988
2989       /* Verify if the reference array element types are compatible.  */
2990       if (TREE_CODE (expr) == ARRAY_REF
2991           && !useless_type_conversion_p (TREE_TYPE (expr),
2992                                          TREE_TYPE (TREE_TYPE (op))))
2993         {
2994           error ("type mismatch in array reference");
2995           debug_generic_stmt (TREE_TYPE (expr));
2996           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
2997           return true;
2998         }
2999       if (TREE_CODE (expr) == ARRAY_RANGE_REF
3000           && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)),
3001                                          TREE_TYPE (TREE_TYPE (op))))
3002         {
3003           error ("type mismatch in array range reference");
3004           debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr)));
3005           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3006           return true;
3007         }
3008
3009       if ((TREE_CODE (expr) == REALPART_EXPR
3010            || TREE_CODE (expr) == IMAGPART_EXPR)
3011           && !useless_type_conversion_p (TREE_TYPE (expr),
3012                                          TREE_TYPE (TREE_TYPE (op))))
3013         {
3014           error ("type mismatch in real/imagpart reference");
3015           debug_generic_stmt (TREE_TYPE (expr));
3016           debug_generic_stmt (TREE_TYPE (TREE_TYPE (op)));
3017           return true;
3018         }
3019
3020       if (TREE_CODE (expr) == COMPONENT_REF
3021           && !useless_type_conversion_p (TREE_TYPE (expr),
3022                                          TREE_TYPE (TREE_OPERAND (expr, 1))))
3023         {
3024           error ("type mismatch in component reference");
3025           debug_generic_stmt (TREE_TYPE (expr));
3026           debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1)));
3027           return true;
3028         }
3029
3030       if (TREE_CODE (expr) == VIEW_CONVERT_EXPR)
3031         {
3032           /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check
3033              that their operand is not an SSA name or an invariant when
3034              requiring an lvalue (this usually means there is a SRA or IPA-SRA
3035              bug).  Otherwise there is nothing to verify, gross mismatches at
3036              most invoke undefined behavior.  */
3037           if (require_lvalue
3038               && (TREE_CODE (op) == SSA_NAME
3039                   || is_gimple_min_invariant (op)))
3040             {
3041               error ("conversion of an SSA_NAME on the left hand side");
3042               debug_generic_stmt (expr);
3043               return true;
3044             }
3045           else if (TREE_CODE (op) == SSA_NAME
3046                    && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op)))
3047             {
3048               error ("conversion of register to a different size");
3049               debug_generic_stmt (expr);
3050               return true;
3051             }
3052           else if (!handled_component_p (op))
3053             return false;
3054         }
3055
3056       expr = op;
3057     }
3058
3059   if (TREE_CODE (expr) == MEM_REF)
3060     {
3061       if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0)))
3062         {
3063           error ("invalid address operand in MEM_REF");
3064           debug_generic_stmt (expr);
3065           return true;
3066         }
3067       if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST
3068           || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1))))
3069         {
3070           error ("invalid offset operand in MEM_REF");
3071           debug_generic_stmt (expr);
3072           return true;
3073         }
3074     }
3075   else if (TREE_CODE (expr) == TARGET_MEM_REF)
3076     {
3077       if (!TMR_BASE (expr)
3078           || !is_gimple_mem_ref_addr (TMR_BASE (expr)))
3079         {
3080           error ("invalid address operand in TARGET_MEM_REF");
3081           return true;
3082         }
3083       if (!TMR_OFFSET (expr)
3084           || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST
3085           || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr))))
3086         {
3087           error ("invalid offset operand in TARGET_MEM_REF");
3088           debug_generic_stmt (expr);
3089           return true;
3090         }
3091     }
3092
3093   return ((require_lvalue || !is_gimple_min_invariant (expr))
3094           && verify_types_in_gimple_min_lval (expr));
3095 }
3096
3097 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ)
3098    list of pointer-to types that is trivially convertible to DEST.  */
3099
3100 static bool
3101 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj)
3102 {
3103   tree src;
3104
3105   if (!TYPE_POINTER_TO (src_obj))
3106     return true;
3107
3108   for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src))
3109     if (useless_type_conversion_p (dest, src))
3110       return true;
3111
3112   return false;
3113 }
3114
3115 /* Return true if TYPE1 is a fixed-point type and if conversions to and
3116    from TYPE2 can be handled by FIXED_CONVERT_EXPR.  */
3117
3118 static bool
3119 valid_fixed_convert_types_p (tree type1, tree type2)
3120 {
3121   return (FIXED_POINT_TYPE_P (type1)
3122           && (INTEGRAL_TYPE_P (type2)
3123               || SCALAR_FLOAT_TYPE_P (type2)
3124               || FIXED_POINT_TYPE_P (type2)));
3125 }
3126
3127 /* Verify the contents of a GIMPLE_CALL STMT.  Returns true when there
3128    is a problem, otherwise false.  */
3129
3130 static bool
3131 verify_gimple_call (gimple stmt)
3132 {
3133   tree fn = gimple_call_fn (stmt);
3134   tree fntype, fndecl;
3135   unsigned i;
3136
3137   if (gimple_call_internal_p (stmt))
3138     {
3139       if (fn)
3140         {
3141           error ("gimple call has two targets");
3142           debug_generic_stmt (fn);
3143           return true;
3144         }
3145     }
3146   else
3147     {
3148       if (!fn)
3149         {
3150           error ("gimple call has no target");
3151           return true;
3152         }
3153     }
3154
3155   if (fn && !is_gimple_call_addr (fn))
3156     {
3157       error ("invalid function in gimple call");
3158       debug_generic_stmt (fn);
3159       return true;
3160     }
3161
3162   if (fn
3163       && (!POINTER_TYPE_P (TREE_TYPE (fn))
3164           || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE
3165               && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE)))
3166     {
3167       error ("non-function in gimple call");
3168       return true;
3169     }
3170
3171    fndecl = gimple_call_fndecl (stmt);
3172    if (fndecl
3173        && TREE_CODE (fndecl) == FUNCTION_DECL
3174        && DECL_LOOPING_CONST_OR_PURE_P (fndecl)
3175        && !DECL_PURE_P (fndecl)
3176        && !TREE_READONLY (fndecl))
3177      {
3178        error ("invalid pure const state for function");
3179        return true;
3180      }
3181
3182   if (gimple_call_lhs (stmt)
3183       && (!is_gimple_lvalue (gimple_call_lhs (stmt))
3184           || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true)))
3185     {
3186       error ("invalid LHS in gimple call");
3187       return true;
3188     }
3189
3190   if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt))
3191     {
3192       error ("LHS in noreturn call");
3193       return true;
3194     }
3195
3196   fntype = gimple_call_fntype (stmt);
3197   if (fntype
3198       && gimple_call_lhs (stmt)
3199       && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)),
3200                                      TREE_TYPE (fntype))
3201       /* ???  At least C++ misses conversions at assignments from
3202          void * call results.
3203          ???  Java is completely off.  Especially with functions
3204          returning java.lang.Object.
3205          For now simply allow arbitrary pointer type conversions.  */
3206       && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt)))
3207            && POINTER_TYPE_P (TREE_TYPE (fntype))))
3208     {
3209       error ("invalid conversion in gimple call");
3210       debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt)));
3211       debug_generic_stmt (TREE_TYPE (fntype));
3212       return true;
3213     }
3214
3215   if (gimple_call_chain (stmt)
3216       && !is_gimple_val (gimple_call_chain (stmt)))
3217     {
3218       error ("invalid static chain in gimple call");
3219       debug_generic_stmt (gimple_call_chain (stmt));
3220       return true;
3221     }
3222
3223   /* If there is a static chain argument, this should not be an indirect
3224      call, and the decl should have DECL_STATIC_CHAIN set.  */
3225   if (gimple_call_chain (stmt))
3226     {
3227       if (!gimple_call_fndecl (stmt))
3228         {
3229           error ("static chain in indirect gimple call");
3230           return true;
3231         }
3232       fn = TREE_OPERAND (fn, 0);
3233
3234       if (!DECL_STATIC_CHAIN (fn))
3235         {
3236           error ("static chain with function that doesn%'t use one");
3237           return true;
3238         }
3239     }
3240
3241   /* ???  The C frontend passes unpromoted arguments in case it
3242      didn't see a function declaration before the call.  So for now
3243      leave the call arguments mostly unverified.  Once we gimplify
3244      unit-at-a-time we have a chance to fix this.  */
3245
3246   for (i = 0; i < gimple_call_num_args (stmt); ++i)
3247     {
3248       tree arg = gimple_call_arg (stmt, i);
3249       if ((is_gimple_reg_type (TREE_TYPE (arg))
3250            && !is_gimple_val (arg))
3251           || (!is_gimple_reg_type (TREE_TYPE (arg))
3252               && !is_gimple_lvalue (arg)))
3253         {
3254           error ("invalid argument to gimple call");
3255           debug_generic_expr (arg);
3256           return true;
3257         }
3258     }
3259
3260   return false;
3261 }
3262
3263 /* Verifies the gimple comparison with the result type TYPE and
3264    the operands OP0 and OP1.  */
3265
3266 static bool
3267 verify_gimple_comparison (tree type, tree op0, tree op1)
3268 {
3269   tree op0_type = TREE_TYPE (op0);
3270   tree op1_type = TREE_TYPE (op1);
3271
3272   if (!is_gimple_val (op0) || !is_gimple_val (op1))
3273     {
3274       error ("invalid operands in gimple comparison");
3275       return true;
3276     }
3277
3278   /* For comparisons we do not have the operations type as the
3279      effective type the comparison is carried out in.  Instead
3280      we require that either the first operand is trivially
3281      convertible into the second, or the other way around.
3282      Because we special-case pointers to void we allow
3283      comparisons of pointers with the same mode as well.  */
3284   if (!useless_type_conversion_p (op0_type, op1_type)
3285       && !useless_type_conversion_p (op1_type, op0_type)
3286       && (!POINTER_TYPE_P (op0_type)
3287           || !POINTER_TYPE_P (op1_type)
3288           || TYPE_MODE (op0_type) != TYPE_MODE (op1_type)))
3289     {
3290       error ("mismatching comparison operand types");
3291       debug_generic_expr (op0_type);
3292       debug_generic_expr (op1_type);
3293       return true;
3294     }
3295
3296   /* The resulting type of a comparison may be an effective boolean type.  */
3297   if (INTEGRAL_TYPE_P (type)
3298       && (TREE_CODE (type) == BOOLEAN_TYPE
3299           || TYPE_PRECISION (type) == 1))
3300     ;
3301   /* Or an integer vector type with the same size and element count
3302      as the comparison operand types.  */
3303   else if (TREE_CODE (type) == VECTOR_TYPE
3304            && TREE_CODE (TREE_TYPE (type)) == INTEGER_TYPE)
3305     {
3306       if (TREE_CODE (op0_type) != VECTOR_TYPE
3307           || TREE_CODE (op1_type) != VECTOR_TYPE)
3308         {
3309           error ("non-vector operands in vector comparison");
3310           debug_generic_expr (op0_type);
3311           debug_generic_expr (op1_type);
3312           return true;
3313         }
3314
3315       if (TYPE_VECTOR_SUBPARTS (type) != TYPE_VECTOR_SUBPARTS (op0_type)
3316           || (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (type)))
3317               != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0_type)))))
3318         {
3319           error ("invalid vector comparison resulting type");
3320           debug_generic_expr (type);
3321           return true;
3322         }
3323     }
3324   else
3325     {
3326       error ("bogus comparison result type");
3327       debug_generic_expr (type);
3328       return true;
3329     }
3330
3331   return false;
3332 }
3333
3334 /* Verify a gimple assignment statement STMT with an unary rhs.
3335    Returns true if anything is wrong.  */
3336
3337 static bool
3338 verify_gimple_assign_unary (gimple stmt)
3339 {
3340   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3341   tree lhs = gimple_assign_lhs (stmt);
3342   tree lhs_type = TREE_TYPE (lhs);
3343   tree rhs1 = gimple_assign_rhs1 (stmt);
3344   tree rhs1_type = TREE_TYPE (rhs1);
3345
3346   if (!is_gimple_reg (lhs))
3347     {
3348       error ("non-register as LHS of unary operation");
3349       return true;
3350     }
3351
3352   if (!is_gimple_val (rhs1))
3353     {
3354       error ("invalid operand in unary operation");
3355       return true;
3356     }
3357
3358   /* First handle conversions.  */
3359   switch (rhs_code)
3360     {
3361     CASE_CONVERT:
3362       {
3363         /* Allow conversions from pointer type to integral type only if
3364            there is no sign or zero extension involved.
3365            For targets were the precision of ptrofftype doesn't match that
3366            of pointers we need to allow arbitrary conversions to ptrofftype.  */
3367         if ((POINTER_TYPE_P (lhs_type)
3368              && INTEGRAL_TYPE_P (rhs1_type))
3369             || (POINTER_TYPE_P (rhs1_type)
3370                 && INTEGRAL_TYPE_P (lhs_type)
3371                 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type)
3372                     || ptrofftype_p (sizetype))))
3373           return false;
3374
3375         /* Allow conversion from integer to offset type and vice versa.  */
3376         if ((TREE_CODE (lhs_type) == OFFSET_TYPE
3377              && TREE_CODE (rhs1_type) == INTEGER_TYPE)
3378             || (TREE_CODE (lhs_type) == INTEGER_TYPE
3379                 && TREE_CODE (rhs1_type) == OFFSET_TYPE))
3380           return false;
3381
3382         /* Otherwise assert we are converting between types of the
3383            same kind.  */
3384         if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type))
3385           {
3386             error ("invalid types in nop conversion");
3387             debug_generic_expr (lhs_type);
3388             debug_generic_expr (rhs1_type);
3389             return true;
3390           }
3391
3392         return false;
3393       }
3394
3395     case ADDR_SPACE_CONVERT_EXPR:
3396       {
3397         if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type)
3398             || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type))
3399                 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type))))
3400           {
3401             error ("invalid types in address space conversion");
3402             debug_generic_expr (lhs_type);
3403             debug_generic_expr (rhs1_type);
3404             return true;
3405           }
3406
3407         return false;
3408       }
3409
3410     case FIXED_CONVERT_EXPR:
3411       {
3412         if (!valid_fixed_convert_types_p (lhs_type, rhs1_type)
3413             && !valid_fixed_convert_types_p (rhs1_type, lhs_type))
3414           {
3415             error ("invalid types in fixed-point conversion");
3416             debug_generic_expr (lhs_type);
3417             debug_generic_expr (rhs1_type);
3418             return true;
3419           }
3420
3421         return false;
3422       }
3423
3424     case FLOAT_EXPR:
3425       {
3426         if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type))
3427             && (!VECTOR_INTEGER_TYPE_P (rhs1_type)
3428                 || !VECTOR_FLOAT_TYPE_P(lhs_type)))
3429           {
3430             error ("invalid types in conversion to floating point");
3431             debug_generic_expr (lhs_type);
3432             debug_generic_expr (rhs1_type);
3433             return true;
3434           }
3435
3436         return false;
3437       }
3438
3439     case FIX_TRUNC_EXPR:
3440       {
3441         if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type))
3442             && (!VECTOR_INTEGER_TYPE_P (lhs_type)
3443                 || !VECTOR_FLOAT_TYPE_P(rhs1_type)))
3444           {
3445             error ("invalid types in conversion to integer");
3446             debug_generic_expr (lhs_type);
3447             debug_generic_expr (rhs1_type);
3448             return true;
3449           }
3450
3451         return false;
3452       }
3453
3454     case VEC_UNPACK_HI_EXPR:
3455     case VEC_UNPACK_LO_EXPR:
3456     case REDUC_MAX_EXPR:
3457     case REDUC_MIN_EXPR:
3458     case REDUC_PLUS_EXPR:
3459     case VEC_UNPACK_FLOAT_HI_EXPR:
3460     case VEC_UNPACK_FLOAT_LO_EXPR:
3461       /* FIXME.  */
3462       return false;
3463
3464     case NEGATE_EXPR:
3465     case ABS_EXPR:
3466     case BIT_NOT_EXPR:
3467     case PAREN_EXPR:
3468     case NON_LVALUE_EXPR:
3469     case CONJ_EXPR:
3470       break;
3471
3472     default:
3473       gcc_unreachable ();
3474     }
3475
3476   /* For the remaining codes assert there is no conversion involved.  */
3477   if (!useless_type_conversion_p (lhs_type, rhs1_type))
3478     {
3479       error ("non-trivial conversion in unary operation");
3480       debug_generic_expr (lhs_type);
3481       debug_generic_expr (rhs1_type);
3482       return true;
3483     }
3484
3485   return false;
3486 }
3487
3488 /* Verify a gimple assignment statement STMT with a binary rhs.
3489    Returns true if anything is wrong.  */
3490
3491 static bool
3492 verify_gimple_assign_binary (gimple stmt)
3493 {
3494   enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
3495   tree lhs = gimple_assign_lhs (stmt);
3496   tree lhs_type = TREE_TYPE (lhs);
3497   tree rhs1 = gimple_assign_rhs1 (stmt);
3498   tree rhs1_type = TREE_TYPE (rhs1);
3499   tree rhs2 = gimple_assign_rhs2 (stmt);
3500   tree rhs2_type = TREE_TYPE (rhs2);
3501
3502   if (!is_gimple_reg (lhs))
3503     {
3504       error ("non-register as LHS of binary operation");
3505       return true;
3506     }
3507
3508   if (!is_gimple_val (rhs1)
3509       || !is_gimple_val (rhs2))
3510     {
3511       error ("invalid operands in binary operation");
3512       return true;
3513     }
3514
3515   /* First handle operations that involve different types.  */
3516   switch (rhs_code)
3517     {
3518     case COMPLEX_EXPR:
3519       {
3520         if (TREE_CODE (lhs_type) != COMPLEX_TYPE
3521             || !(INTEGRAL_TYPE_P (rhs1_type)
3522                  || SCALAR_FLOAT_TYPE_P (rhs1_type))
3523             || !(INTEGRAL_TYPE_P (rhs2_type)
3524                  || SCALAR_FLOAT_TYPE_P (rhs2_type)))
3525           {
3526             error ("type mismatch in complex expression");
3527             debug_generic_expr (lhs_type);
3528             debug_generic_expr (rhs1_type);
3529             debug_generic_expr (rhs2_type);
3530             return true;
3531           }
3532
3533         return false;
3534       }
3535
3536     case LSHIFT_EXPR:
3537     case RSHIFT_EXPR:
3538     case LROTATE_EXPR:
3539     case RROTATE_EXPR:
3540       {
3541         /* Shifts and rotates are ok on integral types, fixed point
3542            types and integer vector types.  */
3543         if ((!INTEGRAL_TYPE_P (rhs1_type)
3544              && !FIXED_POINT_TYPE_P (rhs1_type)
3545              && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3546                   && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))))
3547             || (!INTEGRAL_TYPE_P (rhs2_type)
3548                 /* Vector shifts of vectors are also ok.  */
3549                 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE
3550                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3551                      && TREE_CODE (rhs2_type) == VECTOR_TYPE
3552                      && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3553             || !useless_type_conversion_p (lhs_type, rhs1_type))
3554           {
3555             error ("type mismatch in shift expression");
3556             debug_generic_expr (lhs_type);
3557             debug_generic_expr (rhs1_type);
3558             debug_generic_expr (rhs2_type);
3559             return true;
3560           }
3561
3562         return false;
3563       }
3564
3565     case VEC_LSHIFT_EXPR:
3566     case VEC_RSHIFT_EXPR:
3567       {
3568         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3569             || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3570                  || POINTER_TYPE_P (TREE_TYPE (rhs1_type))
3571                  || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type))
3572                  || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type)))
3573             || (!INTEGRAL_TYPE_P (rhs2_type)
3574                 && (TREE_CODE (rhs2_type) != VECTOR_TYPE
3575                     || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type))))
3576             || !useless_type_conversion_p (lhs_type, rhs1_type))
3577           {
3578             error ("type mismatch in vector shift expression");
3579             debug_generic_expr (lhs_type);
3580             debug_generic_expr (rhs1_type);
3581             debug_generic_expr (rhs2_type);
3582             return true;
3583           }
3584         /* For shifting a vector of non-integral components we
3585            only allow shifting by a constant multiple of the element size.  */
3586         if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type))
3587             && (TREE_CODE (rhs2) != INTEGER_CST
3588                 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2,
3589                                            TYPE_SIZE (TREE_TYPE (rhs1_type)))))
3590           {
3591             error ("non-element sized vector shift of floating point vector");
3592             return true;
3593           }
3594
3595         return false;
3596       }
3597
3598     case WIDEN_LSHIFT_EXPR:
3599       {
3600         if (!INTEGRAL_TYPE_P (lhs_type)
3601             || !INTEGRAL_TYPE_P (rhs1_type)
3602             || TREE_CODE (rhs2) != INTEGER_CST
3603             || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)))
3604           {
3605             error ("type mismatch in widening vector shift expression");
3606             debug_generic_expr (lhs_type);
3607             debug_generic_expr (rhs1_type);
3608             debug_generic_expr (rhs2_type);
3609             return true;
3610           }
3611
3612         return false;
3613       }
3614
3615     case VEC_WIDEN_LSHIFT_HI_EXPR:
3616     case VEC_WIDEN_LSHIFT_LO_EXPR:
3617       {
3618         if (TREE_CODE (rhs1_type) != VECTOR_TYPE
3619             || TREE_CODE (lhs_type) != VECTOR_TYPE