gcc/cfganal.c

   1 /* Control flow graph analysis code for GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2010
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* This file contains various simple utilities to analyze the CFG.  */
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "rtl.h"
  28 #include "obstack.h"
  29 #include "hard-reg-set.h"
  30 #include "basic-block.h"
  31 #include "insn-config.h"
  32 #include "recog.h"
  33 #include "diagnostic-core.h"
  34 #include "tm_p.h"
  35 #include "vec.h"
  36 #include "vecprim.h"
  37 #include "bitmap.h"
  38 #include "sbitmap.h"
  39 #include "timevar.h"
  40 #include "cfgloop.h"
  41
  42 /* Store the data structures necessary for depth-first search.  */
  43 struct depth_first_search_dsS {
  44   /* stack for backtracking during the algorithm */
  45   basic_block *stack;
  46
  47   /* number of edges in the stack.  That is, positions 0, ..., sp-1
  48      have edges.  */
  49   unsigned int sp;
  50
  51   /* record of basic blocks already seen by depth-first search */
  52   sbitmap visited_blocks;
  53 };
  54 typedef struct depth_first_search_dsS *depth_first_search_ds;
  55
  56 static void flow_dfs_compute_reverse_init (depth_first_search_ds);
  57 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds,
  58                                              basic_block);
  59 static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds,
  60                                                      basic_block);
  61 static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
  62 static bool flow_active_insn_p (const_rtx);
  63 \f
  64 /* Like active_insn_p, except keep the return value clobber around
  65    even after reload.  */
  66
  67 static bool
  68 flow_active_insn_p (const_rtx insn)
  69 {
  70   if (active_insn_p (insn))
  71     return true;
  72
  73   /* A clobber of the function return value exists for buggy
  74      programs that fail to return a value.  Its effect is to
  75      keep the return value from being live across the entire
  76      function.  If we allow it to be skipped, we introduce the
  77      possibility for register lifetime confusion.  */
  78   if (GET_CODE (PATTERN (insn)) == CLOBBER
  79       && REG_P (XEXP (PATTERN (insn), 0))
  80       && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
  81     return true;
  82
  83   return false;
  84 }
  85
  86 /* Return true if the block has no effect and only forwards control flow to
  87    its single destination.  */
  88
  89 bool
  90 forwarder_block_p (const_basic_block bb)
  91 {
  92   rtx insn;
  93
  94   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
  95       || !single_succ_p (bb))
  96     return false;
  97
  98   /* Protect loop latches, headers and preheaders.  */
  99   if (current_loops)
 100     {
 101       basic_block dest;
 102       if (bb->loop_father->header == bb)
 103         return false;
 104       dest = EDGE_SUCC (bb, 0)->dest;
 105       if (dest->loop_father->header == dest)
 106         return false;
 107     }
 108
 109   for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
 110     if (INSN_P (insn) && flow_active_insn_p (insn))
 111       return false;
 112
 113   return (!INSN_P (insn)
 114           || (JUMP_P (insn) && simplejump_p (insn))
 115           || !flow_active_insn_p (insn));
 116 }
 117
 118 /* Return nonzero if we can reach target from src by falling through.  */
 119
 120 bool
 121 can_fallthru (basic_block src, basic_block target)
 122 {
 123   rtx insn = BB_END (src);
 124   rtx insn2;
 125   edge e;
 126   edge_iterator ei;
 127
 128   if (target == EXIT_BLOCK_PTR)
 129     return true;
 130   if (src->next_bb != target)
 131     return 0;
 132   FOR_EACH_EDGE (e, ei, src->succs)
 133     if (e->dest == EXIT_BLOCK_PTR
 134         && e->flags & EDGE_FALLTHRU)
 135       return 0;
 136
 137   insn2 = BB_HEAD (target);
 138   if (insn2 && !active_insn_p (insn2))
 139     insn2 = next_active_insn (insn2);
 140
 141   /* ??? Later we may add code to move jump tables offline.  */
 142   return next_active_insn (insn) == insn2;
 143 }
 144
 145 /* Return nonzero if we could reach target from src by falling through,
 146    if the target was made adjacent.  If we already have a fall-through
 147    edge to the exit block, we can't do that.  */
 148 bool
 149 could_fall_through (basic_block src, basic_block target)
 150 {
 151   edge e;
 152   edge_iterator ei;
 153
 154   if (target == EXIT_BLOCK_PTR)
 155     return true;
 156   FOR_EACH_EDGE (e, ei, src->succs)
 157     if (e->dest == EXIT_BLOCK_PTR
 158         && e->flags & EDGE_FALLTHRU)
 159       return 0;
 160   return true;
 161 }
 162 \f
 163 /* Mark the back edges in DFS traversal.
 164    Return nonzero if a loop (natural or otherwise) is present.
 165    Inspired by Depth_First_Search_PP described in:
 166
 167      Advanced Compiler Design and Implementation
 168      Steven Muchnick
 169      Morgan Kaufmann, 1997
 170
 171    and heavily borrowed from pre_and_rev_post_order_compute.  */
 172
 173 bool
 174 mark_dfs_back_edges (void)
 175 {
 176   edge_iterator *stack;
 177   int *pre;
 178   int *post;
 179   int sp;
 180   int prenum = 1;
 181   int postnum = 1;
 182   sbitmap visited;
 183   bool found = false;
 184
 185   /* Allocate the preorder and postorder number arrays.  */
 186   pre = XCNEWVEC (int, last_basic_block);
 187   post = XCNEWVEC (int, last_basic_block);
 188
 189   /* Allocate stack for back-tracking up CFG.  */
 190   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 191   sp = 0;
 192
 193   /* Allocate bitmap to track nodes that have been visited.  */
 194   visited = sbitmap_alloc (last_basic_block);
 195
 196   /* None of the nodes in the CFG have been visited yet.  */
 197   sbitmap_zero (visited);
 198
 199   /* Push the first edge on to the stack.  */
 200   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 201
 202   while (sp)
 203     {
 204       edge_iterator ei;
 205       basic_block src;
 206       basic_block dest;
 207
 208       /* Look at the edge on the top of the stack.  */
 209       ei = stack[sp - 1];
 210       src = ei_edge (ei)->src;
 211       dest = ei_edge (ei)->dest;
 212       ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
 213
 214       /* Check if the edge destination has been visited yet.  */
 215       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 216         {
 217           /* Mark that we have visited the destination.  */
 218           SET_BIT (visited, dest->index);
 219
 220           pre[dest->index] = prenum++;
 221           if (EDGE_COUNT (dest->succs) > 0)
 222             {
 223               /* Since the DEST node has been visited for the first
 224                  time, check its successors.  */
 225               stack[sp++] = ei_start (dest->succs);
 226             }
 227           else
 228             post[dest->index] = postnum++;
 229         }
 230       else
 231         {
 232           if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
 233               && pre[src->index] >= pre[dest->index]
 234               && post[dest->index] == 0)
 235             ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
 236
 237           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
 238             post[src->index] = postnum++;
 239
 240           if (!ei_one_before_end_p (ei))
 241             ei_next (&stack[sp - 1]);
 242           else
 243             sp--;
 244         }
 245     }
 246
 247   free (pre);
 248   free (post);
 249   free (stack);
 250   sbitmap_free (visited);
 251
 252   return found;
 253 }
 254
 255 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru.  */
 256
 257 void
 258 set_edge_can_fallthru_flag (void)
 259 {
 260   basic_block bb;
 261
 262   FOR_EACH_BB (bb)
 263     {
 264       edge e;
 265       edge_iterator ei;
 266
 267       FOR_EACH_EDGE (e, ei, bb->succs)
 268         {
 269           e->flags &= ~EDGE_CAN_FALLTHRU;
 270
 271           /* The FALLTHRU edge is also CAN_FALLTHRU edge.  */
 272           if (e->flags & EDGE_FALLTHRU)
 273             e->flags |= EDGE_CAN_FALLTHRU;
 274         }
 275
 276       /* If the BB ends with an invertible condjump all (2) edges are
 277          CAN_FALLTHRU edges.  */
 278       if (EDGE_COUNT (bb->succs) != 2)
 279         continue;
 280       if (!any_condjump_p (BB_END (bb)))
 281         continue;
 282       if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
 283         continue;
 284       invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0);
 285       EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
 286       EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
 287     }
 288 }
 289
 290 /* Find unreachable blocks.  An unreachable block will have 0 in
 291    the reachable bit in block->flags.  A nonzero value indicates the
 292    block is reachable.  */
 293
 294 void
 295 find_unreachable_blocks (void)
 296 {
 297   edge e;
 298   edge_iterator ei;
 299   basic_block *tos, *worklist, bb;
 300
 301   tos = worklist = XNEWVEC (basic_block, n_basic_blocks);
 302
 303   /* Clear all the reachability flags.  */
 304
 305   FOR_EACH_BB (bb)
 306     bb->flags &= ~BB_REACHABLE;
 307
 308   /* Add our starting points to the worklist.  Almost always there will
 309      be only one.  It isn't inconceivable that we might one day directly
 310      support Fortran alternate entry points.  */
 311
 312   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 313     {
 314       *tos++ = e->dest;
 315
 316       /* Mark the block reachable.  */
 317       e->dest->flags |= BB_REACHABLE;
 318     }
 319
 320   /* Iterate: find everything reachable from what we've already seen.  */
 321
 322   while (tos != worklist)
 323     {
 324       basic_block b = *--tos;
 325
 326       FOR_EACH_EDGE (e, ei, b->succs)
 327         {
 328           basic_block dest = e->dest;
 329
 330           if (!(dest->flags & BB_REACHABLE))
 331             {
 332               *tos++ = dest;
 333               dest->flags |= BB_REACHABLE;
 334             }
 335         }
 336     }
 337
 338   free (worklist);
 339 }
 340 \f
 341 /* Functions to access an edge list with a vector representation.
 342    Enough data is kept such that given an index number, the
 343    pred and succ that edge represents can be determined, or
 344    given a pred and a succ, its index number can be returned.
 345    This allows algorithms which consume a lot of memory to
 346    represent the normally full matrix of edge (pred,succ) with a
 347    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
 348    wasted space in the client code due to sparse flow graphs.  */
 349
 350 /* This functions initializes the edge list. Basically the entire
 351    flowgraph is processed, and all edges are assigned a number,
 352    and the data structure is filled in.  */
 353
 354 struct edge_list *
 355 create_edge_list (void)
 356 {
 357   struct edge_list *elist;
 358   edge e;
 359   int num_edges;
 360   int block_count;
 361   basic_block bb;
 362   edge_iterator ei;
 363
 364   block_count = n_basic_blocks; /* Include the entry and exit blocks.  */
 365
 366   num_edges = 0;
 367
 368   /* Determine the number of edges in the flow graph by counting successor
 369      edges on each basic block.  */
 370   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 371     {
 372       num_edges += EDGE_COUNT (bb->succs);
 373     }
 374
 375   elist = XNEW (struct edge_list);
 376   elist->num_blocks = block_count;
 377   elist->num_edges = num_edges;
 378   elist->index_to_edge = XNEWVEC (edge, num_edges);
 379
 380   num_edges = 0;
 381
 382   /* Follow successors of blocks, and register these edges.  */
 383   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 384     FOR_EACH_EDGE (e, ei, bb->succs)
 385       elist->index_to_edge[num_edges++] = e;
 386
 387   return elist;
 388 }
 389
 390 /* This function free's memory associated with an edge list.  */
 391
 392 void
 393 free_edge_list (struct edge_list *elist)
 394 {
 395   if (elist)
 396     {
 397       free (elist->index_to_edge);
 398       free (elist);
 399     }
 400 }
 401
 402 /* This function provides debug output showing an edge list.  */
 403
 404 DEBUG_FUNCTION void
 405 print_edge_list (FILE *f, struct edge_list *elist)
 406 {
 407   int x;
 408
 409   fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
 410            elist->num_blocks, elist->num_edges);
 411
 412   for (x = 0; x < elist->num_edges; x++)
 413     {
 414       fprintf (f, " %-4d - edge(", x);
 415       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
 416         fprintf (f, "entry,");
 417       else
 418         fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
 419
 420       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
 421         fprintf (f, "exit)\n");
 422       else
 423         fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
 424     }
 425 }
 426
 427 /* This function provides an internal consistency check of an edge list,
 428    verifying that all edges are present, and that there are no
 429    extra edges.  */
 430
 431 DEBUG_FUNCTION void
 432 verify_edge_list (FILE *f, struct edge_list *elist)
 433 {
 434   int pred, succ, index;
 435   edge e;
 436   basic_block bb, p, s;
 437   edge_iterator ei;
 438
 439   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 440     {
 441       FOR_EACH_EDGE (e, ei, bb->succs)
 442         {
 443           pred = e->src->index;
 444           succ = e->dest->index;
 445           index = EDGE_INDEX (elist, e->src, e->dest);
 446           if (index == EDGE_INDEX_NO_EDGE)
 447             {
 448               fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
 449               continue;
 450             }
 451
 452           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
 453             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
 454                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
 455           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
 456             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
 457                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
 458         }
 459     }
 460
 461   /* We've verified that all the edges are in the list, now lets make sure
 462      there are no spurious edges in the list.  */
 463
 464   FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 465     FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 466       {
 467         int found_edge = 0;
 468
 469         FOR_EACH_EDGE (e, ei, p->succs)
 470           if (e->dest == s)
 471             {
 472               found_edge = 1;
 473               break;
 474             }
 475
 476         FOR_EACH_EDGE (e, ei, s->preds)
 477           if (e->src == p)
 478             {
 479               found_edge = 1;
 480               break;
 481             }
 482
 483         if (EDGE_INDEX (elist, p, s)
 484             == EDGE_INDEX_NO_EDGE && found_edge != 0)
 485           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
 486                    p->index, s->index);
 487         if (EDGE_INDEX (elist, p, s)
 488             != EDGE_INDEX_NO_EDGE && found_edge == 0)
 489           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
 490                    p->index, s->index, EDGE_INDEX (elist, p, s));
 491       }
 492 }
 493
 494 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
 495    If no such edge exists, return NULL.  */
 496
 497 edge
 498 find_edge (basic_block pred, basic_block succ)
 499 {
 500   edge e;
 501   edge_iterator ei;
 502
 503   if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
 504     {
 505       FOR_EACH_EDGE (e, ei, pred->succs)
 506         if (e->dest == succ)
 507           return e;
 508     }
 509   else
 510     {
 511       FOR_EACH_EDGE (e, ei, succ->preds)
 512         if (e->src == pred)
 513           return e;
 514     }
 515
 516   return NULL;
 517 }
 518
 519 /* This routine will determine what, if any, edge there is between
 520    a specified predecessor and successor.  */
 521
 522 int
 523 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
 524 {
 525   int x;
 526
 527   for (x = 0; x < NUM_EDGES (edge_list); x++)
 528     if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
 529         && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
 530       return x;
 531
 532   return (EDGE_INDEX_NO_EDGE);
 533 }
 534
 535 /* Dump the list of basic blocks in the bitmap NODES.  */
 536
 537 void
 538 flow_nodes_print (const char *str, const_sbitmap nodes, FILE *file)
 539 {
 540   unsigned int node = 0;
 541   sbitmap_iterator sbi;
 542
 543   if (! nodes)
 544     return;
 545
 546   fprintf (file, "%s { ", str);
 547   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi)
 548     fprintf (file, "%d ", node);
 549   fputs ("}\n", file);
 550 }
 551
 552 /* Dump the list of edges in the array EDGE_LIST.  */
 553
 554 void
 555 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
 556 {
 557   int i;
 558
 559   if (! edge_list)
 560     return;
 561
 562   fprintf (file, "%s { ", str);
 563   for (i = 0; i < num_edges; i++)
 564     fprintf (file, "%d->%d ", edge_list[i]->src->index,
 565              edge_list[i]->dest->index);
 566
 567   fputs ("}\n", file);
 568 }
 569
 570 \f
 571 /* This routine will remove any fake predecessor edges for a basic block.
 572    When the edge is removed, it is also removed from whatever successor
 573    list it is in.  */
 574
 575 static void
 576 remove_fake_predecessors (basic_block bb)
 577 {
 578   edge e;
 579   edge_iterator ei;
 580
 581   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 582     {
 583       if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
 584         remove_edge (e);
 585       else
 586         ei_next (&ei);
 587     }
 588 }
 589
 590 /* This routine will remove all fake edges from the flow graph.  If
 591    we remove all fake successors, it will automatically remove all
 592    fake predecessors.  */
 593
 594 void
 595 remove_fake_edges (void)
 596 {
 597   basic_block bb;
 598
 599   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 600     remove_fake_predecessors (bb);
 601 }
 602
 603 /* This routine will remove all fake edges to the EXIT_BLOCK.  */
 604
 605 void
 606 remove_fake_exit_edges (void)
 607 {
 608   remove_fake_predecessors (EXIT_BLOCK_PTR);
 609 }
 610
 611
 612 /* This function will add a fake edge between any block which has no
 613    successors, and the exit block. Some data flow equations require these
 614    edges to exist.  */
 615
 616 void
 617 add_noreturn_fake_exit_edges (void)
 618 {
 619   basic_block bb;
 620
 621   FOR_EACH_BB (bb)
 622     if (EDGE_COUNT (bb->succs) == 0)
 623       make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 624 }
 625
 626 /* This function adds a fake edge between any infinite loops to the
 627    exit block.  Some optimizations require a path from each node to
 628    the exit node.
 629
 630    See also Morgan, Figure 3.10, pp. 82-83.
 631
 632    The current implementation is ugly, not attempting to minimize the
 633    number of inserted fake edges.  To reduce the number of fake edges
 634    to insert, add fake edges from _innermost_ loops containing only
 635    nodes not reachable from the exit block.  */
 636
 637 void
 638 connect_infinite_loops_to_exit (void)
 639 {
 640   basic_block unvisited_block = EXIT_BLOCK_PTR;
 641   struct depth_first_search_dsS dfs_ds;
 642
 643   /* Perform depth-first search in the reverse graph to find nodes
 644      reachable from the exit block.  */
 645   flow_dfs_compute_reverse_init (&dfs_ds);
 646   flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
 647
 648   /* Repeatedly add fake edges, updating the unreachable nodes.  */
 649   while (1)
 650     {
 651       unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
 652                                                           unvisited_block);
 653       if (!unvisited_block)
 654         break;
 655
 656       make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
 657       flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
 658     }
 659
 660   flow_dfs_compute_reverse_finish (&dfs_ds);
 661   return;
 662 }
 663 \f
 664 /* Compute reverse top sort order.  This is computing a post order
 665    numbering of the graph.  If INCLUDE_ENTRY_EXIT is true, then
 666    ENTRY_BLOCK and EXIT_BLOCK are included.  If DELETE_UNREACHABLE is
 667    true, unreachable blocks are deleted.  */
 668
 669 int
 670 post_order_compute (int *post_order, bool include_entry_exit,
 671                     bool delete_unreachable)
 672 {
 673   edge_iterator *stack;
 674   int sp;
 675   int post_order_num = 0;
 676   sbitmap visited;
 677   int count;
 678
 679   if (include_entry_exit)
 680     post_order[post_order_num++] = EXIT_BLOCK;
 681
 682   /* Allocate stack for back-tracking up CFG.  */
 683   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 684   sp = 0;
 685
 686   /* Allocate bitmap to track nodes that have been visited.  */
 687   visited = sbitmap_alloc (last_basic_block);
 688
 689   /* None of the nodes in the CFG have been visited yet.  */
 690   sbitmap_zero (visited);
 691
 692   /* Push the first edge on to the stack.  */
 693   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 694
 695   while (sp)
 696     {
 697       edge_iterator ei;
 698       basic_block src;
 699       basic_block dest;
 700
 701       /* Look at the edge on the top of the stack.  */
 702       ei = stack[sp - 1];
 703       src = ei_edge (ei)->src;
 704       dest = ei_edge (ei)->dest;
 705
 706       /* Check if the edge destination has been visited yet.  */
 707       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 708         {
 709           /* Mark that we have visited the destination.  */
 710           SET_BIT (visited, dest->index);
 711
 712           if (EDGE_COUNT (dest->succs) > 0)
 713             /* Since the DEST node has been visited for the first
 714                time, check its successors.  */
 715             stack[sp++] = ei_start (dest->succs);
 716           else
 717             post_order[post_order_num++] = dest->index;
 718         }
 719       else
 720         {
 721           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
 722             post_order[post_order_num++] = src->index;
 723
 724           if (!ei_one_before_end_p (ei))
 725             ei_next (&stack[sp - 1]);
 726           else
 727             sp--;
 728         }
 729     }
 730
 731   if (include_entry_exit)
 732     {
 733       post_order[post_order_num++] = ENTRY_BLOCK;
 734       count = post_order_num;
 735     }
 736   else
 737     count = post_order_num + 2;
 738
 739   /* Delete the unreachable blocks if some were found and we are
 740      supposed to do it.  */
 741   if (delete_unreachable && (count != n_basic_blocks))
 742     {
 743       basic_block b;
 744       basic_block next_bb;
 745       for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
 746         {
 747           next_bb = b->next_bb;
 748
 749           if (!(TEST_BIT (visited, b->index)))
 750             delete_basic_block (b);
 751         }
 752
 753       tidy_fallthru_edges ();
 754     }
 755
 756   free (stack);
 757   sbitmap_free (visited);
 758   return post_order_num;
 759 }
 760
 761
 762 /* Helper routine for inverted_post_order_compute.
 763    BB has to belong to a region of CFG
 764    unreachable by inverted traversal from the exit.
 765    i.e. there's no control flow path from ENTRY to EXIT
 766    that contains this BB.
 767    This can happen in two cases - if there's an infinite loop
 768    or if there's a block that has no successor
 769    (call to a function with no return).
 770    Some RTL passes deal with this condition by
 771    calling connect_infinite_loops_to_exit () and/or
 772    add_noreturn_fake_exit_edges ().
 773    However, those methods involve modifying the CFG itself
 774    which may not be desirable.
 775    Hence, we deal with the infinite loop/no return cases
 776    by identifying a unique basic block that can reach all blocks
 777    in such a region by inverted traversal.
 778    This function returns a basic block that guarantees
 779    that all blocks in the region are reachable
 780    by starting an inverted traversal from the returned block.  */
 781
 782 static basic_block
 783 dfs_find_deadend (basic_block bb)
 784 {
 785   sbitmap visited = sbitmap_alloc (last_basic_block);
 786   sbitmap_zero (visited);
 787
 788   for (;;)
 789     {
 790       SET_BIT (visited, bb->index);
 791       if (EDGE_COUNT (bb->succs) == 0
 792           || TEST_BIT (visited, EDGE_SUCC (bb, 0)->dest->index))
 793         {
 794           sbitmap_free (visited);
 795           return bb;
 796         }
 797
 798       bb = EDGE_SUCC (bb, 0)->dest;
 799     }
 800
 801   gcc_unreachable ();
 802 }
 803
 804
 805 /* Compute the reverse top sort order of the inverted CFG
 806    i.e. starting from the exit block and following the edges backward
 807    (from successors to predecessors).
 808    This ordering can be used for forward dataflow problems among others.
 809
 810    This function assumes that all blocks in the CFG are reachable
 811    from the ENTRY (but not necessarily from EXIT).
 812
 813    If there's an infinite loop,
 814    a simple inverted traversal starting from the blocks
 815    with no successors can't visit all blocks.
 816    To solve this problem, we first do inverted traversal
 817    starting from the blocks with no successor.
 818    And if there's any block left that's not visited by the regular
 819    inverted traversal from EXIT,
 820    those blocks are in such problematic region.
 821    Among those, we find one block that has
 822    any visited predecessor (which is an entry into such a region),
 823    and start looking for a "dead end" from that block
 824    and do another inverted traversal from that block.  */
 825
 826 int
 827 inverted_post_order_compute (int *post_order)
 828 {
 829   basic_block bb;
 830   edge_iterator *stack;
 831   int sp;
 832   int post_order_num = 0;
 833   sbitmap visited;
 834
 835   /* Allocate stack for back-tracking up CFG.  */
 836   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 837   sp = 0;
 838
 839   /* Allocate bitmap to track nodes that have been visited.  */
 840   visited = sbitmap_alloc (last_basic_block);
 841
 842   /* None of the nodes in the CFG have been visited yet.  */
 843   sbitmap_zero (visited);
 844
 845   /* Put all blocks that have no successor into the initial work list.  */
 846   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 847     if (EDGE_COUNT (bb->succs) == 0)
 848       {
 849         /* Push the initial edge on to the stack.  */
 850         if (EDGE_COUNT (bb->preds) > 0)
 851           {
 852             stack[sp++] = ei_start (bb->preds);
 853             SET_BIT (visited, bb->index);
 854           }
 855       }
 856
 857   do
 858     {
 859       bool has_unvisited_bb = false;
 860
 861       /* The inverted traversal loop. */
 862       while (sp)
 863         {
 864           edge_iterator ei;
 865           basic_block pred;
 866
 867           /* Look at the edge on the top of the stack.  */
 868           ei = stack[sp - 1];
 869           bb = ei_edge (ei)->dest;
 870           pred = ei_edge (ei)->src;
 871
 872           /* Check if the predecessor has been visited yet.  */
 873           if (! TEST_BIT (visited, pred->index))
 874             {
 875               /* Mark that we have visited the destination.  */
 876               SET_BIT (visited, pred->index);
 877
 878               if (EDGE_COUNT (pred->preds) > 0)
 879                 /* Since the predecessor node has been visited for the first
 880                    time, check its predecessors.  */
 881                 stack[sp++] = ei_start (pred->preds);
 882               else
 883                 post_order[post_order_num++] = pred->index;
 884             }
 885           else
 886             {
 887               if (bb != EXIT_BLOCK_PTR && ei_one_before_end_p (ei))
 888                 post_order[post_order_num++] = bb->index;
 889
 890               if (!ei_one_before_end_p (ei))
 891                 ei_next (&stack[sp - 1]);
 892               else
 893                 sp--;
 894             }
 895         }
 896
 897       /* Detect any infinite loop and activate the kludge.
 898          Note that this doesn't check EXIT_BLOCK itself
 899          since EXIT_BLOCK is always added after the outer do-while loop.  */
 900       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 901         if (!TEST_BIT (visited, bb->index))
 902           {
 903             has_unvisited_bb = true;
 904
 905             if (EDGE_COUNT (bb->preds) > 0)
 906               {
 907                 edge_iterator ei;
 908                 edge e;
 909                 basic_block visited_pred = NULL;
 910
 911                 /* Find an already visited predecessor.  */
 912                 FOR_EACH_EDGE (e, ei, bb->preds)
 913                   {
 914                     if (TEST_BIT (visited, e->src->index))
 915                       visited_pred = e->src;
 916                   }
 917
 918                 if (visited_pred)
 919                   {
 920                     basic_block be = dfs_find_deadend (bb);
 921                     gcc_assert (be != NULL);
 922                     SET_BIT (visited, be->index);
 923                     stack[sp++] = ei_start (be->preds);
 924                     break;
 925                   }
 926               }
 927           }
 928
 929       if (has_unvisited_bb && sp == 0)
 930         {
 931           /* No blocks are reachable from EXIT at all.
 932              Find a dead-end from the ENTRY, and restart the iteration. */
 933           basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR);
 934           gcc_assert (be != NULL);
 935           SET_BIT (visited, be->index);
 936           stack[sp++] = ei_start (be->preds);
 937         }
 938
 939       /* The only case the below while fires is
 940          when there's an infinite loop.  */
 941     }
 942   while (sp);
 943
 944   /* EXIT_BLOCK is always included.  */
 945   post_order[post_order_num++] = EXIT_BLOCK;
 946
 947   free (stack);
 948   sbitmap_free (visited);
 949   return post_order_num;
 950 }
 951
 952 /* Compute the depth first search order and store in the array
 953   PRE_ORDER if nonzero, marking the nodes visited in VISITED.  If
 954   REV_POST_ORDER is nonzero, return the reverse completion number for each
 955   node.  Returns the number of nodes visited.  A depth first search
 956   tries to get as far away from the starting point as quickly as
 957   possible.
 958
 959   pre_order is a really a preorder numbering of the graph.
 960   rev_post_order is really a reverse postorder numbering of the graph.
 961  */
 962
 963 int
 964 pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
 965                                 bool include_entry_exit)
 966 {
 967   edge_iterator *stack;
 968   int sp;
 969   int pre_order_num = 0;
 970   int rev_post_order_num = n_basic_blocks - 1;
 971   sbitmap visited;
 972
 973   /* Allocate stack for back-tracking up CFG.  */
 974   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 975   sp = 0;
 976
 977   if (include_entry_exit)
 978     {
 979       if (pre_order)
 980         pre_order[pre_order_num] = ENTRY_BLOCK;
 981       pre_order_num++;
 982       if (rev_post_order)
 983         rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
 984     }
 985   else
 986     rev_post_order_num -= NUM_FIXED_BLOCKS;
 987
 988   /* Allocate bitmap to track nodes that have been visited.  */
 989   visited = sbitmap_alloc (last_basic_block);
 990
 991   /* None of the nodes in the CFG have been visited yet.  */
 992   sbitmap_zero (visited);
 993
 994   /* Push the first edge on to the stack.  */
 995   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 996
 997   while (sp)
 998     {
 999       edge_iterator ei;
1000       basic_block src;
1001       basic_block dest;
1002
1003       /* Look at the edge on the top of the stack.  */
1004       ei = stack[sp - 1];
1005       src = ei_edge (ei)->src;
1006       dest = ei_edge (ei)->dest;
1007
1008       /* Check if the edge destination has been visited yet.  */
1009       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
1010         {
1011           /* Mark that we have visited the destination.  */
1012           SET_BIT (visited, dest->index);
1013
1014           if (pre_order)
1015             pre_order[pre_order_num] = dest->index;
1016
1017           pre_order_num++;
1018
1019           if (EDGE_COUNT (dest->succs) > 0)
1020             /* Since the DEST node has been visited for the first
1021                time, check its successors.  */
1022             stack[sp++] = ei_start (dest->succs);
1023           else if (rev_post_order)
1024             /* There are no successors for the DEST node so assign
1025                its reverse completion number.  */
1026             rev_post_order[rev_post_order_num--] = dest->index;
1027         }
1028       else
1029         {
1030           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
1031               && rev_post_order)
1032             /* There are no more successors for the SRC node
1033                so assign its reverse completion number.  */
1034             rev_post_order[rev_post_order_num--] = src->index;
1035
1036           if (!ei_one_before_end_p (ei))
1037             ei_next (&stack[sp - 1]);
1038           else
1039             sp--;
1040         }
1041     }
1042
1043   free (stack);
1044   sbitmap_free (visited);
1045
1046   if (include_entry_exit)
1047     {
1048       if (pre_order)
1049         pre_order[pre_order_num] = EXIT_BLOCK;
1050       pre_order_num++;
1051       if (rev_post_order)
1052         rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
1053       /* The number of nodes visited should be the number of blocks.  */
1054       gcc_assert (pre_order_num == n_basic_blocks);
1055     }
1056   else
1057     /* The number of nodes visited should be the number of blocks minus
1058        the entry and exit blocks which are not visited here.  */
1059     gcc_assert (pre_order_num == n_basic_blocks - NUM_FIXED_BLOCKS);
1060
1061   return pre_order_num;
1062 }
1063
1064 /* Compute the depth first search order on the _reverse_ graph and
1065    store in the array DFS_ORDER, marking the nodes visited in VISITED.
1066    Returns the number of nodes visited.
1067
1068    The computation is split into three pieces:
1069
1070    flow_dfs_compute_reverse_init () creates the necessary data
1071    structures.
1072
1073    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1074    structures.  The block will start the search.
1075
1076    flow_dfs_compute_reverse_execute () continues (or starts) the
1077    search using the block on the top of the stack, stopping when the
1078    stack is empty.
1079
1080    flow_dfs_compute_reverse_finish () destroys the necessary data
1081    structures.
1082
1083    Thus, the user will probably call ..._init(), call ..._add_bb() to
1084    add a beginning basic block to the stack, call ..._execute(),
1085    possibly add another bb to the stack and again call ..._execute(),
1086    ..., and finally call _finish().  */
1087
1088 /* Initialize the data structures used for depth-first search on the
1089    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
1090    added to the basic block stack.  DATA is the current depth-first
1091    search context.  If INITIALIZE_STACK is nonzero, there is an
1092    element on the stack.  */
1093
1094 static void
1095 flow_dfs_compute_reverse_init (depth_first_search_ds data)
1096 {
1097   /* Allocate stack for back-tracking up CFG.  */
1098   data->stack = XNEWVEC (basic_block, n_basic_blocks);
1099   data->sp = 0;
1100
1101   /* Allocate bitmap to track nodes that have been visited.  */
1102   data->visited_blocks = sbitmap_alloc (last_basic_block);
1103
1104   /* None of the nodes in the CFG have been visited yet.  */
1105   sbitmap_zero (data->visited_blocks);
1106
1107   return;
1108 }
1109
1110 /* Add the specified basic block to the top of the dfs data
1111    structures.  When the search continues, it will start at the
1112    block.  */
1113
1114 static void
1115 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
1116 {
1117   data->stack[data->sp++] = bb;
1118   SET_BIT (data->visited_blocks, bb->index);
1119 }
1120
1121 /* Continue the depth-first search through the reverse graph starting with the
1122    block at the stack's top and ending when the stack is empty.  Visited nodes
1123    are marked.  Returns an unvisited basic block, or NULL if there is none
1124    available.  */
1125
1126 static basic_block
1127 flow_dfs_compute_reverse_execute (depth_first_search_ds data,
1128                                   basic_block last_unvisited)
1129 {
1130   basic_block bb;
1131   edge e;
1132   edge_iterator ei;
1133
1134   while (data->sp > 0)
1135     {
1136       bb = data->stack[--data->sp];
1137
1138       /* Perform depth-first search on adjacent vertices.  */
1139       FOR_EACH_EDGE (e, ei, bb->preds)
1140         if (!TEST_BIT (data->visited_blocks, e->src->index))
1141           flow_dfs_compute_reverse_add_bb (data, e->src);
1142     }
1143
1144   /* Determine if there are unvisited basic blocks.  */
1145   FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
1146     if (!TEST_BIT (data->visited_blocks, bb->index))
1147       return bb;
1148
1149   return NULL;
1150 }
1151
1152 /* Destroy the data structures needed for depth-first search on the
1153    reverse graph.  */
1154
1155 static void
1156 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
1157 {
1158   free (data->stack);
1159   sbitmap_free (data->visited_blocks);
1160 }
1161
1162 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1163    if REVERSE, go against direction of edges.  Returns number of blocks
1164    found and their list in RSLT.  RSLT can contain at most RSLT_MAX items.  */
1165 int
1166 dfs_enumerate_from (basic_block bb, int reverse,
1167                     bool (*predicate) (const_basic_block, const void *),
1168                     basic_block *rslt, int rslt_max, const void *data)
1169 {
1170   basic_block *st, lbb;
1171   int sp = 0, tv = 0;
1172   unsigned size;
1173
1174   /* A bitmap to keep track of visited blocks.  Allocating it each time
1175      this function is called is not possible, since dfs_enumerate_from
1176      is often used on small (almost) disjoint parts of cfg (bodies of
1177      loops), and allocating a large sbitmap would lead to quadratic
1178      behavior.  */
1179   static sbitmap visited;
1180   static unsigned v_size;
1181
1182 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
1183 #define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index))
1184 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
1185
1186   /* Resize the VISITED sbitmap if necessary.  */
1187   size = last_basic_block;
1188   if (size < 10)
1189     size = 10;
1190
1191   if (!visited)
1192     {
1193
1194       visited = sbitmap_alloc (size);
1195       sbitmap_zero (visited);
1196       v_size = size;
1197     }
1198   else if (v_size < size)
1199     {
1200       /* Ensure that we increase the size of the sbitmap exponentially.  */
1201       if (2 * v_size > size)
1202         size = 2 * v_size;
1203
1204       visited = sbitmap_resize (visited, size, 0);
1205       v_size = size;
1206     }
1207
1208   st = XCNEWVEC (basic_block, rslt_max);
1209   rslt[tv++] = st[sp++] = bb;
1210   MARK_VISITED (bb);
1211   while (sp)
1212     {
1213       edge e;
1214       edge_iterator ei;
1215       lbb = st[--sp];
1216       if (reverse)
1217         {
1218           FOR_EACH_EDGE (e, ei, lbb->preds)
1219             if (!VISITED_P (e->src) && predicate (e->src, data))
1220               {
1221                 gcc_assert (tv != rslt_max);
1222                 rslt[tv++] = st[sp++] = e->src;
1223                 MARK_VISITED (e->src);
1224               }
1225         }
1226       else
1227         {
1228           FOR_EACH_EDGE (e, ei, lbb->succs)
1229             if (!VISITED_P (e->dest) && predicate (e->dest, data))
1230               {
1231                 gcc_assert (tv != rslt_max);
1232                 rslt[tv++] = st[sp++] = e->dest;
1233                 MARK_VISITED (e->dest);
1234               }
1235         }
1236     }
1237   free (st);
1238   for (sp = 0; sp < tv; sp++)
1239     UNMARK_VISITED (rslt[sp]);
1240   return tv;
1241 #undef MARK_VISITED
1242 #undef UNMARK_VISITED
1243 #undef VISITED_P
1244 }
1245
1246
1247 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1248
1249    This algorithm can be found in Timothy Harvey's PhD thesis, at
1250    http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1251    dominance algorithms.
1252
1253    First, we identify each join point, j (any node with more than one
1254    incoming edge is a join point).
1255
1256    We then examine each predecessor, p, of j and walk up the dominator tree
1257    starting at p.
1258
1259    We stop the walk when we reach j's immediate dominator - j is in the
1260    dominance frontier of each of  the nodes in the walk, except for j's
1261    immediate dominator. Intuitively, all of the rest of j's dominators are
1262    shared by j's predecessors as well.
1263    Since they dominate j, they will not have j in their dominance frontiers.
1264
1265    The number of nodes touched by this algorithm is equal to the size
1266    of the dominance frontiers, no more, no less.
1267 */
1268
1269
1270 static void
1271 compute_dominance_frontiers_1 (bitmap_head *frontiers)
1272 {
1273   edge p;
1274   edge_iterator ei;
1275   basic_block b;
1276   FOR_EACH_BB (b)
1277     {
1278       if (EDGE_COUNT (b->preds) >= 2)
1279         {
1280           FOR_EACH_EDGE (p, ei, b->preds)
1281             {
1282               basic_block runner = p->src;
1283               basic_block domsb;
1284               if (runner == ENTRY_BLOCK_PTR)
1285                 continue;
1286
1287               domsb = get_immediate_dominator (CDI_DOMINATORS, b);
1288               while (runner != domsb)
1289                 {
1290                   if (!bitmap_set_bit (&frontiers[runner->index],
1291                                        b->index))
1292                     break;
1293                   runner = get_immediate_dominator (CDI_DOMINATORS,
1294                                                     runner);
1295                 }
1296             }
1297         }
1298     }
1299 }
1300
1301
1302 void
1303 compute_dominance_frontiers (bitmap_head *frontiers)
1304 {
1305   timevar_push (TV_DOM_FRONTIERS);
1306
1307   compute_dominance_frontiers_1 (frontiers);
1308
1309   timevar_pop (TV_DOM_FRONTIERS);
1310 }
1311
1312 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1313    return a bitmap with all the blocks in the iterated dominance
1314    frontier of the blocks in DEF_BLOCKS.  DFS contains dominance
1315    frontier information as returned by compute_dominance_frontiers.
1316
1317    The resulting set of blocks are the potential sites where PHI nodes
1318    are needed.  The caller is responsible for freeing the memory
1319    allocated for the return value.  */
1320
1321 bitmap
1322 compute_idf (bitmap def_blocks, bitmap_head *dfs)
1323 {
1324   bitmap_iterator bi;
1325   unsigned bb_index, i;
1326   VEC(int,heap) *work_stack;
1327   bitmap phi_insertion_points;
1328
1329   work_stack = VEC_alloc (int, heap, n_basic_blocks);
1330   phi_insertion_points = BITMAP_ALLOC (NULL);
1331
1332   /* Seed the work list with all the blocks in DEF_BLOCKS.  We use
1333      VEC_quick_push here for speed.  This is safe because we know that
1334      the number of definition blocks is no greater than the number of
1335      basic blocks, which is the initial capacity of WORK_STACK.  */
1336   EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
1337     VEC_quick_push (int, work_stack, bb_index);
1338
1339   /* Pop a block off the worklist, add every block that appears in
1340      the original block's DF that we have not already processed to
1341      the worklist.  Iterate until the worklist is empty.   Blocks
1342      which are added to the worklist are potential sites for
1343      PHI nodes.  */
1344   while (VEC_length (int, work_stack) > 0)
1345     {
1346       bb_index = VEC_pop (int, work_stack);
1347
1348       /* Since the registration of NEW -> OLD name mappings is done
1349          separately from the call to update_ssa, when updating the SSA
1350          form, the basic blocks where new and/or old names are defined
1351          may have disappeared by CFG cleanup calls.  In this case,
1352          we may pull a non-existing block from the work stack.  */
1353       gcc_assert (bb_index < (unsigned) last_basic_block);
1354
1355       EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points,
1356                                       0, i, bi)
1357         {
1358           /* Use a safe push because if there is a definition of VAR
1359              in every basic block, then WORK_STACK may eventually have
1360              more than N_BASIC_BLOCK entries.  */
1361           VEC_safe_push (int, heap, work_stack, i);
1362           bitmap_set_bit (phi_insertion_points, i);
1363         }
1364     }
1365
1366   VEC_free (int, heap, work_stack);
1367
1368   return phi_insertion_points;
1369 }
1370
1371