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