gcc/gimple-iterator.c

   1 /* Iterator routines for GIMPLE statements.
   2    Copyright (C) 2007-2014 Free Software Foundation, Inc.
   3    Contributed by Aldy Hernandez  <aldy@quesejoda.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "predict.h"
  27 #include "vec.h"
  28 #include "hashtab.h"
  29 #include "hash-set.h"
  30 #include "machmode.h"
  31 #include "hard-reg-set.h"
  32 #include "input.h"
  33 #include "function.h"
  34 #include "dominance.h"
  35 #include "cfg.h"
  36 #include "basic-block.h"
  37 #include "tree-ssa-alias.h"
  38 #include "internal-fn.h"
  39 #include "tree-eh.h"
  40 #include "gimple-expr.h"
  41 #include "is-a.h"
  42 #include "gimple.h"
  43 #include "gimple-iterator.h"
  44 #include "gimple-ssa.h"
  45 #include "hash-map.h"
  46 #include "plugin-api.h"
  47 #include "ipa-ref.h"
  48 #include "cgraph.h"
  49 #include "tree-cfg.h"
  50 #include "tree-phinodes.h"
  51 #include "ssa-iterators.h"
  52 #include "tree-ssa.h"
  53 #include "value-prof.h"
  54
  55
  56 /* Mark the statement STMT as modified, and update it.  */
  57
  58 static inline void
  59 update_modified_stmt (gimple stmt)
  60 {
  61   if (!ssa_operands_active (cfun))
  62     return;
  63   update_stmt_if_modified (stmt);
  64 }
  65
  66
  67 /* Mark the statements in SEQ as modified, and update them.  */
  68
  69 static void
  70 update_modified_stmts (gimple_seq seq)
  71 {
  72   gimple_stmt_iterator gsi;
  73
  74   if (!ssa_operands_active (cfun))
  75     return;
  76   for (gsi = gsi_start (seq); !gsi_end_p (gsi); gsi_next (&gsi))
  77     update_stmt_if_modified (gsi_stmt (gsi));
  78 }
  79
  80
  81 /* Set BB to be the basic block for all the statements in the list
  82    starting at FIRST and LAST.  */
  83
  84 static void
  85 update_bb_for_stmts (gimple_seq_node first, gimple_seq_node last,
  86                      basic_block bb)
  87 {
  88   gimple_seq_node n;
  89
  90   for (n = first; n; n = n->next)
  91     {
  92       gimple_set_bb (n, bb);
  93       if (n == last)
  94         break;
  95     }
  96 }
  97
  98 /* Set the frequencies for the cgraph_edges for each of the calls
  99    starting at FIRST for their new position within BB.  */
 100
 101 static void
 102 update_call_edge_frequencies (gimple_seq_node first, basic_block bb)
 103 {
 104   struct cgraph_node *cfun_node = NULL;
 105   int bb_freq = 0;
 106   gimple_seq_node n;
 107
 108   for (n = first; n ; n = n->next)
 109     if (is_gimple_call (n))
 110       {
 111         struct cgraph_edge *e;
 112
 113         /* These function calls are expensive enough that we want
 114            to avoid calling them if we never see any calls.  */
 115         if (cfun_node == NULL)
 116           {
 117             cfun_node = cgraph_node::get (current_function_decl);
 118             bb_freq = (compute_call_stmt_bb_frequency
 119                        (current_function_decl, bb));
 120           }
 121
 122         e = cfun_node->get_edge (n);
 123         if (e != NULL)
 124           e->frequency = bb_freq;
 125       }
 126 }
 127
 128 /* Insert the sequence delimited by nodes FIRST and LAST before
 129    iterator I.  M specifies how to update iterator I after insertion
 130    (see enum gsi_iterator_update).
 131
 132    This routine assumes that there is a forward and backward path
 133    between FIRST and LAST (i.e., they are linked in a doubly-linked
 134    list).  Additionally, if FIRST == LAST, this routine will properly
 135    insert a single node.  */
 136
 137 static void
 138 gsi_insert_seq_nodes_before (gimple_stmt_iterator *i,
 139                              gimple_seq_node first,
 140                              gimple_seq_node last,
 141                              enum gsi_iterator_update mode)
 142 {
 143   basic_block bb;
 144   gimple_seq_node cur = i->ptr;
 145
 146   gcc_assert (!cur || cur->prev);
 147
 148   if ((bb = gsi_bb (*i)) != NULL)
 149     update_bb_for_stmts (first, last, bb);
 150
 151   /* Link SEQ before CUR in the sequence.  */
 152   if (cur)
 153     {
 154       first->prev = cur->prev;
 155       if (first->prev->next)
 156         first->prev->next = first;
 157       else
 158         gimple_seq_set_first (i->seq, first);
 159       last->next = cur;
 160       cur->prev = last;
 161     }
 162   else
 163     {
 164       gimple_seq_node itlast = gimple_seq_last (*i->seq);
 165
 166       /* If CUR is NULL, we link at the end of the sequence (this case happens
 167          when gsi_after_labels is called for a basic block that contains only
 168          labels, so it returns an iterator after the end of the block, and
 169          we need to insert before it; it might be cleaner to add a flag to the
 170          iterator saying whether we are at the start or end of the list).  */
 171       last->next = NULL;
 172       if (itlast)
 173         {
 174           first->prev = itlast;
 175           itlast->next = first;
 176         }
 177       else
 178         gimple_seq_set_first (i->seq, first);
 179       gimple_seq_set_last (i->seq, last);
 180     }
 181
 182   /* Update the iterator, if requested.  */
 183   switch (mode)
 184     {
 185     case GSI_NEW_STMT:
 186     case GSI_CONTINUE_LINKING:
 187       i->ptr = first;
 188       break;
 189     case GSI_SAME_STMT:
 190       break;
 191     default:
 192       gcc_unreachable ();
 193     }
 194 }
 195
 196
 197 /* Inserts the sequence of statements SEQ before the statement pointed
 198    by iterator I.  MODE indicates what to do with the iterator after
 199    insertion (see enum gsi_iterator_update).
 200
 201    This function does not scan for new operands.  It is provided for
 202    the use of the gimplifier, which manipulates statements for which
 203    def/use information has not yet been constructed.  Most callers
 204    should use gsi_insert_seq_before.  */
 205
 206 void
 207 gsi_insert_seq_before_without_update (gimple_stmt_iterator *i, gimple_seq seq,
 208                                       enum gsi_iterator_update mode)
 209 {
 210   gimple_seq_node first, last;
 211
 212   if (seq == NULL)
 213     return;
 214
 215   /* Don't allow inserting a sequence into itself.  */
 216   gcc_assert (seq != *i->seq);
 217
 218   first = gimple_seq_first (seq);
 219   last = gimple_seq_last (seq);
 220
 221   /* Empty sequences need no work.  */
 222   if (!first || !last)
 223     {
 224       gcc_assert (first == last);
 225       return;
 226     }
 227
 228   gsi_insert_seq_nodes_before (i, first, last, mode);
 229 }
 230
 231
 232 /* Inserts the sequence of statements SEQ before the statement pointed
 233    by iterator I.  MODE indicates what to do with the iterator after
 234    insertion (see enum gsi_iterator_update). Scan the statements in SEQ
 235    for new operands.  */
 236
 237 void
 238 gsi_insert_seq_before (gimple_stmt_iterator *i, gimple_seq seq,
 239                        enum gsi_iterator_update mode)
 240 {
 241   update_modified_stmts (seq);
 242   gsi_insert_seq_before_without_update (i, seq, mode);
 243 }
 244
 245
 246 /* Insert the sequence delimited by nodes FIRST and LAST after
 247    iterator I.  M specifies how to update iterator I after insertion
 248    (see enum gsi_iterator_update).
 249
 250    This routine assumes that there is a forward and backward path
 251    between FIRST and LAST (i.e., they are linked in a doubly-linked
 252    list).  Additionally, if FIRST == LAST, this routine will properly
 253    insert a single node.  */
 254
 255 static void
 256 gsi_insert_seq_nodes_after (gimple_stmt_iterator *i,
 257                             gimple_seq_node first,
 258                             gimple_seq_node last,
 259                             enum gsi_iterator_update m)
 260 {
 261   basic_block bb;
 262   gimple_seq_node cur = i->ptr;
 263
 264   gcc_assert (!cur || cur->prev);
 265
 266   /* If the iterator is inside a basic block, we need to update the
 267      basic block information for all the nodes between FIRST and LAST.  */
 268   if ((bb = gsi_bb (*i)) != NULL)
 269     update_bb_for_stmts (first, last, bb);
 270
 271   /* Link SEQ after CUR.  */
 272   if (cur)
 273     {
 274       last->next = cur->next;
 275       if (last->next)
 276         {
 277           last->next->prev = last;
 278         }
 279       else
 280         gimple_seq_set_last (i->seq, last);
 281       first->prev = cur;
 282       cur->next = first;
 283     }
 284   else
 285     {
 286       gcc_assert (!gimple_seq_last (*i->seq));
 287       last->next = NULL;
 288       gimple_seq_set_first (i->seq, first);
 289       gimple_seq_set_last (i->seq, last);
 290     }
 291
 292   /* Update the iterator, if requested.  */
 293   switch (m)
 294     {
 295     case GSI_NEW_STMT:
 296       i->ptr = first;
 297       break;
 298     case GSI_CONTINUE_LINKING:
 299       i->ptr = last;
 300       break;
 301     case GSI_SAME_STMT:
 302       gcc_assert (cur);
 303       break;
 304     default:
 305       gcc_unreachable ();
 306     }
 307 }
 308
 309
 310 /* Links sequence SEQ after the statement pointed-to by iterator I.
 311    MODE is as in gsi_insert_after.
 312
 313    This function does not scan for new operands.  It is provided for
 314    the use of the gimplifier, which manipulates statements for which
 315    def/use information has not yet been constructed.  Most callers
 316    should use gsi_insert_seq_after.  */
 317
 318 void
 319 gsi_insert_seq_after_without_update (gimple_stmt_iterator *i, gimple_seq seq,
 320                                      enum gsi_iterator_update mode)
 321 {
 322   gimple_seq_node first, last;
 323
 324   if (seq == NULL)
 325     return;
 326
 327   /* Don't allow inserting a sequence into itself.  */
 328   gcc_assert (seq != *i->seq);
 329
 330   first = gimple_seq_first (seq);
 331   last = gimple_seq_last (seq);
 332
 333   /* Empty sequences need no work.  */
 334   if (!first || !last)
 335     {
 336       gcc_assert (first == last);
 337       return;
 338     }
 339
 340   gsi_insert_seq_nodes_after (i, first, last, mode);
 341 }
 342
 343
 344 /* Links sequence SEQ after the statement pointed-to by iterator I.
 345    MODE is as in gsi_insert_after.  Scan the statements in SEQ
 346    for new operands.  */
 347
 348 void
 349 gsi_insert_seq_after (gimple_stmt_iterator *i, gimple_seq seq,
 350                       enum gsi_iterator_update mode)
 351 {
 352   update_modified_stmts (seq);
 353   gsi_insert_seq_after_without_update (i, seq, mode);
 354 }
 355
 356
 357 /* Move all statements in the sequence after I to a new sequence.
 358    Return this new sequence.  */
 359
 360 gimple_seq
 361 gsi_split_seq_after (gimple_stmt_iterator i)
 362 {
 363   gimple_seq_node cur, next;
 364   gimple_seq *pold_seq, new_seq;
 365
 366   cur = i.ptr;
 367
 368   /* How can we possibly split after the end, or before the beginning?  */
 369   gcc_assert (cur && cur->next);
 370   next = cur->next;
 371
 372   pold_seq = i.seq;
 373
 374   gimple_seq_set_first (&new_seq, next);
 375   gimple_seq_set_last (&new_seq, gimple_seq_last (*pold_seq));
 376   gimple_seq_set_last (pold_seq, cur);
 377   cur->next = NULL;
 378
 379   return new_seq;
 380 }
 381
 382
 383 /* Set the statement to which GSI points to STMT.  This only updates
 384    the iterator and the gimple sequence, it doesn't do the bookkeeping
 385    of gsi_replace.  */
 386
 387 void
 388 gsi_set_stmt (gimple_stmt_iterator *gsi, gimple stmt)
 389 {
 390   gimple orig_stmt = gsi_stmt (*gsi);
 391   gimple prev, next;
 392
 393   stmt->next = next = orig_stmt->next;
 394   stmt->prev = prev = orig_stmt->prev;
 395   /* Note how we don't clear next/prev of orig_stmt.  This is so that
 396      copies of *GSI our callers might still hold (to orig_stmt)
 397      can be advanced as if they too were replaced.  */
 398   if (prev->next)
 399     prev->next = stmt;
 400   else
 401     gimple_seq_set_first (gsi->seq, stmt);
 402   if (next)
 403     next->prev = stmt;
 404   else
 405     gimple_seq_set_last (gsi->seq, stmt);
 406
 407   gsi->ptr = stmt;
 408 }
 409
 410
 411 /* Move all statements in the sequence before I to a new sequence.
 412    Return this new sequence.  I is set to the head of the new list.  */
 413
 414 void
 415 gsi_split_seq_before (gimple_stmt_iterator *i, gimple_seq *pnew_seq)
 416 {
 417   gimple_seq_node cur, prev;
 418   gimple_seq old_seq;
 419
 420   cur = i->ptr;
 421
 422   /* How can we possibly split after the end?  */
 423   gcc_assert (cur);
 424   prev = cur->prev;
 425
 426   old_seq = *i->seq;
 427   if (!prev->next)
 428     *i->seq = NULL;
 429   i->seq = pnew_seq;
 430
 431   /* Set the limits on NEW_SEQ.  */
 432   gimple_seq_set_first (pnew_seq, cur);
 433   gimple_seq_set_last (pnew_seq, gimple_seq_last (old_seq));
 434
 435   /* Cut OLD_SEQ before I.  */
 436   gimple_seq_set_last (&old_seq, prev);
 437   if (prev->next)
 438     prev->next = NULL;
 439 }
 440
 441
 442 /* Replace the statement pointed-to by GSI to STMT.  If UPDATE_EH_INFO
 443    is true, the exception handling information of the original
 444    statement is moved to the new statement.  Assignments must only be
 445    replaced with assignments to the same LHS.  Returns whether EH edge
 446    cleanup is required.  */
 447
 448 bool
 449 gsi_replace (gimple_stmt_iterator *gsi, gimple stmt, bool update_eh_info)
 450 {
 451   gimple orig_stmt = gsi_stmt (*gsi);
 452   bool require_eh_edge_purge = false;
 453
 454   if (stmt == orig_stmt)
 455     return false;
 456
 457   gcc_assert (!gimple_has_lhs (orig_stmt) || !gimple_has_lhs (stmt)
 458               || gimple_get_lhs (orig_stmt) == gimple_get_lhs (stmt));
 459
 460   gimple_set_location (stmt, gimple_location (orig_stmt));
 461   gimple_set_bb (stmt, gsi_bb (*gsi));
 462
 463   /* Preserve EH region information from the original statement, if
 464      requested by the caller.  */
 465   if (update_eh_info)
 466     require_eh_edge_purge = maybe_clean_or_replace_eh_stmt (orig_stmt, stmt);
 467
 468   gimple_duplicate_stmt_histograms (cfun, stmt, cfun, orig_stmt);
 469
 470   /* Free all the data flow information for ORIG_STMT.  */
 471   gimple_set_bb (orig_stmt, NULL);
 472   gimple_remove_stmt_histograms (cfun, orig_stmt);
 473   delink_stmt_imm_use (orig_stmt);
 474
 475   gsi_set_stmt (gsi, stmt);
 476   gimple_set_modified (stmt, true);
 477   update_modified_stmt (stmt);
 478   return require_eh_edge_purge;
 479 }
 480
 481
 482 /* Replace the statement pointed-to by GSI with the sequence SEQ.
 483    If UPDATE_EH_INFO is true, the exception handling information of
 484    the original statement is moved to the last statement of the new
 485    sequence.  If the old statement is an assignment, then so must
 486    be the last statement of the new sequence, and they must have the
 487    same LHS.  */
 488
 489 void
 490 gsi_replace_with_seq (gimple_stmt_iterator *gsi, gimple_seq seq,
 491                       bool update_eh_info)
 492 {
 493   gimple_stmt_iterator seqi;
 494   gimple last;
 495   if (gimple_seq_empty_p (seq))
 496     {
 497       gsi_remove (gsi, true);
 498       return;
 499     }
 500   seqi = gsi_last (seq);
 501   last = gsi_stmt (seqi);
 502   gsi_remove (&seqi, false);
 503   gsi_insert_seq_before (gsi, seq, GSI_SAME_STMT);
 504   gsi_replace (gsi, last, update_eh_info);
 505 }
 506
 507
 508 /* Insert statement STMT before the statement pointed-to by iterator I.
 509    M specifies how to update iterator I after insertion (see enum
 510    gsi_iterator_update).
 511
 512    This function does not scan for new operands.  It is provided for
 513    the use of the gimplifier, which manipulates statements for which
 514    def/use information has not yet been constructed.  Most callers
 515    should use gsi_insert_before.  */
 516
 517 void
 518 gsi_insert_before_without_update (gimple_stmt_iterator *i, gimple stmt,
 519                                   enum gsi_iterator_update m)
 520 {
 521   gsi_insert_seq_nodes_before (i, stmt, stmt, m);
 522 }
 523
 524 /* Insert statement STMT before the statement pointed-to by iterator I.
 525    Update STMT's basic block and scan it for new operands.  M
 526    specifies how to update iterator I after insertion (see enum
 527    gsi_iterator_update).  */
 528
 529 void
 530 gsi_insert_before (gimple_stmt_iterator *i, gimple stmt,
 531                    enum gsi_iterator_update m)
 532 {
 533   update_modified_stmt (stmt);
 534   gsi_insert_before_without_update (i, stmt, m);
 535 }
 536
 537
 538 /* Insert statement STMT after the statement pointed-to by iterator I.
 539    M specifies how to update iterator I after insertion (see enum
 540    gsi_iterator_update).
 541
 542    This function does not scan for new operands.  It is provided for
 543    the use of the gimplifier, which manipulates statements for which
 544    def/use information has not yet been constructed.  Most callers
 545    should use gsi_insert_after.  */
 546
 547 void
 548 gsi_insert_after_without_update (gimple_stmt_iterator *i, gimple stmt,
 549                                  enum gsi_iterator_update m)
 550 {
 551   gsi_insert_seq_nodes_after (i, stmt, stmt, m);
 552 }
 553
 554
 555 /* Insert statement STMT after the statement pointed-to by iterator I.
 556    Update STMT's basic block and scan it for new operands.  M
 557    specifies how to update iterator I after insertion (see enum
 558    gsi_iterator_update).  */
 559
 560 void
 561 gsi_insert_after (gimple_stmt_iterator *i, gimple stmt,
 562                   enum gsi_iterator_update m)
 563 {
 564   update_modified_stmt (stmt);
 565   gsi_insert_after_without_update (i, stmt, m);
 566 }
 567
 568
 569 /* Remove the current stmt from the sequence.  The iterator is updated
 570    to point to the next statement.
 571
 572    REMOVE_PERMANENTLY is true when the statement is going to be removed
 573    from the IL and not reinserted elsewhere.  In that case we remove the
 574    statement pointed to by iterator I from the EH tables, and free its
 575    operand caches.  Otherwise we do not modify this information.  Returns
 576    true whether EH edge cleanup is required.  */
 577
 578 bool
 579 gsi_remove (gimple_stmt_iterator *i, bool remove_permanently)
 580 {
 581   gimple_seq_node cur, next, prev;
 582   gimple stmt = gsi_stmt (*i);
 583   bool require_eh_edge_purge = false;
 584
 585   if (gimple_code (stmt) != GIMPLE_PHI)
 586     insert_debug_temps_for_defs (i);
 587
 588   /* Free all the data flow information for STMT.  */
 589   gimple_set_bb (stmt, NULL);
 590   delink_stmt_imm_use (stmt);
 591   gimple_set_modified (stmt, true);
 592
 593   if (remove_permanently)
 594     {
 595       require_eh_edge_purge = remove_stmt_from_eh_lp (stmt);
 596       gimple_remove_stmt_histograms (cfun, stmt);
 597     }
 598
 599   /* Update the iterator and re-wire the links in I->SEQ.  */
 600   cur = i->ptr;
 601   next = cur->next;
 602   prev = cur->prev;
 603   /* See gsi_set_stmt for why we don't reset prev/next of STMT.  */
 604
 605   if (next)
 606     /* Cur is not last.  */
 607     next->prev = prev;
 608   else if (prev->next)
 609     /* Cur is last but not first.  */
 610     gimple_seq_set_last (i->seq, prev);
 611
 612   if (prev->next)
 613     /* Cur is not first.  */
 614     prev->next = next;
 615   else
 616     /* Cur is first.  */
 617     *i->seq = next;
 618
 619   i->ptr = next;
 620
 621   return require_eh_edge_purge;
 622 }
 623
 624
 625 /* Finds iterator for STMT.  */
 626
 627 gimple_stmt_iterator
 628 gsi_for_stmt (gimple stmt)
 629 {
 630   gimple_stmt_iterator i;
 631   basic_block bb = gimple_bb (stmt);
 632
 633   if (gimple_code (stmt) == GIMPLE_PHI)
 634     i = gsi_start_phis (bb);
 635   else
 636     i = gsi_start_bb (bb);
 637
 638   i.ptr = stmt;
 639   return i;
 640 }
 641
 642
 643 /* Move the statement at FROM so it comes right after the statement at TO.  */
 644
 645 void
 646 gsi_move_after (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
 647 {
 648   gimple stmt = gsi_stmt (*from);
 649   gsi_remove (from, false);
 650
 651   /* We must have GSI_NEW_STMT here, as gsi_move_after is sometimes used to
 652      move statements to an empty block.  */
 653   gsi_insert_after (to, stmt, GSI_NEW_STMT);
 654 }
 655
 656
 657 /* Move the statement at FROM so it comes right before the statement
 658    at TO.  */
 659
 660 void
 661 gsi_move_before (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
 662 {
 663   gimple stmt = gsi_stmt (*from);
 664   gsi_remove (from, false);
 665
 666   /* For consistency with gsi_move_after, it might be better to have
 667      GSI_NEW_STMT here; however, that breaks several places that expect
 668      that TO does not change.  */
 669   gsi_insert_before (to, stmt, GSI_SAME_STMT);
 670 }
 671
 672
 673 /* Move the statement at FROM to the end of basic block BB.  */
 674
 675 void
 676 gsi_move_to_bb_end (gimple_stmt_iterator *from, basic_block bb)
 677 {
 678   gimple_stmt_iterator last = gsi_last_bb (bb);
 679   gcc_checking_assert (gsi_bb (last) == bb);
 680
 681   /* Have to check gsi_end_p because it could be an empty block.  */
 682   if (!gsi_end_p (last) && is_ctrl_stmt (gsi_stmt (last)))
 683     gsi_move_before (from, &last);
 684   else
 685     gsi_move_after (from, &last);
 686 }
 687
 688
 689 /* Add STMT to the pending list of edge E.  No actual insertion is
 690    made until a call to gsi_commit_edge_inserts () is made.  */
 691
 692 void
 693 gsi_insert_on_edge (edge e, gimple stmt)
 694 {
 695   gimple_seq_add_stmt (&PENDING_STMT (e), stmt);
 696 }
 697
 698 /* Add the sequence of statements SEQ to the pending list of edge E.
 699    No actual insertion is made until a call to gsi_commit_edge_inserts
 700    is made.  */
 701
 702 void
 703 gsi_insert_seq_on_edge (edge e, gimple_seq seq)
 704 {
 705   gimple_seq_add_seq (&PENDING_STMT (e), seq);
 706 }
 707
 708 /* Return a new iterator pointing to the first statement in sequence of
 709    statements on edge E.  Such statements need to be subsequently moved into a
 710    basic block by calling gsi_commit_edge_inserts.  */
 711
 712 gimple_stmt_iterator
 713 gsi_start_edge (edge e)
 714 {
 715   return gsi_start (PENDING_STMT (e));
 716 }
 717
 718 /* Insert the statement pointed-to by GSI into edge E.  Every attempt
 719    is made to place the statement in an existing basic block, but
 720    sometimes that isn't possible.  When it isn't possible, the edge is
 721    split and the statement is added to the new block.
 722
 723    In all cases, the returned *GSI points to the correct location.  The
 724    return value is true if insertion should be done after the location,
 725    or false if it should be done before the location.  If a new basic block
 726    has to be created, it is stored in *NEW_BB.  */
 727
 728 static bool
 729 gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi,
 730                              basic_block *new_bb)
 731 {
 732   basic_block dest, src;
 733   gimple tmp;
 734
 735   dest = e->dest;
 736
 737   /* If the destination has one predecessor which has no PHI nodes,
 738      insert there.  Except for the exit block.
 739
 740      The requirement for no PHI nodes could be relaxed.  Basically we
 741      would have to examine the PHIs to prove that none of them used
 742      the value set by the statement we want to insert on E.  That
 743      hardly seems worth the effort.  */
 744  restart:
 745   if (single_pred_p (dest)
 746       && gimple_seq_empty_p (phi_nodes (dest))
 747       && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
 748     {
 749       *gsi = gsi_start_bb (dest);
 750       if (gsi_end_p (*gsi))
 751         return true;
 752
 753       /* Make sure we insert after any leading labels.  */
 754       tmp = gsi_stmt (*gsi);
 755       while (gimple_code (tmp) == GIMPLE_LABEL)
 756         {
 757           gsi_next (gsi);
 758           if (gsi_end_p (*gsi))
 759             break;
 760           tmp = gsi_stmt (*gsi);
 761         }
 762
 763       if (gsi_end_p (*gsi))
 764         {
 765           *gsi = gsi_last_bb (dest);
 766           return true;
 767         }
 768       else
 769         return false;
 770     }
 771
 772   /* If the source has one successor, the edge is not abnormal and
 773      the last statement does not end a basic block, insert there.
 774      Except for the entry block.  */
 775   src = e->src;
 776   if ((e->flags & EDGE_ABNORMAL) == 0
 777       && single_succ_p (src)
 778       && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
 779     {
 780       *gsi = gsi_last_bb (src);
 781       if (gsi_end_p (*gsi))
 782         return true;
 783
 784       tmp = gsi_stmt (*gsi);
 785       if (!stmt_ends_bb_p (tmp))
 786         return true;
 787
 788       switch (gimple_code (tmp))
 789         {
 790         case GIMPLE_RETURN:
 791         case GIMPLE_RESX:
 792           return false;
 793         default:
 794           break;
 795         }
 796     }
 797
 798   /* Otherwise, create a new basic block, and split this edge.  */
 799   dest = split_edge (e);
 800   if (new_bb)
 801     *new_bb = dest;
 802   e = single_pred_edge (dest);
 803   goto restart;
 804 }
 805
 806
 807 /* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts.  If a new
 808    block has to be created, it is returned.  */
 809
 810 basic_block
 811 gsi_insert_on_edge_immediate (edge e, gimple stmt)
 812 {
 813   gimple_stmt_iterator gsi;
 814   basic_block new_bb = NULL;
 815   bool ins_after;
 816
 817   gcc_assert (!PENDING_STMT (e));
 818
 819   ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
 820
 821   update_call_edge_frequencies (stmt, gsi.bb);
 822
 823   if (ins_after)
 824     gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 825   else
 826     gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 827
 828   return new_bb;
 829 }
 830
 831 /* Insert STMTS on edge E.  If a new block has to be created, it
 832    is returned.  */
 833
 834 basic_block
 835 gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts)
 836 {
 837   gimple_stmt_iterator gsi;
 838   basic_block new_bb = NULL;
 839   bool ins_after;
 840
 841   gcc_assert (!PENDING_STMT (e));
 842
 843   ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
 844   update_call_edge_frequencies (gimple_seq_first (stmts), gsi.bb);
 845
 846   if (ins_after)
 847     gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
 848   else
 849     gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
 850
 851   return new_bb;
 852 }
 853
 854 /* This routine will commit all pending edge insertions, creating any new
 855    basic blocks which are necessary.  */
 856
 857 void
 858 gsi_commit_edge_inserts (void)
 859 {
 860   basic_block bb;
 861   edge e;
 862   edge_iterator ei;
 863
 864   gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
 865                               NULL);
 866
 867   FOR_EACH_BB_FN (bb, cfun)
 868     FOR_EACH_EDGE (e, ei, bb->succs)
 869       gsi_commit_one_edge_insert (e, NULL);
 870 }
 871
 872
 873 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
 874    to this block, otherwise set it to NULL.  */
 875
 876 void
 877 gsi_commit_one_edge_insert (edge e, basic_block *new_bb)
 878 {
 879   if (new_bb)
 880     *new_bb = NULL;
 881
 882   if (PENDING_STMT (e))
 883     {
 884       gimple_stmt_iterator gsi;
 885       gimple_seq seq = PENDING_STMT (e);
 886       bool ins_after;
 887
 888       PENDING_STMT (e) = NULL;
 889
 890       ins_after = gimple_find_edge_insert_loc (e, &gsi, new_bb);
 891       update_call_edge_frequencies (gimple_seq_first (seq), gsi.bb);
 892
 893       if (ins_after)
 894         gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
 895       else
 896         gsi_insert_seq_before (&gsi, seq, GSI_NEW_STMT);
 897     }
 898 }
 899
 900 /* Returns iterator at the start of the list of phi nodes of BB.  */
 901
 902 gimple_stmt_iterator
 903 gsi_start_phis (basic_block bb)
 904 {
 905   gimple_seq *pseq = phi_nodes_ptr (bb);
 906   return gsi_start_1 (pseq);
 907 }