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