gcc/gimple-iterator.c

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