gcc/gimple-iterator.c

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