190075Sobrien/* Control flow graph analysis code for GNU compiler. 290075Sobrien Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3169689Skan 1999, 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc. 490075Sobrien 590075SobrienThis file is part of GCC. 690075Sobrien 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1190075Sobrien 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1690075Sobrien 1790075SobrienYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 2190075Sobrien 2290075Sobrien/* This file contains various simple utilities to analyze the CFG. */ 2390075Sobrien#include "config.h" 2490075Sobrien#include "system.h" 25132718Skan#include "coretypes.h" 26132718Skan#include "tm.h" 2790075Sobrien#include "rtl.h" 28169689Skan#include "obstack.h" 2990075Sobrien#include "hard-reg-set.h" 3090075Sobrien#include "basic-block.h" 3196263Sobrien#include "insn-config.h" 3296263Sobrien#include "recog.h" 3390075Sobrien#include "toplev.h" 3496263Sobrien#include "tm_p.h" 35169689Skan#include "timevar.h" 3690075Sobrien 3790075Sobrien/* Store the data structures necessary for depth-first search. */ 3890075Sobrienstruct depth_first_search_dsS { 3990075Sobrien /* stack for backtracking during the algorithm */ 4090075Sobrien basic_block *stack; 4190075Sobrien 4290075Sobrien /* number of edges in the stack. That is, positions 0, ..., sp-1 4390075Sobrien have edges. */ 4490075Sobrien unsigned int sp; 4590075Sobrien 4690075Sobrien /* record of basic blocks already seen by depth-first search */ 4790075Sobrien sbitmap visited_blocks; 4890075Sobrien}; 4990075Sobrientypedef struct depth_first_search_dsS *depth_first_search_ds; 5090075Sobrien 51132718Skanstatic void flow_dfs_compute_reverse_init (depth_first_search_ds); 52132718Skanstatic void flow_dfs_compute_reverse_add_bb (depth_first_search_ds, 53132718Skan basic_block); 54169689Skanstatic basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds, 55169689Skan basic_block); 56132718Skanstatic void flow_dfs_compute_reverse_finish (depth_first_search_ds); 57132718Skanstatic bool flow_active_insn_p (rtx); 5890075Sobrien 59107590Sobrien/* Like active_insn_p, except keep the return value clobber around 60107590Sobrien even after reload. */ 61107590Sobrien 62107590Sobrienstatic bool 63132718Skanflow_active_insn_p (rtx insn) 64107590Sobrien{ 65107590Sobrien if (active_insn_p (insn)) 66107590Sobrien return true; 67107590Sobrien 68132718Skan /* A clobber of the function return value exists for buggy 69117395Skan programs that fail to return a value. Its effect is to 70107590Sobrien keep the return value from being live across the entire 71107590Sobrien function. If we allow it to be skipped, we introduce the 72169689Skan possibility for register lifetime confusion. */ 73107590Sobrien if (GET_CODE (PATTERN (insn)) == CLOBBER 74169689Skan && REG_P (XEXP (PATTERN (insn), 0)) 75107590Sobrien && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0))) 76107590Sobrien return true; 77107590Sobrien 78107590Sobrien return false; 79107590Sobrien} 80107590Sobrien 8190075Sobrien/* Return true if the block has no effect and only forwards control flow to 8290075Sobrien its single destination. */ 8390075Sobrien 8490075Sobrienbool 85132718Skanforwarder_block_p (basic_block bb) 8690075Sobrien{ 8790075Sobrien rtx insn; 8890075Sobrien 8990075Sobrien if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR 90169689Skan || !single_succ_p (bb)) 9190075Sobrien return false; 9290075Sobrien 93132718Skan for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn)) 94107590Sobrien if (INSN_P (insn) && flow_active_insn_p (insn)) 9590075Sobrien return false; 9690075Sobrien 9790075Sobrien return (!INSN_P (insn) 98169689Skan || (JUMP_P (insn) && simplejump_p (insn)) 99107590Sobrien || !flow_active_insn_p (insn)); 10090075Sobrien} 10190075Sobrien 10290075Sobrien/* Return nonzero if we can reach target from src by falling through. */ 10390075Sobrien 10490075Sobrienbool 105132718Skancan_fallthru (basic_block src, basic_block target) 10690075Sobrien{ 107132718Skan rtx insn = BB_END (src); 108169689Skan rtx insn2; 109169689Skan edge e; 110169689Skan edge_iterator ei; 11190075Sobrien 112169689Skan if (target == EXIT_BLOCK_PTR) 113169689Skan return true; 114117395Skan if (src->next_bb != target) 115117395Skan return 0; 116169689Skan FOR_EACH_EDGE (e, ei, src->succs) 117169689Skan if (e->dest == EXIT_BLOCK_PTR 118169689Skan && e->flags & EDGE_FALLTHRU) 119169689Skan return 0; 120117395Skan 121169689Skan insn2 = BB_HEAD (target); 122132718Skan if (insn2 && !active_insn_p (insn2)) 12390075Sobrien insn2 = next_active_insn (insn2); 12490075Sobrien 12590075Sobrien /* ??? Later we may add code to move jump tables offline. */ 12690075Sobrien return next_active_insn (insn) == insn2; 12790075Sobrien} 128169689Skan 129169689Skan/* Return nonzero if we could reach target from src by falling through, 130169689Skan if the target was made adjacent. If we already have a fall-through 131169689Skan edge to the exit block, we can't do that. */ 132169689Skanbool 133169689Skancould_fall_through (basic_block src, basic_block target) 134169689Skan{ 135169689Skan edge e; 136169689Skan edge_iterator ei; 137169689Skan 138169689Skan if (target == EXIT_BLOCK_PTR) 139169689Skan return true; 140169689Skan FOR_EACH_EDGE (e, ei, src->succs) 141169689Skan if (e->dest == EXIT_BLOCK_PTR 142169689Skan && e->flags & EDGE_FALLTHRU) 143169689Skan return 0; 144169689Skan return true; 145169689Skan} 14690075Sobrien 14790075Sobrien/* Mark the back edges in DFS traversal. 148117395Skan Return nonzero if a loop (natural or otherwise) is present. 14990075Sobrien Inspired by Depth_First_Search_PP described in: 15090075Sobrien 15190075Sobrien Advanced Compiler Design and Implementation 15290075Sobrien Steven Muchnick 15390075Sobrien Morgan Kaufmann, 1997 15490075Sobrien 155169689Skan and heavily borrowed from pre_and_rev_post_order_compute. */ 15690075Sobrien 15790075Sobrienbool 158132718Skanmark_dfs_back_edges (void) 15990075Sobrien{ 160169689Skan edge_iterator *stack; 16190075Sobrien int *pre; 16290075Sobrien int *post; 16390075Sobrien int sp; 16490075Sobrien int prenum = 1; 16590075Sobrien int postnum = 1; 16690075Sobrien sbitmap visited; 16790075Sobrien bool found = false; 16890075Sobrien 16990075Sobrien /* Allocate the preorder and postorder number arrays. */ 170169689Skan pre = XCNEWVEC (int, last_basic_block); 171169689Skan post = XCNEWVEC (int, last_basic_block); 17290075Sobrien 17390075Sobrien /* Allocate stack for back-tracking up CFG. */ 174169689Skan stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); 17590075Sobrien sp = 0; 17690075Sobrien 17790075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 178117395Skan visited = sbitmap_alloc (last_basic_block); 17990075Sobrien 18090075Sobrien /* None of the nodes in the CFG have been visited yet. */ 18190075Sobrien sbitmap_zero (visited); 18290075Sobrien 18390075Sobrien /* Push the first edge on to the stack. */ 184169689Skan stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); 18590075Sobrien 18690075Sobrien while (sp) 18790075Sobrien { 188169689Skan edge_iterator ei; 18990075Sobrien basic_block src; 19090075Sobrien basic_block dest; 19190075Sobrien 19290075Sobrien /* Look at the edge on the top of the stack. */ 193169689Skan ei = stack[sp - 1]; 194169689Skan src = ei_edge (ei)->src; 195169689Skan dest = ei_edge (ei)->dest; 196169689Skan ei_edge (ei)->flags &= ~EDGE_DFS_BACK; 19790075Sobrien 19890075Sobrien /* Check if the edge destination has been visited yet. */ 19990075Sobrien if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 20090075Sobrien { 20190075Sobrien /* Mark that we have visited the destination. */ 20290075Sobrien SET_BIT (visited, dest->index); 20390075Sobrien 20490075Sobrien pre[dest->index] = prenum++; 205169689Skan if (EDGE_COUNT (dest->succs) > 0) 20690075Sobrien { 20790075Sobrien /* Since the DEST node has been visited for the first 20890075Sobrien time, check its successors. */ 209169689Skan stack[sp++] = ei_start (dest->succs); 21090075Sobrien } 21190075Sobrien else 21290075Sobrien post[dest->index] = postnum++; 21390075Sobrien } 21490075Sobrien else 21590075Sobrien { 21690075Sobrien if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR 21790075Sobrien && pre[src->index] >= pre[dest->index] 21890075Sobrien && post[dest->index] == 0) 219169689Skan ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true; 22090075Sobrien 221169689Skan if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR) 22290075Sobrien post[src->index] = postnum++; 22390075Sobrien 224169689Skan if (!ei_one_before_end_p (ei)) 225169689Skan ei_next (&stack[sp - 1]); 22690075Sobrien else 22790075Sobrien sp--; 22890075Sobrien } 22990075Sobrien } 23090075Sobrien 23190075Sobrien free (pre); 23290075Sobrien free (post); 23390075Sobrien free (stack); 23490075Sobrien sbitmap_free (visited); 23590075Sobrien 23690075Sobrien return found; 23790075Sobrien} 23890075Sobrien 239117395Skan/* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */ 240117395Skan 241117395Skanvoid 242132718Skanset_edge_can_fallthru_flag (void) 243117395Skan{ 244117395Skan basic_block bb; 245117395Skan 246117395Skan FOR_EACH_BB (bb) 247117395Skan { 248117395Skan edge e; 249169689Skan edge_iterator ei; 250117395Skan 251169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 252117395Skan { 253117395Skan e->flags &= ~EDGE_CAN_FALLTHRU; 254117395Skan 255117395Skan /* The FALLTHRU edge is also CAN_FALLTHRU edge. */ 256117395Skan if (e->flags & EDGE_FALLTHRU) 257117395Skan e->flags |= EDGE_CAN_FALLTHRU; 258117395Skan } 259117395Skan 260132718Skan /* If the BB ends with an invertible condjump all (2) edges are 261117395Skan CAN_FALLTHRU edges. */ 262169689Skan if (EDGE_COUNT (bb->succs) != 2) 263117395Skan continue; 264132718Skan if (!any_condjump_p (BB_END (bb))) 265117395Skan continue; 266132718Skan if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0)) 267117395Skan continue; 268132718Skan invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0); 269169689Skan EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU; 270169689Skan EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU; 271117395Skan } 272117395Skan} 273117395Skan 27490075Sobrien/* Find unreachable blocks. An unreachable block will have 0 in 275117395Skan the reachable bit in block->flags. A nonzero value indicates the 27690075Sobrien block is reachable. */ 27790075Sobrien 27890075Sobrienvoid 279132718Skanfind_unreachable_blocks (void) 28090075Sobrien{ 28190075Sobrien edge e; 282169689Skan edge_iterator ei; 283117395Skan basic_block *tos, *worklist, bb; 28490075Sobrien 285169689Skan tos = worklist = XNEWVEC (basic_block, n_basic_blocks); 28690075Sobrien 28790075Sobrien /* Clear all the reachability flags. */ 28890075Sobrien 289117395Skan FOR_EACH_BB (bb) 290117395Skan bb->flags &= ~BB_REACHABLE; 29190075Sobrien 29290075Sobrien /* Add our starting points to the worklist. Almost always there will 29390075Sobrien be only one. It isn't inconceivable that we might one day directly 29490075Sobrien support Fortran alternate entry points. */ 29590075Sobrien 296169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 29790075Sobrien { 29890075Sobrien *tos++ = e->dest; 29990075Sobrien 30090075Sobrien /* Mark the block reachable. */ 30190075Sobrien e->dest->flags |= BB_REACHABLE; 30290075Sobrien } 30390075Sobrien 30490075Sobrien /* Iterate: find everything reachable from what we've already seen. */ 30590075Sobrien 30690075Sobrien while (tos != worklist) 30790075Sobrien { 30890075Sobrien basic_block b = *--tos; 30990075Sobrien 310169689Skan FOR_EACH_EDGE (e, ei, b->succs) 311169689Skan { 312169689Skan basic_block dest = e->dest; 313169689Skan 314169689Skan if (!(dest->flags & BB_REACHABLE)) 315169689Skan { 316169689Skan *tos++ = dest; 317169689Skan dest->flags |= BB_REACHABLE; 318169689Skan } 319169689Skan } 32090075Sobrien } 32190075Sobrien 32290075Sobrien free (worklist); 32390075Sobrien} 32490075Sobrien 32590075Sobrien/* Functions to access an edge list with a vector representation. 32690075Sobrien Enough data is kept such that given an index number, the 32790075Sobrien pred and succ that edge represents can be determined, or 32890075Sobrien given a pred and a succ, its index number can be returned. 32990075Sobrien This allows algorithms which consume a lot of memory to 33090075Sobrien represent the normally full matrix of edge (pred,succ) with a 33190075Sobrien single indexed vector, edge (EDGE_INDEX (pred, succ)), with no 33290075Sobrien wasted space in the client code due to sparse flow graphs. */ 33390075Sobrien 33490075Sobrien/* This functions initializes the edge list. Basically the entire 33590075Sobrien flowgraph is processed, and all edges are assigned a number, 33690075Sobrien and the data structure is filled in. */ 33790075Sobrien 33890075Sobrienstruct edge_list * 339132718Skancreate_edge_list (void) 34090075Sobrien{ 34190075Sobrien struct edge_list *elist; 34290075Sobrien edge e; 34390075Sobrien int num_edges; 34490075Sobrien int block_count; 345117395Skan basic_block bb; 346169689Skan edge_iterator ei; 34790075Sobrien 348169689Skan block_count = n_basic_blocks; /* Include the entry and exit blocks. */ 34990075Sobrien 35090075Sobrien num_edges = 0; 35190075Sobrien 35290075Sobrien /* Determine the number of edges in the flow graph by counting successor 35390075Sobrien edges on each basic block. */ 354117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 35590075Sobrien { 356169689Skan num_edges += EDGE_COUNT (bb->succs); 35790075Sobrien } 35890075Sobrien 359169689Skan elist = XNEW (struct edge_list); 36090075Sobrien elist->num_blocks = block_count; 36190075Sobrien elist->num_edges = num_edges; 362169689Skan elist->index_to_edge = XNEWVEC (edge, num_edges); 36390075Sobrien 36490075Sobrien num_edges = 0; 36590075Sobrien 366117395Skan /* Follow successors of blocks, and register these edges. */ 367117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 368169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 369117395Skan elist->index_to_edge[num_edges++] = e; 37090075Sobrien 37190075Sobrien return elist; 37290075Sobrien} 37390075Sobrien 37490075Sobrien/* This function free's memory associated with an edge list. */ 37590075Sobrien 37690075Sobrienvoid 377132718Skanfree_edge_list (struct edge_list *elist) 37890075Sobrien{ 37990075Sobrien if (elist) 38090075Sobrien { 38190075Sobrien free (elist->index_to_edge); 38290075Sobrien free (elist); 38390075Sobrien } 38490075Sobrien} 38590075Sobrien 38690075Sobrien/* This function provides debug output showing an edge list. */ 38790075Sobrien 38890075Sobrienvoid 389132718Skanprint_edge_list (FILE *f, struct edge_list *elist) 39090075Sobrien{ 39190075Sobrien int x; 39290075Sobrien 39390075Sobrien fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n", 394169689Skan elist->num_blocks, elist->num_edges); 39590075Sobrien 39690075Sobrien for (x = 0; x < elist->num_edges; x++) 39790075Sobrien { 39890075Sobrien fprintf (f, " %-4d - edge(", x); 39990075Sobrien if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR) 40090075Sobrien fprintf (f, "entry,"); 40190075Sobrien else 40290075Sobrien fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index); 40390075Sobrien 40490075Sobrien if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR) 40590075Sobrien fprintf (f, "exit)\n"); 40690075Sobrien else 40790075Sobrien fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index); 40890075Sobrien } 40990075Sobrien} 41090075Sobrien 41190075Sobrien/* This function provides an internal consistency check of an edge list, 41290075Sobrien verifying that all edges are present, and that there are no 41390075Sobrien extra edges. */ 41490075Sobrien 41590075Sobrienvoid 416132718Skanverify_edge_list (FILE *f, struct edge_list *elist) 41790075Sobrien{ 418117395Skan int pred, succ, index; 41990075Sobrien edge e; 420117395Skan basic_block bb, p, s; 421169689Skan edge_iterator ei; 42290075Sobrien 423117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 42490075Sobrien { 425169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 42690075Sobrien { 42790075Sobrien pred = e->src->index; 42890075Sobrien succ = e->dest->index; 42990075Sobrien index = EDGE_INDEX (elist, e->src, e->dest); 43090075Sobrien if (index == EDGE_INDEX_NO_EDGE) 43190075Sobrien { 43290075Sobrien fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ); 43390075Sobrien continue; 43490075Sobrien } 43590075Sobrien 43690075Sobrien if (INDEX_EDGE_PRED_BB (elist, index)->index != pred) 43790075Sobrien fprintf (f, "*p* Pred for index %d should be %d not %d\n", 43890075Sobrien index, pred, INDEX_EDGE_PRED_BB (elist, index)->index); 43990075Sobrien if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ) 44090075Sobrien fprintf (f, "*p* Succ for index %d should be %d not %d\n", 44190075Sobrien index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index); 44290075Sobrien } 44390075Sobrien } 44490075Sobrien 445117395Skan /* We've verified that all the edges are in the list, now lets make sure 44690075Sobrien there are no spurious edges in the list. */ 44790075Sobrien 448117395Skan FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 449117395Skan FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) 45090075Sobrien { 45190075Sobrien int found_edge = 0; 45290075Sobrien 453169689Skan FOR_EACH_EDGE (e, ei, p->succs) 45490075Sobrien if (e->dest == s) 45590075Sobrien { 45690075Sobrien found_edge = 1; 45790075Sobrien break; 45890075Sobrien } 45990075Sobrien 460169689Skan FOR_EACH_EDGE (e, ei, s->preds) 46190075Sobrien if (e->src == p) 46290075Sobrien { 46390075Sobrien found_edge = 1; 46490075Sobrien break; 46590075Sobrien } 46690075Sobrien 467117395Skan if (EDGE_INDEX (elist, p, s) 46890075Sobrien == EDGE_INDEX_NO_EDGE && found_edge != 0) 46990075Sobrien fprintf (f, "*** Edge (%d, %d) appears to not have an index\n", 470117395Skan p->index, s->index); 471117395Skan if (EDGE_INDEX (elist, p, s) 47290075Sobrien != EDGE_INDEX_NO_EDGE && found_edge == 0) 47390075Sobrien fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n", 474117395Skan p->index, s->index, EDGE_INDEX (elist, p, s)); 47590075Sobrien } 47690075Sobrien} 47790075Sobrien 478169689Skan/* Given PRED and SUCC blocks, return the edge which connects the blocks. 479169689Skan If no such edge exists, return NULL. */ 480169689Skan 481169689Skanedge 482169689Skanfind_edge (basic_block pred, basic_block succ) 483169689Skan{ 484169689Skan edge e; 485169689Skan edge_iterator ei; 486169689Skan 487169689Skan if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds)) 488169689Skan { 489169689Skan FOR_EACH_EDGE (e, ei, pred->succs) 490169689Skan if (e->dest == succ) 491169689Skan return e; 492169689Skan } 493169689Skan else 494169689Skan { 495169689Skan FOR_EACH_EDGE (e, ei, succ->preds) 496169689Skan if (e->src == pred) 497169689Skan return e; 498169689Skan } 499169689Skan 500169689Skan return NULL; 501169689Skan} 502169689Skan 50390075Sobrien/* This routine will determine what, if any, edge there is between 50490075Sobrien a specified predecessor and successor. */ 50590075Sobrien 50690075Sobrienint 507132718Skanfind_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ) 50890075Sobrien{ 50990075Sobrien int x; 51090075Sobrien 51190075Sobrien for (x = 0; x < NUM_EDGES (edge_list); x++) 51290075Sobrien if (INDEX_EDGE_PRED_BB (edge_list, x) == pred 51390075Sobrien && INDEX_EDGE_SUCC_BB (edge_list, x) == succ) 51490075Sobrien return x; 51590075Sobrien 51690075Sobrien return (EDGE_INDEX_NO_EDGE); 51790075Sobrien} 51890075Sobrien 51990075Sobrien/* Dump the list of basic blocks in the bitmap NODES. */ 52090075Sobrien 52190075Sobrienvoid 522132718Skanflow_nodes_print (const char *str, const sbitmap nodes, FILE *file) 52390075Sobrien{ 524169689Skan unsigned int node = 0; 525169689Skan sbitmap_iterator sbi; 52690075Sobrien 52790075Sobrien if (! nodes) 52890075Sobrien return; 52990075Sobrien 53090075Sobrien fprintf (file, "%s { ", str); 531169689Skan EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi) 532169689Skan fprintf (file, "%d ", node); 53390075Sobrien fputs ("}\n", file); 53490075Sobrien} 53590075Sobrien 53690075Sobrien/* Dump the list of edges in the array EDGE_LIST. */ 53790075Sobrien 53890075Sobrienvoid 539132718Skanflow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file) 54090075Sobrien{ 54190075Sobrien int i; 54290075Sobrien 54390075Sobrien if (! edge_list) 54490075Sobrien return; 54590075Sobrien 54690075Sobrien fprintf (file, "%s { ", str); 54790075Sobrien for (i = 0; i < num_edges; i++) 54890075Sobrien fprintf (file, "%d->%d ", edge_list[i]->src->index, 54990075Sobrien edge_list[i]->dest->index); 55090075Sobrien 55190075Sobrien fputs ("}\n", file); 55290075Sobrien} 55390075Sobrien 55490075Sobrien 555169689Skan/* This routine will remove any fake predecessor edges for a basic block. 556169689Skan When the edge is removed, it is also removed from whatever successor 55790075Sobrien list it is in. */ 55890075Sobrien 55990075Sobrienstatic void 560169689Skanremove_fake_predecessors (basic_block bb) 56190075Sobrien{ 56290075Sobrien edge e; 563169689Skan edge_iterator ei; 56490075Sobrien 565169689Skan for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) 56690075Sobrien { 567169689Skan if ((e->flags & EDGE_FAKE) == EDGE_FAKE) 568169689Skan remove_edge (e); 569169689Skan else 570169689Skan ei_next (&ei); 57190075Sobrien } 57290075Sobrien} 57390075Sobrien 57490075Sobrien/* This routine will remove all fake edges from the flow graph. If 57590075Sobrien we remove all fake successors, it will automatically remove all 57690075Sobrien fake predecessors. */ 57790075Sobrien 57890075Sobrienvoid 579132718Skanremove_fake_edges (void) 58090075Sobrien{ 581117395Skan basic_block bb; 58290075Sobrien 583169689Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) 584169689Skan remove_fake_predecessors (bb); 58590075Sobrien} 58690075Sobrien 587169689Skan/* This routine will remove all fake edges to the EXIT_BLOCK. */ 588169689Skan 589169689Skanvoid 590169689Skanremove_fake_exit_edges (void) 591169689Skan{ 592169689Skan remove_fake_predecessors (EXIT_BLOCK_PTR); 593169689Skan} 594169689Skan 595169689Skan 59690075Sobrien/* This function will add a fake edge between any block which has no 59790075Sobrien successors, and the exit block. Some data flow equations require these 59890075Sobrien edges to exist. */ 59990075Sobrien 60090075Sobrienvoid 601132718Skanadd_noreturn_fake_exit_edges (void) 60290075Sobrien{ 603117395Skan basic_block bb; 60490075Sobrien 605117395Skan FOR_EACH_BB (bb) 606169689Skan if (EDGE_COUNT (bb->succs) == 0) 607117395Skan make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 60890075Sobrien} 60990075Sobrien 61090075Sobrien/* This function adds a fake edge between any infinite loops to the 61190075Sobrien exit block. Some optimizations require a path from each node to 61290075Sobrien the exit node. 61390075Sobrien 61490075Sobrien See also Morgan, Figure 3.10, pp. 82-83. 61590075Sobrien 61690075Sobrien The current implementation is ugly, not attempting to minimize the 61790075Sobrien number of inserted fake edges. To reduce the number of fake edges 61890075Sobrien to insert, add fake edges from _innermost_ loops containing only 61990075Sobrien nodes not reachable from the exit block. */ 62090075Sobrien 62190075Sobrienvoid 622132718Skanconnect_infinite_loops_to_exit (void) 62390075Sobrien{ 624169689Skan basic_block unvisited_block = EXIT_BLOCK_PTR; 62590075Sobrien struct depth_first_search_dsS dfs_ds; 62690075Sobrien 62790075Sobrien /* Perform depth-first search in the reverse graph to find nodes 62890075Sobrien reachable from the exit block. */ 62990075Sobrien flow_dfs_compute_reverse_init (&dfs_ds); 63090075Sobrien flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR); 63190075Sobrien 63290075Sobrien /* Repeatedly add fake edges, updating the unreachable nodes. */ 63390075Sobrien while (1) 63490075Sobrien { 635169689Skan unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds, 636169689Skan unvisited_block); 63790075Sobrien if (!unvisited_block) 63890075Sobrien break; 63990075Sobrien 64090075Sobrien make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE); 64190075Sobrien flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block); 64290075Sobrien } 64390075Sobrien 64490075Sobrien flow_dfs_compute_reverse_finish (&dfs_ds); 64590075Sobrien return; 64690075Sobrien} 64790075Sobrien 648169689Skan/* Compute reverse top sort order. 649169689Skan This is computing a post order numbering of the graph. */ 65090075Sobrien 651169689Skanint 652169689Skanpost_order_compute (int *post_order, bool include_entry_exit) 65390075Sobrien{ 654169689Skan edge_iterator *stack; 65590075Sobrien int sp; 656169689Skan int post_order_num = 0; 65790075Sobrien sbitmap visited; 65890075Sobrien 659169689Skan if (include_entry_exit) 660169689Skan post_order[post_order_num++] = EXIT_BLOCK; 661169689Skan 66290075Sobrien /* Allocate stack for back-tracking up CFG. */ 663169689Skan stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); 66490075Sobrien sp = 0; 66590075Sobrien 66690075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 667117395Skan visited = sbitmap_alloc (last_basic_block); 66890075Sobrien 66990075Sobrien /* None of the nodes in the CFG have been visited yet. */ 67090075Sobrien sbitmap_zero (visited); 67190075Sobrien 67290075Sobrien /* Push the first edge on to the stack. */ 673169689Skan stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); 67490075Sobrien 67590075Sobrien while (sp) 67690075Sobrien { 677169689Skan edge_iterator ei; 67890075Sobrien basic_block src; 67990075Sobrien basic_block dest; 68090075Sobrien 68190075Sobrien /* Look at the edge on the top of the stack. */ 682169689Skan ei = stack[sp - 1]; 683169689Skan src = ei_edge (ei)->src; 684169689Skan dest = ei_edge (ei)->dest; 68590075Sobrien 68690075Sobrien /* Check if the edge destination has been visited yet. */ 68790075Sobrien if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 68890075Sobrien { 68990075Sobrien /* Mark that we have visited the destination. */ 69090075Sobrien SET_BIT (visited, dest->index); 69190075Sobrien 692169689Skan if (EDGE_COUNT (dest->succs) > 0) 69390075Sobrien /* Since the DEST node has been visited for the first 69490075Sobrien time, check its successors. */ 695169689Skan stack[sp++] = ei_start (dest->succs); 69690075Sobrien else 697169689Skan post_order[post_order_num++] = dest->index; 69890075Sobrien } 69990075Sobrien else 70090075Sobrien { 701169689Skan if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR) 702169689Skan post_order[post_order_num++] = src->index; 70390075Sobrien 704169689Skan if (!ei_one_before_end_p (ei)) 705169689Skan ei_next (&stack[sp - 1]); 70690075Sobrien else 70790075Sobrien sp--; 70890075Sobrien } 70990075Sobrien } 71090075Sobrien 711169689Skan if (include_entry_exit) 712169689Skan post_order[post_order_num++] = ENTRY_BLOCK; 713169689Skan 71490075Sobrien free (stack); 71590075Sobrien sbitmap_free (visited); 716169689Skan return post_order_num; 71790075Sobrien} 71890075Sobrien 71990075Sobrien/* Compute the depth first search order and store in the array 720169689Skan PRE_ORDER if nonzero, marking the nodes visited in VISITED. If 721169689Skan REV_POST_ORDER is nonzero, return the reverse completion number for each 72290075Sobrien node. Returns the number of nodes visited. A depth first search 72390075Sobrien tries to get as far away from the starting point as quickly as 724169689Skan possible. 72590075Sobrien 726169689Skan pre_order is a really a preorder numbering of the graph. 727169689Skan rev_post_order is really a reverse postorder numbering of the graph. 728169689Skan */ 729169689Skan 73090075Sobrienint 731169689Skanpre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, 732169689Skan bool include_entry_exit) 73390075Sobrien{ 734169689Skan edge_iterator *stack; 73590075Sobrien int sp; 736169689Skan int pre_order_num = 0; 737169689Skan int rev_post_order_num = n_basic_blocks - 1; 73890075Sobrien sbitmap visited; 73990075Sobrien 74090075Sobrien /* Allocate stack for back-tracking up CFG. */ 741169689Skan stack = XNEWVEC (edge_iterator, n_basic_blocks + 1); 74290075Sobrien sp = 0; 74390075Sobrien 744169689Skan if (include_entry_exit) 745169689Skan { 746169689Skan if (pre_order) 747169689Skan pre_order[pre_order_num] = ENTRY_BLOCK; 748169689Skan pre_order_num++; 749169689Skan if (rev_post_order) 750169689Skan rev_post_order[rev_post_order_num--] = ENTRY_BLOCK; 751169689Skan } 752169689Skan else 753169689Skan rev_post_order_num -= NUM_FIXED_BLOCKS; 754169689Skan 75590075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 756117395Skan visited = sbitmap_alloc (last_basic_block); 75790075Sobrien 75890075Sobrien /* None of the nodes in the CFG have been visited yet. */ 75990075Sobrien sbitmap_zero (visited); 76090075Sobrien 76190075Sobrien /* Push the first edge on to the stack. */ 762169689Skan stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs); 76390075Sobrien 76490075Sobrien while (sp) 76590075Sobrien { 766169689Skan edge_iterator ei; 76790075Sobrien basic_block src; 76890075Sobrien basic_block dest; 76990075Sobrien 77090075Sobrien /* Look at the edge on the top of the stack. */ 771169689Skan ei = stack[sp - 1]; 772169689Skan src = ei_edge (ei)->src; 773169689Skan dest = ei_edge (ei)->dest; 77490075Sobrien 77590075Sobrien /* Check if the edge destination has been visited yet. */ 77690075Sobrien if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 77790075Sobrien { 77890075Sobrien /* Mark that we have visited the destination. */ 77990075Sobrien SET_BIT (visited, dest->index); 78090075Sobrien 781169689Skan if (pre_order) 782169689Skan pre_order[pre_order_num] = dest->index; 78390075Sobrien 784169689Skan pre_order_num++; 78590075Sobrien 786169689Skan if (EDGE_COUNT (dest->succs) > 0) 78790075Sobrien /* Since the DEST node has been visited for the first 78890075Sobrien time, check its successors. */ 789169689Skan stack[sp++] = ei_start (dest->succs); 790169689Skan else if (rev_post_order) 79190075Sobrien /* There are no successors for the DEST node so assign 79290075Sobrien its reverse completion number. */ 793169689Skan rev_post_order[rev_post_order_num--] = dest->index; 79490075Sobrien } 79590075Sobrien else 79690075Sobrien { 797169689Skan if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR 798169689Skan && rev_post_order) 79990075Sobrien /* There are no more successors for the SRC node 80090075Sobrien so assign its reverse completion number. */ 801169689Skan rev_post_order[rev_post_order_num--] = src->index; 80290075Sobrien 803169689Skan if (!ei_one_before_end_p (ei)) 804169689Skan ei_next (&stack[sp - 1]); 80590075Sobrien else 80690075Sobrien sp--; 80790075Sobrien } 80890075Sobrien } 80990075Sobrien 81090075Sobrien free (stack); 81190075Sobrien sbitmap_free (visited); 81290075Sobrien 813169689Skan if (include_entry_exit) 81490075Sobrien { 815169689Skan if (pre_order) 816169689Skan pre_order[pre_order_num] = EXIT_BLOCK; 817169689Skan pre_order_num++; 818169689Skan if (rev_post_order) 819169689Skan rev_post_order[rev_post_order_num--] = EXIT_BLOCK; 820169689Skan /* The number of nodes visited should be the number of blocks. */ 821169689Skan gcc_assert (pre_order_num == n_basic_blocks); 82290075Sobrien } 823169689Skan else 824169689Skan /* The number of nodes visited should be the number of blocks minus 825169689Skan the entry and exit blocks which are not visited here. */ 826169689Skan gcc_assert (pre_order_num == n_basic_blocks - NUM_FIXED_BLOCKS); 82790075Sobrien 828169689Skan return pre_order_num; 82990075Sobrien} 83090075Sobrien 83190075Sobrien/* Compute the depth first search order on the _reverse_ graph and 83290075Sobrien store in the array DFS_ORDER, marking the nodes visited in VISITED. 83390075Sobrien Returns the number of nodes visited. 83490075Sobrien 83590075Sobrien The computation is split into three pieces: 83690075Sobrien 83790075Sobrien flow_dfs_compute_reverse_init () creates the necessary data 83890075Sobrien structures. 83990075Sobrien 84090075Sobrien flow_dfs_compute_reverse_add_bb () adds a basic block to the data 84190075Sobrien structures. The block will start the search. 84290075Sobrien 84390075Sobrien flow_dfs_compute_reverse_execute () continues (or starts) the 84490075Sobrien search using the block on the top of the stack, stopping when the 84590075Sobrien stack is empty. 84690075Sobrien 84790075Sobrien flow_dfs_compute_reverse_finish () destroys the necessary data 84890075Sobrien structures. 84990075Sobrien 85090075Sobrien Thus, the user will probably call ..._init(), call ..._add_bb() to 85190075Sobrien add a beginning basic block to the stack, call ..._execute(), 85290075Sobrien possibly add another bb to the stack and again call ..._execute(), 85390075Sobrien ..., and finally call _finish(). */ 85490075Sobrien 85590075Sobrien/* Initialize the data structures used for depth-first search on the 85690075Sobrien reverse graph. If INITIALIZE_STACK is nonzero, the exit block is 85790075Sobrien added to the basic block stack. DATA is the current depth-first 858117395Skan search context. If INITIALIZE_STACK is nonzero, there is an 85990075Sobrien element on the stack. */ 86090075Sobrien 86190075Sobrienstatic void 862132718Skanflow_dfs_compute_reverse_init (depth_first_search_ds data) 86390075Sobrien{ 86490075Sobrien /* Allocate stack for back-tracking up CFG. */ 865169689Skan data->stack = XNEWVEC (basic_block, n_basic_blocks); 86690075Sobrien data->sp = 0; 86790075Sobrien 86890075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 869169689Skan data->visited_blocks = sbitmap_alloc (last_basic_block); 87090075Sobrien 87190075Sobrien /* None of the nodes in the CFG have been visited yet. */ 87290075Sobrien sbitmap_zero (data->visited_blocks); 87390075Sobrien 87490075Sobrien return; 87590075Sobrien} 87690075Sobrien 87790075Sobrien/* Add the specified basic block to the top of the dfs data 87890075Sobrien structures. When the search continues, it will start at the 87990075Sobrien block. */ 88090075Sobrien 88190075Sobrienstatic void 882132718Skanflow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb) 88390075Sobrien{ 88490075Sobrien data->stack[data->sp++] = bb; 885169689Skan SET_BIT (data->visited_blocks, bb->index); 88690075Sobrien} 88790075Sobrien 88890075Sobrien/* Continue the depth-first search through the reverse graph starting with the 88990075Sobrien block at the stack's top and ending when the stack is empty. Visited nodes 89090075Sobrien are marked. Returns an unvisited basic block, or NULL if there is none 89190075Sobrien available. */ 89290075Sobrien 89390075Sobrienstatic basic_block 894169689Skanflow_dfs_compute_reverse_execute (depth_first_search_ds data, 895169689Skan basic_block last_unvisited) 89690075Sobrien{ 89790075Sobrien basic_block bb; 89890075Sobrien edge e; 899169689Skan edge_iterator ei; 90090075Sobrien 90190075Sobrien while (data->sp > 0) 90290075Sobrien { 90390075Sobrien bb = data->stack[--data->sp]; 90490075Sobrien 90590075Sobrien /* Perform depth-first search on adjacent vertices. */ 906169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 907169689Skan if (!TEST_BIT (data->visited_blocks, e->src->index)) 90890075Sobrien flow_dfs_compute_reverse_add_bb (data, e->src); 90990075Sobrien } 91090075Sobrien 91190075Sobrien /* Determine if there are unvisited basic blocks. */ 912169689Skan FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb) 913169689Skan if (!TEST_BIT (data->visited_blocks, bb->index)) 914117395Skan return bb; 91590075Sobrien 91690075Sobrien return NULL; 91790075Sobrien} 91890075Sobrien 91990075Sobrien/* Destroy the data structures needed for depth-first search on the 92090075Sobrien reverse graph. */ 92190075Sobrien 92290075Sobrienstatic void 923132718Skanflow_dfs_compute_reverse_finish (depth_first_search_ds data) 92490075Sobrien{ 92590075Sobrien free (data->stack); 92690075Sobrien sbitmap_free (data->visited_blocks); 92790075Sobrien} 928117395Skan 929117395Skan/* Performs dfs search from BB over vertices satisfying PREDICATE; 930117395Skan if REVERSE, go against direction of edges. Returns number of blocks 931117395Skan found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */ 932117395Skanint 933132718Skandfs_enumerate_from (basic_block bb, int reverse, 934132718Skan bool (*predicate) (basic_block, void *), 935132718Skan basic_block *rslt, int rslt_max, void *data) 936117395Skan{ 937117395Skan basic_block *st, lbb; 938117395Skan int sp = 0, tv = 0; 939169689Skan unsigned size; 940117395Skan 941169689Skan /* A bitmap to keep track of visited blocks. Allocating it each time 942169689Skan this function is called is not possible, since dfs_enumerate_from 943169689Skan is often used on small (almost) disjoint parts of cfg (bodies of 944169689Skan loops), and allocating a large sbitmap would lead to quadratic 945169689Skan behavior. */ 946169689Skan static sbitmap visited; 947169689Skan static unsigned v_size; 948169689Skan 949169689Skan#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index)) 950169689Skan#define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index)) 951169689Skan#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index)) 952169689Skan 953169689Skan /* Resize the VISITED sbitmap if necessary. */ 954169689Skan size = last_basic_block; 955169689Skan if (size < 10) 956169689Skan size = 10; 957169689Skan 958169689Skan if (!visited) 959169689Skan { 960169689Skan 961169689Skan visited = sbitmap_alloc (size); 962169689Skan sbitmap_zero (visited); 963169689Skan v_size = size; 964169689Skan } 965169689Skan else if (v_size < size) 966169689Skan { 967169689Skan /* Ensure that we increase the size of the sbitmap exponentially. */ 968169689Skan if (2 * v_size > size) 969169689Skan size = 2 * v_size; 970169689Skan 971169689Skan visited = sbitmap_resize (visited, size, 0); 972169689Skan v_size = size; 973169689Skan } 974169689Skan 975169689Skan st = XCNEWVEC (basic_block, rslt_max); 976117395Skan rslt[tv++] = st[sp++] = bb; 977169689Skan MARK_VISITED (bb); 978117395Skan while (sp) 979117395Skan { 980117395Skan edge e; 981169689Skan edge_iterator ei; 982117395Skan lbb = st[--sp]; 983117395Skan if (reverse) 984169689Skan { 985169689Skan FOR_EACH_EDGE (e, ei, lbb->preds) 986169689Skan if (!VISITED_P (e->src) && predicate (e->src, data)) 987117395Skan { 988169689Skan gcc_assert (tv != rslt_max); 989169689Skan rslt[tv++] = st[sp++] = e->src; 990169689Skan MARK_VISITED (e->src); 991117395Skan } 992169689Skan } 993117395Skan else 994169689Skan { 995169689Skan FOR_EACH_EDGE (e, ei, lbb->succs) 996169689Skan if (!VISITED_P (e->dest) && predicate (e->dest, data)) 997117395Skan { 998169689Skan gcc_assert (tv != rslt_max); 999169689Skan rslt[tv++] = st[sp++] = e->dest; 1000169689Skan MARK_VISITED (e->dest); 1001117395Skan } 1002117395Skan } 1003117395Skan } 1004117395Skan free (st); 1005117395Skan for (sp = 0; sp < tv; sp++) 1006169689Skan UNMARK_VISITED (rslt[sp]); 1007117395Skan return tv; 1008169689Skan#undef MARK_VISITED 1009169689Skan#undef UNMARK_VISITED 1010169689Skan#undef VISITED_P 1011117395Skan} 1012169689Skan 1013169689Skan 1014169689Skan/* Compute dominance frontiers, ala Harvey, Ferrante, et al. 1015169689Skan 1016169689Skan This algorithm can be found in Timothy Harvey's PhD thesis, at 1017169689Skan http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative 1018169689Skan dominance algorithms. 1019169689Skan 1020169689Skan First, we identify each join point, j (any node with more than one 1021169689Skan incoming edge is a join point). 1022169689Skan 1023169689Skan We then examine each predecessor, p, of j and walk up the dominator tree 1024169689Skan starting at p. 1025169689Skan 1026169689Skan We stop the walk when we reach j's immediate dominator - j is in the 1027169689Skan dominance frontier of each of the nodes in the walk, except for j's 1028169689Skan immediate dominator. Intuitively, all of the rest of j's dominators are 1029169689Skan shared by j's predecessors as well. 1030169689Skan Since they dominate j, they will not have j in their dominance frontiers. 1031169689Skan 1032169689Skan The number of nodes touched by this algorithm is equal to the size 1033169689Skan of the dominance frontiers, no more, no less. 1034169689Skan*/ 1035169689Skan 1036169689Skan 1037169689Skanstatic void 1038169689Skancompute_dominance_frontiers_1 (bitmap *frontiers) 1039169689Skan{ 1040169689Skan edge p; 1041169689Skan edge_iterator ei; 1042169689Skan basic_block b; 1043169689Skan FOR_EACH_BB (b) 1044169689Skan { 1045169689Skan if (EDGE_COUNT (b->preds) >= 2) 1046169689Skan { 1047169689Skan FOR_EACH_EDGE (p, ei, b->preds) 1048169689Skan { 1049169689Skan basic_block runner = p->src; 1050169689Skan basic_block domsb; 1051169689Skan if (runner == ENTRY_BLOCK_PTR) 1052169689Skan continue; 1053169689Skan 1054169689Skan domsb = get_immediate_dominator (CDI_DOMINATORS, b); 1055169689Skan while (runner != domsb) 1056169689Skan { 1057169689Skan if (bitmap_bit_p (frontiers[runner->index], b->index)) 1058169689Skan break; 1059169689Skan bitmap_set_bit (frontiers[runner->index], 1060169689Skan b->index); 1061169689Skan runner = get_immediate_dominator (CDI_DOMINATORS, 1062169689Skan runner); 1063169689Skan } 1064169689Skan } 1065169689Skan } 1066169689Skan } 1067169689Skan} 1068169689Skan 1069169689Skan 1070169689Skanvoid 1071169689Skancompute_dominance_frontiers (bitmap *frontiers) 1072169689Skan{ 1073169689Skan timevar_push (TV_DOM_FRONTIERS); 1074169689Skan 1075169689Skan compute_dominance_frontiers_1 (frontiers); 1076169689Skan 1077169689Skan timevar_pop (TV_DOM_FRONTIERS); 1078169689Skan} 1079169689Skan 1080