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 /* Finds iterator for PHI.  */
 643
 644 gphi_iterator
 645 gsi_for_phi (gphi *phi)
 646 {
 647   gphi_iterator i;
 648   basic_block bb = gimple_bb (phi);
 649
 650   i = gsi_start_phis (bb);
 651   i.ptr = phi;
 652
 653   return i;
 654 }
 655
 656 /* Move the statement at FROM so it comes right after the statement at TO.  */
 657
 658 void
 659 gsi_move_after (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
 660 {
 661   gimple stmt = gsi_stmt (*from);
 662   gsi_remove (from, false);
 663
 664   /* We must have GSI_NEW_STMT here, as gsi_move_after is sometimes used to
 665      move statements to an empty block.  */
 666   gsi_insert_after (to, stmt, GSI_NEW_STMT);
 667 }
 668
 669
 670 /* Move the statement at FROM so it comes right before the statement
 671    at TO.  */
 672
 673 void
 674 gsi_move_before (gimple_stmt_iterator *from, gimple_stmt_iterator *to)
 675 {
 676   gimple stmt = gsi_stmt (*from);
 677   gsi_remove (from, false);
 678
 679   /* For consistency with gsi_move_after, it might be better to have
 680      GSI_NEW_STMT here; however, that breaks several places that expect
 681      that TO does not change.  */
 682   gsi_insert_before (to, stmt, GSI_SAME_STMT);
 683 }
 684
 685
 686 /* Move the statement at FROM to the end of basic block BB.  */
 687
 688 void
 689 gsi_move_to_bb_end (gimple_stmt_iterator *from, basic_block bb)
 690 {
 691   gimple_stmt_iterator last = gsi_last_bb (bb);
 692   gcc_checking_assert (gsi_bb (last) == bb);
 693
 694   /* Have to check gsi_end_p because it could be an empty block.  */
 695   if (!gsi_end_p (last) && is_ctrl_stmt (gsi_stmt (last)))
 696     gsi_move_before (from, &last);
 697   else
 698     gsi_move_after (from, &last);
 699 }
 700
 701
 702 /* Add STMT to the pending list of edge E.  No actual insertion is
 703    made until a call to gsi_commit_edge_inserts () is made.  */
 704
 705 void
 706 gsi_insert_on_edge (edge e, gimple stmt)
 707 {
 708   gimple_seq_add_stmt (&PENDING_STMT (e), stmt);
 709 }
 710
 711 /* Add the sequence of statements SEQ to the pending list of edge E.
 712    No actual insertion is made until a call to gsi_commit_edge_inserts
 713    is made.  */
 714
 715 void
 716 gsi_insert_seq_on_edge (edge e, gimple_seq seq)
 717 {
 718   gimple_seq_add_seq (&PENDING_STMT (e), seq);
 719 }
 720
 721 /* Return a new iterator pointing to the first statement in sequence of
 722    statements on edge E.  Such statements need to be subsequently moved into a
 723    basic block by calling gsi_commit_edge_inserts.  */
 724
 725 gimple_stmt_iterator
 726 gsi_start_edge (edge e)
 727 {
 728   return gsi_start (PENDING_STMT (e));
 729 }
 730
 731 /* Insert the statement pointed-to by GSI into edge E.  Every attempt
 732    is made to place the statement in an existing basic block, but
 733    sometimes that isn't possible.  When it isn't possible, the edge is
 734    split and the statement is added to the new block.
 735
 736    In all cases, the returned *GSI points to the correct location.  The
 737    return value is true if insertion should be done after the location,
 738    or false if it should be done before the location.  If a new basic block
 739    has to be created, it is stored in *NEW_BB.  */
 740
 741 static bool
 742 gimple_find_edge_insert_loc (edge e, gimple_stmt_iterator *gsi,
 743                              basic_block *new_bb)
 744 {
 745   basic_block dest, src;
 746   gimple tmp;
 747
 748   dest = e->dest;
 749
 750   /* If the destination has one predecessor which has no PHI nodes,
 751      insert there.  Except for the exit block.
 752
 753      The requirement for no PHI nodes could be relaxed.  Basically we
 754      would have to examine the PHIs to prove that none of them used
 755      the value set by the statement we want to insert on E.  That
 756      hardly seems worth the effort.  */
 757  restart:
 758   if (single_pred_p (dest)
 759       && gimple_seq_empty_p (phi_nodes (dest))
 760       && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
 761     {
 762       *gsi = gsi_start_bb (dest);
 763       if (gsi_end_p (*gsi))
 764         return true;
 765
 766       /* Make sure we insert after any leading labels.  */
 767       tmp = gsi_stmt (*gsi);
 768       while (gimple_code (tmp) == GIMPLE_LABEL)
 769         {
 770           gsi_next (gsi);
 771           if (gsi_end_p (*gsi))
 772             break;
 773           tmp = gsi_stmt (*gsi);
 774         }
 775
 776       if (gsi_end_p (*gsi))
 777         {
 778           *gsi = gsi_last_bb (dest);
 779           return true;
 780         }
 781       else
 782         return false;
 783     }
 784
 785   /* If the source has one successor, the edge is not abnormal and
 786      the last statement does not end a basic block, insert there.
 787      Except for the entry block.  */
 788   src = e->src;
 789   if ((e->flags & EDGE_ABNORMAL) == 0
 790       && single_succ_p (src)
 791       && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
 792     {
 793       *gsi = gsi_last_bb (src);
 794       if (gsi_end_p (*gsi))
 795         return true;
 796
 797       tmp = gsi_stmt (*gsi);
 798       if (!stmt_ends_bb_p (tmp))
 799         return true;
 800
 801       switch (gimple_code (tmp))
 802         {
 803         case GIMPLE_RETURN:
 804         case GIMPLE_RESX:
 805           return false;
 806         default:
 807           break;
 808         }
 809     }
 810
 811   /* Otherwise, create a new basic block, and split this edge.  */
 812   dest = split_edge (e);
 813   if (new_bb)
 814     *new_bb = dest;
 815   e = single_pred_edge (dest);
 816   goto restart;
 817 }
 818
 819
 820 /* Similar to gsi_insert_on_edge+gsi_commit_edge_inserts.  If a new
 821    block has to be created, it is returned.  */
 822
 823 basic_block
 824 gsi_insert_on_edge_immediate (edge e, gimple stmt)
 825 {
 826   gimple_stmt_iterator gsi;
 827   basic_block new_bb = NULL;
 828   bool ins_after;
 829
 830   gcc_assert (!PENDING_STMT (e));
 831
 832   ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
 833
 834   update_call_edge_frequencies (stmt, gsi.bb);
 835
 836   if (ins_after)
 837     gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
 838   else
 839     gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
 840
 841   return new_bb;
 842 }
 843
 844 /* Insert STMTS on edge E.  If a new block has to be created, it
 845    is returned.  */
 846
 847 basic_block
 848 gsi_insert_seq_on_edge_immediate (edge e, gimple_seq stmts)
 849 {
 850   gimple_stmt_iterator gsi;
 851   basic_block new_bb = NULL;
 852   bool ins_after;
 853
 854   gcc_assert (!PENDING_STMT (e));
 855
 856   ins_after = gimple_find_edge_insert_loc (e, &gsi, &new_bb);
 857   update_call_edge_frequencies (gimple_seq_first (stmts), gsi.bb);
 858
 859   if (ins_after)
 860     gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
 861   else
 862     gsi_insert_seq_before (&gsi, stmts, GSI_NEW_STMT);
 863
 864   return new_bb;
 865 }
 866
 867 /* This routine will commit all pending edge insertions, creating any new
 868    basic blocks which are necessary.  */
 869
 870 void
 871 gsi_commit_edge_inserts (void)
 872 {
 873   basic_block bb;
 874   edge e;
 875   edge_iterator ei;
 876
 877   gsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)),
 878                               NULL);
 879
 880   FOR_EACH_BB_FN (bb, cfun)
 881     FOR_EACH_EDGE (e, ei, bb->succs)
 882       gsi_commit_one_edge_insert (e, NULL);
 883 }
 884
 885
 886 /* Commit insertions pending at edge E. If a new block is created, set NEW_BB
 887    to this block, otherwise set it to NULL.  */
 888
 889 void
 890 gsi_commit_one_edge_insert (edge e, basic_block *new_bb)
 891 {
 892   if (new_bb)
 893     *new_bb = NULL;
 894
 895   if (PENDING_STMT (e))
 896     {
 897       gimple_stmt_iterator gsi;
 898       gimple_seq seq = PENDING_STMT (e);
 899       bool ins_after;
 900
 901       PENDING_STMT (e) = NULL;
 902
 903       ins_after = gimple_find_edge_insert_loc (e, &gsi, new_bb);
 904       update_call_edge_frequencies (gimple_seq_first (seq), gsi.bb);
 905
 906       if (ins_after)
 907         gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
 908       else
 909         gsi_insert_seq_before (&gsi, seq, GSI_NEW_STMT);
 910     }
 911 }
 912
 913 /* Returns iterator at the start of the list of phi nodes of BB.  */
 914
 915 gphi_iterator
 916 gsi_start_phis (basic_block bb)
 917 {
 918   gimple_seq *pseq = phi_nodes_ptr (bb);
 919
 920   /* Adapted from gsi_start_1. */
 921   gphi_iterator i;
 922
 923   i.ptr = gimple_seq_first (*pseq);
 924   i.seq = pseq;
 925   i.bb = i.ptr ? gimple_bb (i.ptr) : NULL;
 926
 927   return i;
 928 }