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