cfganal.c revision 117395
190075Sobrien/* Control flow graph analysis code for GNU compiler. 290075Sobrien Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3110611Skan 1999, 2000, 2001, 2003 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 1990075SobrienSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 2090075Sobrien02111-1307, USA. */ 2190075Sobrien 2290075Sobrien/* This file contains various simple utilities to analyze the CFG. */ 2390075Sobrien#include "config.h" 2490075Sobrien#include "system.h" 2590075Sobrien#include "rtl.h" 2690075Sobrien#include "hard-reg-set.h" 2790075Sobrien#include "basic-block.h" 2896263Sobrien#include "insn-config.h" 2996263Sobrien#include "recog.h" 3090075Sobrien#include "toplev.h" 3196263Sobrien#include "tm_p.h" 3290075Sobrien 3390075Sobrien/* Store the data structures necessary for depth-first search. */ 3490075Sobrienstruct depth_first_search_dsS { 3590075Sobrien /* stack for backtracking during the algorithm */ 3690075Sobrien basic_block *stack; 3790075Sobrien 3890075Sobrien /* number of edges in the stack. That is, positions 0, ..., sp-1 3990075Sobrien have edges. */ 4090075Sobrien unsigned int sp; 4190075Sobrien 4290075Sobrien /* record of basic blocks already seen by depth-first search */ 4390075Sobrien sbitmap visited_blocks; 4490075Sobrien}; 4590075Sobrientypedef struct depth_first_search_dsS *depth_first_search_ds; 4690075Sobrien 4790075Sobrienstatic void flow_dfs_compute_reverse_init 4890075Sobrien PARAMS ((depth_first_search_ds)); 4990075Sobrienstatic void flow_dfs_compute_reverse_add_bb 5090075Sobrien PARAMS ((depth_first_search_ds, basic_block)); 5190075Sobrienstatic basic_block flow_dfs_compute_reverse_execute 5290075Sobrien PARAMS ((depth_first_search_ds)); 5390075Sobrienstatic void flow_dfs_compute_reverse_finish 5490075Sobrien PARAMS ((depth_first_search_ds)); 5590075Sobrienstatic void remove_fake_successors PARAMS ((basic_block)); 5690075Sobrienstatic bool need_fake_edge_p PARAMS ((rtx)); 57107590Sobrienstatic bool flow_active_insn_p PARAMS ((rtx)); 5890075Sobrien 59107590Sobrien/* Like active_insn_p, except keep the return value clobber around 60107590Sobrien even after reload. */ 61107590Sobrien 62107590Sobrienstatic bool 63107590Sobrienflow_active_insn_p (insn) 64107590Sobrien rtx insn; 65107590Sobrien{ 66107590Sobrien if (active_insn_p (insn)) 67107590Sobrien return true; 68107590Sobrien 69107590Sobrien /* A clobber of the function return value exists for buggy 70117395Skan programs that fail to return a value. Its effect is to 71107590Sobrien keep the return value from being live across the entire 72107590Sobrien function. If we allow it to be skipped, we introduce the 73107590Sobrien possibility for register livetime aborts. */ 74107590Sobrien if (GET_CODE (PATTERN (insn)) == CLOBBER 75107590Sobrien && GET_CODE (XEXP (PATTERN (insn), 0)) == REG 76107590Sobrien && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0))) 77107590Sobrien return true; 78107590Sobrien 79107590Sobrien return false; 80107590Sobrien} 81107590Sobrien 8290075Sobrien/* Return true if the block has no effect and only forwards control flow to 8390075Sobrien its single destination. */ 8490075Sobrien 8590075Sobrienbool 8690075Sobrienforwarder_block_p (bb) 8790075Sobrien basic_block bb; 8890075Sobrien{ 8990075Sobrien rtx insn; 9090075Sobrien 9190075Sobrien if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR 9290075Sobrien || !bb->succ || bb->succ->succ_next) 9390075Sobrien return false; 9490075Sobrien 9590075Sobrien for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn)) 96107590Sobrien if (INSN_P (insn) && flow_active_insn_p (insn)) 9790075Sobrien return false; 9890075Sobrien 9990075Sobrien return (!INSN_P (insn) 10090075Sobrien || (GET_CODE (insn) == JUMP_INSN && simplejump_p (insn)) 101107590Sobrien || !flow_active_insn_p (insn)); 10290075Sobrien} 10390075Sobrien 10490075Sobrien/* Return nonzero if we can reach target from src by falling through. */ 10590075Sobrien 10690075Sobrienbool 10790075Sobriencan_fallthru (src, target) 10890075Sobrien basic_block src, target; 10990075Sobrien{ 11090075Sobrien rtx insn = src->end; 11190075Sobrien rtx insn2 = target->head; 11290075Sobrien 113117395Skan if (src->next_bb != target) 114117395Skan return 0; 115117395Skan 116117395Skan if (!active_insn_p (insn2)) 11790075Sobrien insn2 = next_active_insn (insn2); 11890075Sobrien 11990075Sobrien /* ??? Later we may add code to move jump tables offline. */ 12090075Sobrien return next_active_insn (insn) == insn2; 12190075Sobrien} 12290075Sobrien 12390075Sobrien/* Mark the back edges in DFS traversal. 124117395Skan Return nonzero if a loop (natural or otherwise) is present. 12590075Sobrien Inspired by Depth_First_Search_PP described in: 12690075Sobrien 12790075Sobrien Advanced Compiler Design and Implementation 12890075Sobrien Steven Muchnick 12990075Sobrien Morgan Kaufmann, 1997 13090075Sobrien 13190075Sobrien and heavily borrowed from flow_depth_first_order_compute. */ 13290075Sobrien 13390075Sobrienbool 13490075Sobrienmark_dfs_back_edges () 13590075Sobrien{ 13690075Sobrien edge *stack; 13790075Sobrien int *pre; 13890075Sobrien int *post; 13990075Sobrien int sp; 14090075Sobrien int prenum = 1; 14190075Sobrien int postnum = 1; 14290075Sobrien sbitmap visited; 14390075Sobrien bool found = false; 14490075Sobrien 14590075Sobrien /* Allocate the preorder and postorder number arrays. */ 146117395Skan pre = (int *) xcalloc (last_basic_block, sizeof (int)); 147117395Skan post = (int *) xcalloc (last_basic_block, sizeof (int)); 14890075Sobrien 14990075Sobrien /* Allocate stack for back-tracking up CFG. */ 15090075Sobrien stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); 15190075Sobrien sp = 0; 15290075Sobrien 15390075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 154117395Skan visited = sbitmap_alloc (last_basic_block); 15590075Sobrien 15690075Sobrien /* None of the nodes in the CFG have been visited yet. */ 15790075Sobrien sbitmap_zero (visited); 15890075Sobrien 15990075Sobrien /* Push the first edge on to the stack. */ 16090075Sobrien stack[sp++] = ENTRY_BLOCK_PTR->succ; 16190075Sobrien 16290075Sobrien while (sp) 16390075Sobrien { 16490075Sobrien edge e; 16590075Sobrien basic_block src; 16690075Sobrien basic_block dest; 16790075Sobrien 16890075Sobrien /* Look at the edge on the top of the stack. */ 16990075Sobrien e = stack[sp - 1]; 17090075Sobrien src = e->src; 17190075Sobrien dest = e->dest; 17290075Sobrien e->flags &= ~EDGE_DFS_BACK; 17390075Sobrien 17490075Sobrien /* Check if the edge destination has been visited yet. */ 17590075Sobrien if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 17690075Sobrien { 17790075Sobrien /* Mark that we have visited the destination. */ 17890075Sobrien SET_BIT (visited, dest->index); 17990075Sobrien 18090075Sobrien pre[dest->index] = prenum++; 18190075Sobrien if (dest->succ) 18290075Sobrien { 18390075Sobrien /* Since the DEST node has been visited for the first 18490075Sobrien time, check its successors. */ 18590075Sobrien stack[sp++] = dest->succ; 18690075Sobrien } 18790075Sobrien else 18890075Sobrien post[dest->index] = postnum++; 18990075Sobrien } 19090075Sobrien else 19190075Sobrien { 19290075Sobrien if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR 19390075Sobrien && pre[src->index] >= pre[dest->index] 19490075Sobrien && post[dest->index] == 0) 19590075Sobrien e->flags |= EDGE_DFS_BACK, found = true; 19690075Sobrien 19790075Sobrien if (! e->succ_next && src != ENTRY_BLOCK_PTR) 19890075Sobrien post[src->index] = postnum++; 19990075Sobrien 20090075Sobrien if (e->succ_next) 20190075Sobrien stack[sp - 1] = e->succ_next; 20290075Sobrien else 20390075Sobrien sp--; 20490075Sobrien } 20590075Sobrien } 20690075Sobrien 20790075Sobrien free (pre); 20890075Sobrien free (post); 20990075Sobrien free (stack); 21090075Sobrien sbitmap_free (visited); 21190075Sobrien 21290075Sobrien return found; 21390075Sobrien} 21490075Sobrien 215117395Skan/* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */ 216117395Skan 217117395Skanvoid 218117395Skanset_edge_can_fallthru_flag () 219117395Skan{ 220117395Skan basic_block bb; 221117395Skan 222117395Skan FOR_EACH_BB (bb) 223117395Skan { 224117395Skan edge e; 225117395Skan 226117395Skan for (e = bb->succ; e; e = e->succ_next) 227117395Skan { 228117395Skan e->flags &= ~EDGE_CAN_FALLTHRU; 229117395Skan 230117395Skan /* The FALLTHRU edge is also CAN_FALLTHRU edge. */ 231117395Skan if (e->flags & EDGE_FALLTHRU) 232117395Skan e->flags |= EDGE_CAN_FALLTHRU; 233117395Skan } 234117395Skan 235117395Skan /* If the BB ends with an invertable condjump all (2) edges are 236117395Skan CAN_FALLTHRU edges. */ 237117395Skan if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next) 238117395Skan continue; 239117395Skan if (!any_condjump_p (bb->end)) 240117395Skan continue; 241117395Skan if (!invert_jump (bb->end, JUMP_LABEL (bb->end), 0)) 242117395Skan continue; 243117395Skan invert_jump (bb->end, JUMP_LABEL (bb->end), 0); 244117395Skan bb->succ->flags |= EDGE_CAN_FALLTHRU; 245117395Skan bb->succ->succ_next->flags |= EDGE_CAN_FALLTHRU; 246117395Skan } 247117395Skan} 248117395Skan 24990075Sobrien/* Return true if we need to add fake edge to exit. 25090075Sobrien Helper function for the flow_call_edges_add. */ 25190075Sobrien 25290075Sobrienstatic bool 25390075Sobrienneed_fake_edge_p (insn) 25490075Sobrien rtx insn; 25590075Sobrien{ 25690075Sobrien if (!INSN_P (insn)) 25790075Sobrien return false; 25890075Sobrien 25990075Sobrien if ((GET_CODE (insn) == CALL_INSN 26090075Sobrien && !SIBLING_CALL_P (insn) 26190075Sobrien && !find_reg_note (insn, REG_NORETURN, NULL) 26290075Sobrien && !find_reg_note (insn, REG_ALWAYS_RETURN, NULL) 26390075Sobrien && !CONST_OR_PURE_CALL_P (insn))) 26490075Sobrien return true; 26590075Sobrien 26690075Sobrien return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS 26790075Sobrien && MEM_VOLATILE_P (PATTERN (insn))) 26890075Sobrien || (GET_CODE (PATTERN (insn)) == PARALLEL 26990075Sobrien && asm_noperands (insn) != -1 27090075Sobrien && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0))) 27190075Sobrien || GET_CODE (PATTERN (insn)) == ASM_INPUT); 27290075Sobrien} 27390075Sobrien 27490075Sobrien/* Add fake edges to the function exit for any non constant and non noreturn 27590075Sobrien calls, volatile inline assembly in the bitmap of blocks specified by 27690075Sobrien BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks 27790075Sobrien that were split. 27890075Sobrien 27990075Sobrien The goal is to expose cases in which entering a basic block does not imply 28090075Sobrien that all subsequent instructions must be executed. */ 28190075Sobrien 28290075Sobrienint 28390075Sobrienflow_call_edges_add (blocks) 28490075Sobrien sbitmap blocks; 28590075Sobrien{ 28690075Sobrien int i; 28790075Sobrien int blocks_split = 0; 288117395Skan int last_bb = last_basic_block; 28990075Sobrien bool check_last_block = false; 29090075Sobrien 291117395Skan if (n_basic_blocks == 0) 292117395Skan return 0; 29390075Sobrien 29490075Sobrien if (! blocks) 295117395Skan check_last_block = true; 29690075Sobrien else 297117395Skan check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index); 29890075Sobrien 29990075Sobrien /* In the last basic block, before epilogue generation, there will be 30090075Sobrien a fallthru edge to EXIT. Special care is required if the last insn 30190075Sobrien of the last basic block is a call because make_edge folds duplicate 30290075Sobrien edges, which would result in the fallthru edge also being marked 30390075Sobrien fake, which would result in the fallthru edge being removed by 30490075Sobrien remove_fake_edges, which would result in an invalid CFG. 30590075Sobrien 30690075Sobrien Moreover, we can't elide the outgoing fake edge, since the block 30790075Sobrien profiler needs to take this into account in order to solve the minimal 30890075Sobrien spanning tree in the case that the call doesn't return. 30990075Sobrien 31090075Sobrien Handle this by adding a dummy instruction in a new last basic block. */ 31196263Sobrien if (check_last_block) 31290075Sobrien { 313117395Skan basic_block bb = EXIT_BLOCK_PTR->prev_bb; 31496263Sobrien rtx insn = bb->end; 31590075Sobrien 31696263Sobrien /* Back up past insns that must be kept in the same block as a call. */ 31796263Sobrien while (insn != bb->head 31896263Sobrien && keep_with_call_p (insn)) 31996263Sobrien insn = PREV_INSN (insn); 32090075Sobrien 32196263Sobrien if (need_fake_edge_p (insn)) 32296263Sobrien { 32396263Sobrien edge e; 32496263Sobrien 32596263Sobrien for (e = bb->succ; e; e = e->succ_next) 32696263Sobrien if (e->dest == EXIT_BLOCK_PTR) 327110611Skan { 328110611Skan insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e); 329110611Skan commit_edge_insertions (); 330110611Skan break; 331110611Skan } 33296263Sobrien } 33390075Sobrien } 33490075Sobrien 33590075Sobrien /* Now add fake edges to the function exit for any non constant 33690075Sobrien calls since there is no way that we can determine if they will 33790075Sobrien return or not... */ 33890075Sobrien 339117395Skan for (i = 0; i < last_bb; i++) 34090075Sobrien { 341117395Skan basic_block bb = BASIC_BLOCK (i); 34290075Sobrien rtx insn; 34390075Sobrien rtx prev_insn; 34490075Sobrien 345117395Skan if (!bb) 346117395Skan continue; 347117395Skan 348117395Skan if (blocks && !TEST_BIT (blocks, i)) 349117395Skan continue; 350117395Skan 35190075Sobrien for (insn = bb->end; ; insn = prev_insn) 35290075Sobrien { 35390075Sobrien prev_insn = PREV_INSN (insn); 35490075Sobrien if (need_fake_edge_p (insn)) 35590075Sobrien { 35690075Sobrien edge e; 35796263Sobrien rtx split_at_insn = insn; 35890075Sobrien 35996263Sobrien /* Don't split the block between a call and an insn that should 36096263Sobrien remain in the same block as the call. */ 36196263Sobrien if (GET_CODE (insn) == CALL_INSN) 36296263Sobrien while (split_at_insn != bb->end 36396263Sobrien && keep_with_call_p (NEXT_INSN (split_at_insn))) 36496263Sobrien split_at_insn = NEXT_INSN (split_at_insn); 36590075Sobrien 36696263Sobrien /* The handling above of the final block before the epilogue 36796263Sobrien should be enough to verify that there is no edge to the exit 36896263Sobrien block in CFG already. Calling make_edge in such case would 36996263Sobrien cause us to mark that edge as fake and remove it later. */ 37096263Sobrien 37190075Sobrien#ifdef ENABLE_CHECKING 37296263Sobrien if (split_at_insn == bb->end) 37390075Sobrien for (e = bb->succ; e; e = e->succ_next) 37490075Sobrien if (e->dest == EXIT_BLOCK_PTR) 37590075Sobrien abort (); 37690075Sobrien#endif 37790075Sobrien 37890075Sobrien /* Note that the following may create a new basic block 37990075Sobrien and renumber the existing basic blocks. */ 380117395Skan if (split_at_insn != bb->end) 381117395Skan { 382117395Skan e = split_block (bb, split_at_insn); 383117395Skan if (e) 384117395Skan blocks_split++; 385117395Skan } 38690075Sobrien 38790075Sobrien make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 38890075Sobrien } 38990075Sobrien 39090075Sobrien if (insn == bb->head) 39190075Sobrien break; 39290075Sobrien } 39390075Sobrien } 39490075Sobrien 39590075Sobrien if (blocks_split) 39690075Sobrien verify_flow_info (); 39790075Sobrien 39890075Sobrien return blocks_split; 39990075Sobrien} 40090075Sobrien 40190075Sobrien/* Find unreachable blocks. An unreachable block will have 0 in 402117395Skan the reachable bit in block->flags. A nonzero value indicates the 40390075Sobrien block is reachable. */ 40490075Sobrien 40590075Sobrienvoid 40690075Sobrienfind_unreachable_blocks () 40790075Sobrien{ 40890075Sobrien edge e; 409117395Skan basic_block *tos, *worklist, bb; 41090075Sobrien 411117395Skan tos = worklist = 412117395Skan (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks); 41390075Sobrien 41490075Sobrien /* Clear all the reachability flags. */ 41590075Sobrien 416117395Skan FOR_EACH_BB (bb) 417117395Skan bb->flags &= ~BB_REACHABLE; 41890075Sobrien 41990075Sobrien /* Add our starting points to the worklist. Almost always there will 42090075Sobrien be only one. It isn't inconceivable that we might one day directly 42190075Sobrien support Fortran alternate entry points. */ 42290075Sobrien 42390075Sobrien for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) 42490075Sobrien { 42590075Sobrien *tos++ = e->dest; 42690075Sobrien 42790075Sobrien /* Mark the block reachable. */ 42890075Sobrien e->dest->flags |= BB_REACHABLE; 42990075Sobrien } 43090075Sobrien 43190075Sobrien /* Iterate: find everything reachable from what we've already seen. */ 43290075Sobrien 43390075Sobrien while (tos != worklist) 43490075Sobrien { 43590075Sobrien basic_block b = *--tos; 43690075Sobrien 43790075Sobrien for (e = b->succ; e; e = e->succ_next) 43890075Sobrien if (!(e->dest->flags & BB_REACHABLE)) 43990075Sobrien { 44090075Sobrien *tos++ = e->dest; 44190075Sobrien e->dest->flags |= BB_REACHABLE; 44290075Sobrien } 44390075Sobrien } 44490075Sobrien 44590075Sobrien free (worklist); 44690075Sobrien} 44790075Sobrien 44890075Sobrien/* Functions to access an edge list with a vector representation. 44990075Sobrien Enough data is kept such that given an index number, the 45090075Sobrien pred and succ that edge represents can be determined, or 45190075Sobrien given a pred and a succ, its index number can be returned. 45290075Sobrien This allows algorithms which consume a lot of memory to 45390075Sobrien represent the normally full matrix of edge (pred,succ) with a 45490075Sobrien single indexed vector, edge (EDGE_INDEX (pred, succ)), with no 45590075Sobrien wasted space in the client code due to sparse flow graphs. */ 45690075Sobrien 45790075Sobrien/* This functions initializes the edge list. Basically the entire 45890075Sobrien flowgraph is processed, and all edges are assigned a number, 45990075Sobrien and the data structure is filled in. */ 46090075Sobrien 46190075Sobrienstruct edge_list * 46290075Sobriencreate_edge_list () 46390075Sobrien{ 46490075Sobrien struct edge_list *elist; 46590075Sobrien edge e; 46690075Sobrien int num_edges; 46790075Sobrien int block_count; 468117395Skan basic_block bb; 46990075Sobrien 47090075Sobrien block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */ 47190075Sobrien 47290075Sobrien num_edges = 0; 47390075Sobrien 47490075Sobrien /* Determine the number of edges in the flow graph by counting successor 47590075Sobrien edges on each basic block. */ 476117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 47790075Sobrien { 47890075Sobrien for (e = bb->succ; e; e = e->succ_next) 47990075Sobrien num_edges++; 48090075Sobrien } 48190075Sobrien 48290075Sobrien elist = (struct edge_list *) xmalloc (sizeof (struct edge_list)); 48390075Sobrien elist->num_blocks = block_count; 48490075Sobrien elist->num_edges = num_edges; 48590075Sobrien elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges); 48690075Sobrien 48790075Sobrien num_edges = 0; 48890075Sobrien 489117395Skan /* Follow successors of blocks, and register these edges. */ 490117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 491117395Skan for (e = bb->succ; e; e = e->succ_next) 492117395Skan elist->index_to_edge[num_edges++] = e; 49390075Sobrien 49490075Sobrien return elist; 49590075Sobrien} 49690075Sobrien 49790075Sobrien/* This function free's memory associated with an edge list. */ 49890075Sobrien 49990075Sobrienvoid 50090075Sobrienfree_edge_list (elist) 50190075Sobrien struct edge_list *elist; 50290075Sobrien{ 50390075Sobrien if (elist) 50490075Sobrien { 50590075Sobrien free (elist->index_to_edge); 50690075Sobrien free (elist); 50790075Sobrien } 50890075Sobrien} 50990075Sobrien 51090075Sobrien/* This function provides debug output showing an edge list. */ 51190075Sobrien 51290075Sobrienvoid 51390075Sobrienprint_edge_list (f, elist) 51490075Sobrien FILE *f; 51590075Sobrien struct edge_list *elist; 51690075Sobrien{ 51790075Sobrien int x; 51890075Sobrien 51990075Sobrien fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n", 52090075Sobrien elist->num_blocks - 2, elist->num_edges); 52190075Sobrien 52290075Sobrien for (x = 0; x < elist->num_edges; x++) 52390075Sobrien { 52490075Sobrien fprintf (f, " %-4d - edge(", x); 52590075Sobrien if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR) 52690075Sobrien fprintf (f, "entry,"); 52790075Sobrien else 52890075Sobrien fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index); 52990075Sobrien 53090075Sobrien if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR) 53190075Sobrien fprintf (f, "exit)\n"); 53290075Sobrien else 53390075Sobrien fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index); 53490075Sobrien } 53590075Sobrien} 53690075Sobrien 53790075Sobrien/* This function provides an internal consistency check of an edge list, 53890075Sobrien verifying that all edges are present, and that there are no 53990075Sobrien extra edges. */ 54090075Sobrien 54190075Sobrienvoid 54290075Sobrienverify_edge_list (f, elist) 54390075Sobrien FILE *f; 54490075Sobrien struct edge_list *elist; 54590075Sobrien{ 546117395Skan int pred, succ, index; 54790075Sobrien edge e; 548117395Skan basic_block bb, p, s; 54990075Sobrien 550117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 55190075Sobrien { 55290075Sobrien for (e = bb->succ; e; e = e->succ_next) 55390075Sobrien { 55490075Sobrien pred = e->src->index; 55590075Sobrien succ = e->dest->index; 55690075Sobrien index = EDGE_INDEX (elist, e->src, e->dest); 55790075Sobrien if (index == EDGE_INDEX_NO_EDGE) 55890075Sobrien { 55990075Sobrien fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ); 56090075Sobrien continue; 56190075Sobrien } 56290075Sobrien 56390075Sobrien if (INDEX_EDGE_PRED_BB (elist, index)->index != pred) 56490075Sobrien fprintf (f, "*p* Pred for index %d should be %d not %d\n", 56590075Sobrien index, pred, INDEX_EDGE_PRED_BB (elist, index)->index); 56690075Sobrien if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ) 56790075Sobrien fprintf (f, "*p* Succ for index %d should be %d not %d\n", 56890075Sobrien index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index); 56990075Sobrien } 57090075Sobrien } 57190075Sobrien 572117395Skan /* We've verified that all the edges are in the list, now lets make sure 57390075Sobrien there are no spurious edges in the list. */ 57490075Sobrien 575117395Skan FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 576117395Skan FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) 57790075Sobrien { 57890075Sobrien int found_edge = 0; 57990075Sobrien 58090075Sobrien for (e = p->succ; e; e = e->succ_next) 58190075Sobrien if (e->dest == s) 58290075Sobrien { 58390075Sobrien found_edge = 1; 58490075Sobrien break; 58590075Sobrien } 58690075Sobrien 58790075Sobrien for (e = s->pred; e; e = e->pred_next) 58890075Sobrien if (e->src == p) 58990075Sobrien { 59090075Sobrien found_edge = 1; 59190075Sobrien break; 59290075Sobrien } 59390075Sobrien 594117395Skan if (EDGE_INDEX (elist, p, s) 59590075Sobrien == EDGE_INDEX_NO_EDGE && found_edge != 0) 59690075Sobrien fprintf (f, "*** Edge (%d, %d) appears to not have an index\n", 597117395Skan p->index, s->index); 598117395Skan if (EDGE_INDEX (elist, p, s) 59990075Sobrien != EDGE_INDEX_NO_EDGE && found_edge == 0) 60090075Sobrien fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n", 601117395Skan p->index, s->index, EDGE_INDEX (elist, p, s)); 60290075Sobrien } 60390075Sobrien} 60490075Sobrien 60590075Sobrien/* This routine will determine what, if any, edge there is between 60690075Sobrien a specified predecessor and successor. */ 60790075Sobrien 60890075Sobrienint 60990075Sobrienfind_edge_index (edge_list, pred, succ) 61090075Sobrien struct edge_list *edge_list; 61190075Sobrien basic_block pred, succ; 61290075Sobrien{ 61390075Sobrien int x; 61490075Sobrien 61590075Sobrien for (x = 0; x < NUM_EDGES (edge_list); x++) 61690075Sobrien if (INDEX_EDGE_PRED_BB (edge_list, x) == pred 61790075Sobrien && INDEX_EDGE_SUCC_BB (edge_list, x) == succ) 61890075Sobrien return x; 61990075Sobrien 62090075Sobrien return (EDGE_INDEX_NO_EDGE); 62190075Sobrien} 62290075Sobrien 62390075Sobrien/* Dump the list of basic blocks in the bitmap NODES. */ 62490075Sobrien 62590075Sobrienvoid 62690075Sobrienflow_nodes_print (str, nodes, file) 62790075Sobrien const char *str; 62890075Sobrien const sbitmap nodes; 62990075Sobrien FILE *file; 63090075Sobrien{ 63190075Sobrien int node; 63290075Sobrien 63390075Sobrien if (! nodes) 63490075Sobrien return; 63590075Sobrien 63690075Sobrien fprintf (file, "%s { ", str); 63790075Sobrien EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);}); 63890075Sobrien fputs ("}\n", file); 63990075Sobrien} 64090075Sobrien 64190075Sobrien/* Dump the list of edges in the array EDGE_LIST. */ 64290075Sobrien 64390075Sobrienvoid 64490075Sobrienflow_edge_list_print (str, edge_list, num_edges, file) 64590075Sobrien const char *str; 64690075Sobrien const edge *edge_list; 64790075Sobrien int num_edges; 64890075Sobrien FILE *file; 64990075Sobrien{ 65090075Sobrien int i; 65190075Sobrien 65290075Sobrien if (! edge_list) 65390075Sobrien return; 65490075Sobrien 65590075Sobrien fprintf (file, "%s { ", str); 65690075Sobrien for (i = 0; i < num_edges; i++) 65790075Sobrien fprintf (file, "%d->%d ", edge_list[i]->src->index, 65890075Sobrien edge_list[i]->dest->index); 65990075Sobrien 66090075Sobrien fputs ("}\n", file); 66190075Sobrien} 66290075Sobrien 66390075Sobrien 66490075Sobrien/* This routine will remove any fake successor edges for a basic block. 66590075Sobrien When the edge is removed, it is also removed from whatever predecessor 66690075Sobrien list it is in. */ 66790075Sobrien 66890075Sobrienstatic void 66990075Sobrienremove_fake_successors (bb) 67090075Sobrien basic_block bb; 67190075Sobrien{ 67290075Sobrien edge e; 67390075Sobrien 67490075Sobrien for (e = bb->succ; e;) 67590075Sobrien { 67690075Sobrien edge tmp = e; 67790075Sobrien 67890075Sobrien e = e->succ_next; 67990075Sobrien if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE) 68090075Sobrien remove_edge (tmp); 68190075Sobrien } 68290075Sobrien} 68390075Sobrien 68490075Sobrien/* This routine will remove all fake edges from the flow graph. If 68590075Sobrien we remove all fake successors, it will automatically remove all 68690075Sobrien fake predecessors. */ 68790075Sobrien 68890075Sobrienvoid 68990075Sobrienremove_fake_edges () 69090075Sobrien{ 691117395Skan basic_block bb; 69290075Sobrien 693117395Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb) 694117395Skan remove_fake_successors (bb); 69590075Sobrien} 69690075Sobrien 69790075Sobrien/* This function will add a fake edge between any block which has no 69890075Sobrien successors, and the exit block. Some data flow equations require these 69990075Sobrien edges to exist. */ 70090075Sobrien 70190075Sobrienvoid 70290075Sobrienadd_noreturn_fake_exit_edges () 70390075Sobrien{ 704117395Skan basic_block bb; 70590075Sobrien 706117395Skan FOR_EACH_BB (bb) 707117395Skan if (bb->succ == NULL) 708117395Skan make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 70990075Sobrien} 71090075Sobrien 71190075Sobrien/* This function adds a fake edge between any infinite loops to the 71290075Sobrien exit block. Some optimizations require a path from each node to 71390075Sobrien the exit node. 71490075Sobrien 71590075Sobrien See also Morgan, Figure 3.10, pp. 82-83. 71690075Sobrien 71790075Sobrien The current implementation is ugly, not attempting to minimize the 71890075Sobrien number of inserted fake edges. To reduce the number of fake edges 71990075Sobrien to insert, add fake edges from _innermost_ loops containing only 72090075Sobrien nodes not reachable from the exit block. */ 72190075Sobrien 72290075Sobrienvoid 72390075Sobrienconnect_infinite_loops_to_exit () 72490075Sobrien{ 72590075Sobrien basic_block unvisited_block; 72690075Sobrien struct depth_first_search_dsS dfs_ds; 72790075Sobrien 72890075Sobrien /* Perform depth-first search in the reverse graph to find nodes 72990075Sobrien reachable from the exit block. */ 73090075Sobrien flow_dfs_compute_reverse_init (&dfs_ds); 73190075Sobrien flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR); 73290075Sobrien 73390075Sobrien /* Repeatedly add fake edges, updating the unreachable nodes. */ 73490075Sobrien while (1) 73590075Sobrien { 73690075Sobrien unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds); 73790075Sobrien if (!unvisited_block) 73890075Sobrien break; 73990075Sobrien 74090075Sobrien make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE); 74190075Sobrien flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block); 74290075Sobrien } 74390075Sobrien 74490075Sobrien flow_dfs_compute_reverse_finish (&dfs_ds); 74590075Sobrien return; 74690075Sobrien} 74790075Sobrien 74890075Sobrien/* Compute reverse top sort order */ 74990075Sobrien 75090075Sobrienvoid 75190075Sobrienflow_reverse_top_sort_order_compute (rts_order) 75290075Sobrien int *rts_order; 75390075Sobrien{ 75490075Sobrien edge *stack; 75590075Sobrien int sp; 75690075Sobrien int postnum = 0; 75790075Sobrien sbitmap visited; 75890075Sobrien 75990075Sobrien /* Allocate stack for back-tracking up CFG. */ 76090075Sobrien stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); 76190075Sobrien sp = 0; 76290075Sobrien 76390075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 764117395Skan visited = sbitmap_alloc (last_basic_block); 76590075Sobrien 76690075Sobrien /* None of the nodes in the CFG have been visited yet. */ 76790075Sobrien sbitmap_zero (visited); 76890075Sobrien 76990075Sobrien /* Push the first edge on to the stack. */ 77090075Sobrien stack[sp++] = ENTRY_BLOCK_PTR->succ; 77190075Sobrien 77290075Sobrien while (sp) 77390075Sobrien { 77490075Sobrien edge e; 77590075Sobrien basic_block src; 77690075Sobrien basic_block dest; 77790075Sobrien 77890075Sobrien /* Look at the edge on the top of the stack. */ 77990075Sobrien e = stack[sp - 1]; 78090075Sobrien src = e->src; 78190075Sobrien dest = e->dest; 78290075Sobrien 78390075Sobrien /* Check if the edge destination has been visited yet. */ 78490075Sobrien if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 78590075Sobrien { 78690075Sobrien /* Mark that we have visited the destination. */ 78790075Sobrien SET_BIT (visited, dest->index); 78890075Sobrien 78990075Sobrien if (dest->succ) 79090075Sobrien /* Since the DEST node has been visited for the first 79190075Sobrien time, check its successors. */ 79290075Sobrien stack[sp++] = dest->succ; 79390075Sobrien else 79490075Sobrien rts_order[postnum++] = dest->index; 79590075Sobrien } 79690075Sobrien else 79790075Sobrien { 79890075Sobrien if (! e->succ_next && src != ENTRY_BLOCK_PTR) 79990075Sobrien rts_order[postnum++] = src->index; 80090075Sobrien 80190075Sobrien if (e->succ_next) 80290075Sobrien stack[sp - 1] = e->succ_next; 80390075Sobrien else 80490075Sobrien sp--; 80590075Sobrien } 80690075Sobrien } 80790075Sobrien 80890075Sobrien free (stack); 80990075Sobrien sbitmap_free (visited); 81090075Sobrien} 81190075Sobrien 81290075Sobrien/* Compute the depth first search order and store in the array 813117395Skan DFS_ORDER if nonzero, marking the nodes visited in VISITED. If 814117395Skan RC_ORDER is nonzero, return the reverse completion number for each 81590075Sobrien node. Returns the number of nodes visited. A depth first search 81690075Sobrien tries to get as far away from the starting point as quickly as 81790075Sobrien possible. */ 81890075Sobrien 81990075Sobrienint 82090075Sobrienflow_depth_first_order_compute (dfs_order, rc_order) 82190075Sobrien int *dfs_order; 82290075Sobrien int *rc_order; 82390075Sobrien{ 82490075Sobrien edge *stack; 82590075Sobrien int sp; 82690075Sobrien int dfsnum = 0; 82790075Sobrien int rcnum = n_basic_blocks - 1; 82890075Sobrien sbitmap visited; 82990075Sobrien 83090075Sobrien /* Allocate stack for back-tracking up CFG. */ 83190075Sobrien stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); 83290075Sobrien sp = 0; 83390075Sobrien 83490075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 835117395Skan visited = sbitmap_alloc (last_basic_block); 83690075Sobrien 83790075Sobrien /* None of the nodes in the CFG have been visited yet. */ 83890075Sobrien sbitmap_zero (visited); 83990075Sobrien 84090075Sobrien /* Push the first edge on to the stack. */ 84190075Sobrien stack[sp++] = ENTRY_BLOCK_PTR->succ; 84290075Sobrien 84390075Sobrien while (sp) 84490075Sobrien { 84590075Sobrien edge e; 84690075Sobrien basic_block src; 84790075Sobrien basic_block dest; 84890075Sobrien 84990075Sobrien /* Look at the edge on the top of the stack. */ 85090075Sobrien e = stack[sp - 1]; 85190075Sobrien src = e->src; 85290075Sobrien dest = e->dest; 85390075Sobrien 85490075Sobrien /* Check if the edge destination has been visited yet. */ 85590075Sobrien if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 85690075Sobrien { 85790075Sobrien /* Mark that we have visited the destination. */ 85890075Sobrien SET_BIT (visited, dest->index); 85990075Sobrien 86090075Sobrien if (dfs_order) 86190075Sobrien dfs_order[dfsnum] = dest->index; 86290075Sobrien 86390075Sobrien dfsnum++; 86490075Sobrien 86590075Sobrien if (dest->succ) 86690075Sobrien /* Since the DEST node has been visited for the first 86790075Sobrien time, check its successors. */ 86890075Sobrien stack[sp++] = dest->succ; 86990075Sobrien else if (rc_order) 87090075Sobrien /* There are no successors for the DEST node so assign 87190075Sobrien its reverse completion number. */ 87290075Sobrien rc_order[rcnum--] = dest->index; 87390075Sobrien } 87490075Sobrien else 87590075Sobrien { 87690075Sobrien if (! e->succ_next && src != ENTRY_BLOCK_PTR 87790075Sobrien && rc_order) 87890075Sobrien /* There are no more successors for the SRC node 87990075Sobrien so assign its reverse completion number. */ 88090075Sobrien rc_order[rcnum--] = src->index; 88190075Sobrien 88290075Sobrien if (e->succ_next) 88390075Sobrien stack[sp - 1] = e->succ_next; 88490075Sobrien else 88590075Sobrien sp--; 88690075Sobrien } 88790075Sobrien } 88890075Sobrien 88990075Sobrien free (stack); 89090075Sobrien sbitmap_free (visited); 89190075Sobrien 89290075Sobrien /* The number of nodes visited should not be greater than 89390075Sobrien n_basic_blocks. */ 89490075Sobrien if (dfsnum > n_basic_blocks) 89590075Sobrien abort (); 89690075Sobrien 89790075Sobrien /* There are some nodes left in the CFG that are unreachable. */ 89890075Sobrien if (dfsnum < n_basic_blocks) 89990075Sobrien abort (); 90090075Sobrien 90190075Sobrien return dfsnum; 90290075Sobrien} 90390075Sobrien 90490075Sobrienstruct dfst_node 90590075Sobrien{ 90690075Sobrien unsigned nnodes; 90790075Sobrien struct dfst_node **node; 90890075Sobrien struct dfst_node *up; 90990075Sobrien}; 91090075Sobrien 91190075Sobrien/* Compute a preorder transversal ordering such that a sub-tree which 91290075Sobrien is the source of a cross edge appears before the sub-tree which is 91390075Sobrien the destination of the cross edge. This allows for easy detection 91490075Sobrien of all the entry blocks for a loop. 91590075Sobrien 91690075Sobrien The ordering is compute by: 91790075Sobrien 91890075Sobrien 1) Generating a depth first spanning tree. 91990075Sobrien 92090075Sobrien 2) Walking the resulting tree from right to left. */ 92190075Sobrien 92290075Sobrienvoid 92390075Sobrienflow_preorder_transversal_compute (pot_order) 92490075Sobrien int *pot_order; 92590075Sobrien{ 92690075Sobrien edge e; 92790075Sobrien edge *stack; 92890075Sobrien int i; 92990075Sobrien int max_successors; 93090075Sobrien int sp; 93190075Sobrien sbitmap visited; 93290075Sobrien struct dfst_node *node; 93390075Sobrien struct dfst_node *dfst; 934117395Skan basic_block bb; 93590075Sobrien 93690075Sobrien /* Allocate stack for back-tracking up CFG. */ 93790075Sobrien stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); 93890075Sobrien sp = 0; 93990075Sobrien 94090075Sobrien /* Allocate the tree. */ 941117395Skan dfst = (struct dfst_node *) xcalloc (last_basic_block, 94290075Sobrien sizeof (struct dfst_node)); 94390075Sobrien 944117395Skan FOR_EACH_BB (bb) 94590075Sobrien { 94690075Sobrien max_successors = 0; 947117395Skan for (e = bb->succ; e; e = e->succ_next) 94890075Sobrien max_successors++; 94990075Sobrien 950117395Skan dfst[bb->index].node 95190075Sobrien = (max_successors 95290075Sobrien ? (struct dfst_node **) xcalloc (max_successors, 95390075Sobrien sizeof (struct dfst_node *)) 95490075Sobrien : NULL); 95590075Sobrien } 95690075Sobrien 95790075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 958117395Skan visited = sbitmap_alloc (last_basic_block); 95990075Sobrien 96090075Sobrien /* None of the nodes in the CFG have been visited yet. */ 96190075Sobrien sbitmap_zero (visited); 96290075Sobrien 96390075Sobrien /* Push the first edge on to the stack. */ 96490075Sobrien stack[sp++] = ENTRY_BLOCK_PTR->succ; 96590075Sobrien 96690075Sobrien while (sp) 96790075Sobrien { 96890075Sobrien basic_block src; 96990075Sobrien basic_block dest; 97090075Sobrien 97190075Sobrien /* Look at the edge on the top of the stack. */ 97290075Sobrien e = stack[sp - 1]; 97390075Sobrien src = e->src; 97490075Sobrien dest = e->dest; 97590075Sobrien 97690075Sobrien /* Check if the edge destination has been visited yet. */ 97790075Sobrien if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 97890075Sobrien { 97990075Sobrien /* Mark that we have visited the destination. */ 98090075Sobrien SET_BIT (visited, dest->index); 98190075Sobrien 98290075Sobrien /* Add the destination to the preorder tree. */ 98390075Sobrien if (src != ENTRY_BLOCK_PTR) 98490075Sobrien { 98590075Sobrien dfst[src->index].node[dfst[src->index].nnodes++] 98690075Sobrien = &dfst[dest->index]; 98790075Sobrien dfst[dest->index].up = &dfst[src->index]; 98890075Sobrien } 98990075Sobrien 99090075Sobrien if (dest->succ) 99190075Sobrien /* Since the DEST node has been visited for the first 99290075Sobrien time, check its successors. */ 99390075Sobrien stack[sp++] = dest->succ; 99490075Sobrien } 99590075Sobrien 99690075Sobrien else if (e->succ_next) 99790075Sobrien stack[sp - 1] = e->succ_next; 99890075Sobrien else 99990075Sobrien sp--; 100090075Sobrien } 100190075Sobrien 100290075Sobrien free (stack); 100390075Sobrien sbitmap_free (visited); 100490075Sobrien 100590075Sobrien /* Record the preorder transversal order by 100690075Sobrien walking the tree from right to left. */ 100790075Sobrien 100890075Sobrien i = 0; 1009117395Skan node = &dfst[ENTRY_BLOCK_PTR->next_bb->index]; 101090075Sobrien pot_order[i++] = 0; 101190075Sobrien 101290075Sobrien while (node) 101390075Sobrien { 101490075Sobrien if (node->nnodes) 101590075Sobrien { 101690075Sobrien node = node->node[--node->nnodes]; 101790075Sobrien pot_order[i++] = node - dfst; 101890075Sobrien } 101990075Sobrien else 102090075Sobrien node = node->up; 102190075Sobrien } 102290075Sobrien 102390075Sobrien /* Free the tree. */ 102490075Sobrien 1025117395Skan for (i = 0; i < last_basic_block; i++) 102690075Sobrien if (dfst[i].node) 102790075Sobrien free (dfst[i].node); 102890075Sobrien 102990075Sobrien free (dfst); 103090075Sobrien} 103190075Sobrien 103290075Sobrien/* Compute the depth first search order on the _reverse_ graph and 103390075Sobrien store in the array DFS_ORDER, marking the nodes visited in VISITED. 103490075Sobrien Returns the number of nodes visited. 103590075Sobrien 103690075Sobrien The computation is split into three pieces: 103790075Sobrien 103890075Sobrien flow_dfs_compute_reverse_init () creates the necessary data 103990075Sobrien structures. 104090075Sobrien 104190075Sobrien flow_dfs_compute_reverse_add_bb () adds a basic block to the data 104290075Sobrien structures. The block will start the search. 104390075Sobrien 104490075Sobrien flow_dfs_compute_reverse_execute () continues (or starts) the 104590075Sobrien search using the block on the top of the stack, stopping when the 104690075Sobrien stack is empty. 104790075Sobrien 104890075Sobrien flow_dfs_compute_reverse_finish () destroys the necessary data 104990075Sobrien structures. 105090075Sobrien 105190075Sobrien Thus, the user will probably call ..._init(), call ..._add_bb() to 105290075Sobrien add a beginning basic block to the stack, call ..._execute(), 105390075Sobrien possibly add another bb to the stack and again call ..._execute(), 105490075Sobrien ..., and finally call _finish(). */ 105590075Sobrien 105690075Sobrien/* Initialize the data structures used for depth-first search on the 105790075Sobrien reverse graph. If INITIALIZE_STACK is nonzero, the exit block is 105890075Sobrien added to the basic block stack. DATA is the current depth-first 1059117395Skan search context. If INITIALIZE_STACK is nonzero, there is an 106090075Sobrien element on the stack. */ 106190075Sobrien 106290075Sobrienstatic void 106390075Sobrienflow_dfs_compute_reverse_init (data) 106490075Sobrien depth_first_search_ds data; 106590075Sobrien{ 106690075Sobrien /* Allocate stack for back-tracking up CFG. */ 106790075Sobrien data->stack = (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1)) 106890075Sobrien * sizeof (basic_block)); 106990075Sobrien data->sp = 0; 107090075Sobrien 107190075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 1072117395Skan data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1)); 107390075Sobrien 107490075Sobrien /* None of the nodes in the CFG have been visited yet. */ 107590075Sobrien sbitmap_zero (data->visited_blocks); 107690075Sobrien 107790075Sobrien return; 107890075Sobrien} 107990075Sobrien 108090075Sobrien/* Add the specified basic block to the top of the dfs data 108190075Sobrien structures. When the search continues, it will start at the 108290075Sobrien block. */ 108390075Sobrien 108490075Sobrienstatic void 108590075Sobrienflow_dfs_compute_reverse_add_bb (data, bb) 108690075Sobrien depth_first_search_ds data; 108790075Sobrien basic_block bb; 108890075Sobrien{ 108990075Sobrien data->stack[data->sp++] = bb; 109090075Sobrien SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)); 109190075Sobrien} 109290075Sobrien 109390075Sobrien/* Continue the depth-first search through the reverse graph starting with the 109490075Sobrien block at the stack's top and ending when the stack is empty. Visited nodes 109590075Sobrien are marked. Returns an unvisited basic block, or NULL if there is none 109690075Sobrien available. */ 109790075Sobrien 109890075Sobrienstatic basic_block 109990075Sobrienflow_dfs_compute_reverse_execute (data) 110090075Sobrien depth_first_search_ds data; 110190075Sobrien{ 110290075Sobrien basic_block bb; 110390075Sobrien edge e; 110490075Sobrien 110590075Sobrien while (data->sp > 0) 110690075Sobrien { 110790075Sobrien bb = data->stack[--data->sp]; 110890075Sobrien 110990075Sobrien /* Perform depth-first search on adjacent vertices. */ 111090075Sobrien for (e = bb->pred; e; e = e->pred_next) 111190075Sobrien if (!TEST_BIT (data->visited_blocks, 111290075Sobrien e->src->index - (INVALID_BLOCK + 1))) 111390075Sobrien flow_dfs_compute_reverse_add_bb (data, e->src); 111490075Sobrien } 111590075Sobrien 111690075Sobrien /* Determine if there are unvisited basic blocks. */ 1117117395Skan FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb) 1118117395Skan if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1))) 1119117395Skan return bb; 112090075Sobrien 112190075Sobrien return NULL; 112290075Sobrien} 112390075Sobrien 112490075Sobrien/* Destroy the data structures needed for depth-first search on the 112590075Sobrien reverse graph. */ 112690075Sobrien 112790075Sobrienstatic void 112890075Sobrienflow_dfs_compute_reverse_finish (data) 112990075Sobrien depth_first_search_ds data; 113090075Sobrien{ 113190075Sobrien free (data->stack); 113290075Sobrien sbitmap_free (data->visited_blocks); 113390075Sobrien} 1134117395Skan 1135117395Skan/* Performs dfs search from BB over vertices satisfying PREDICATE; 1136117395Skan if REVERSE, go against direction of edges. Returns number of blocks 1137117395Skan found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */ 1138117395Skanint 1139117395Skandfs_enumerate_from (bb, reverse, predicate, rslt, rslt_max, data) 1140117395Skan basic_block bb; 1141117395Skan int reverse; 1142117395Skan bool (*predicate) PARAMS ((basic_block, void *)); 1143117395Skan basic_block *rslt; 1144117395Skan int rslt_max; 1145117395Skan void *data; 1146117395Skan{ 1147117395Skan basic_block *st, lbb; 1148117395Skan int sp = 0, tv = 0; 1149117395Skan 1150117395Skan st = xcalloc (rslt_max, sizeof (basic_block)); 1151117395Skan rslt[tv++] = st[sp++] = bb; 1152117395Skan bb->flags |= BB_VISITED; 1153117395Skan while (sp) 1154117395Skan { 1155117395Skan edge e; 1156117395Skan lbb = st[--sp]; 1157117395Skan if (reverse) 1158117395Skan { 1159117395Skan for (e = lbb->pred; e; e = e->pred_next) 1160117395Skan if (!(e->src->flags & BB_VISITED) && predicate (e->src, data)) 1161117395Skan { 1162117395Skan if (tv == rslt_max) 1163117395Skan abort (); 1164117395Skan rslt[tv++] = st[sp++] = e->src; 1165117395Skan e->src->flags |= BB_VISITED; 1166117395Skan } 1167117395Skan } 1168117395Skan else 1169117395Skan { 1170117395Skan for (e = lbb->succ; e; e = e->succ_next) 1171117395Skan if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data)) 1172117395Skan { 1173117395Skan if (tv == rslt_max) 1174117395Skan abort (); 1175117395Skan rslt[tv++] = st[sp++] = e->dest; 1176117395Skan e->dest->flags |= BB_VISITED; 1177117395Skan } 1178117395Skan } 1179117395Skan } 1180117395Skan free (st); 1181117395Skan for (sp = 0; sp < tv; sp++) 1182117395Skan rslt[sp]->flags &= ~BB_VISITED; 1183117395Skan return tv; 1184117395Skan} 1185