cfganal.c revision 107590
190075Sobrien/* Control flow graph analysis code for GNU compiler. 290075Sobrien Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 390075Sobrien 1999, 2000, 2001 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" 3190075Sobrien#include "obstack.h" 3296263Sobrien#include "tm_p.h" 3390075Sobrien 3490075Sobrien/* Store the data structures necessary for depth-first search. */ 3590075Sobrienstruct depth_first_search_dsS { 3690075Sobrien /* stack for backtracking during the algorithm */ 3790075Sobrien basic_block *stack; 3890075Sobrien 3990075Sobrien /* number of edges in the stack. That is, positions 0, ..., sp-1 4090075Sobrien have edges. */ 4190075Sobrien unsigned int sp; 4290075Sobrien 4390075Sobrien /* record of basic blocks already seen by depth-first search */ 4490075Sobrien sbitmap visited_blocks; 4590075Sobrien}; 4690075Sobrientypedef struct depth_first_search_dsS *depth_first_search_ds; 4790075Sobrien 4890075Sobrienstatic void flow_dfs_compute_reverse_init 4990075Sobrien PARAMS ((depth_first_search_ds)); 5090075Sobrienstatic void flow_dfs_compute_reverse_add_bb 5190075Sobrien PARAMS ((depth_first_search_ds, basic_block)); 5290075Sobrienstatic basic_block flow_dfs_compute_reverse_execute 5390075Sobrien PARAMS ((depth_first_search_ds)); 5490075Sobrienstatic void flow_dfs_compute_reverse_finish 5590075Sobrien PARAMS ((depth_first_search_ds)); 5690075Sobrienstatic void remove_fake_successors PARAMS ((basic_block)); 5790075Sobrienstatic bool need_fake_edge_p PARAMS ((rtx)); 5896263Sobrienstatic bool keep_with_call_p PARAMS ((rtx)); 59107590Sobrienstatic bool flow_active_insn_p PARAMS ((rtx)); 6090075Sobrien 61107590Sobrien/* Like active_insn_p, except keep the return value clobber around 62107590Sobrien even after reload. */ 63107590Sobrien 64107590Sobrienstatic bool 65107590Sobrienflow_active_insn_p (insn) 66107590Sobrien rtx insn; 67107590Sobrien{ 68107590Sobrien if (active_insn_p (insn)) 69107590Sobrien return true; 70107590Sobrien 71107590Sobrien /* A clobber of the function return value exists for buggy 72107590Sobrien programs that fail to return a value. It's effect is to 73107590Sobrien keep the return value from being live across the entire 74107590Sobrien function. If we allow it to be skipped, we introduce the 75107590Sobrien possibility for register livetime aborts. */ 76107590Sobrien if (GET_CODE (PATTERN (insn)) == CLOBBER 77107590Sobrien && GET_CODE (XEXP (PATTERN (insn), 0)) == REG 78107590Sobrien && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0))) 79107590Sobrien return true; 80107590Sobrien 81107590Sobrien return false; 82107590Sobrien} 83107590Sobrien 8490075Sobrien/* Return true if the block has no effect and only forwards control flow to 8590075Sobrien its single destination. */ 8690075Sobrien 8790075Sobrienbool 8890075Sobrienforwarder_block_p (bb) 8990075Sobrien basic_block bb; 9090075Sobrien{ 9190075Sobrien rtx insn; 9290075Sobrien 9390075Sobrien if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR 9490075Sobrien || !bb->succ || bb->succ->succ_next) 9590075Sobrien return false; 9690075Sobrien 9790075Sobrien for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn)) 98107590Sobrien if (INSN_P (insn) && flow_active_insn_p (insn)) 9990075Sobrien return false; 10090075Sobrien 10190075Sobrien return (!INSN_P (insn) 10290075Sobrien || (GET_CODE (insn) == JUMP_INSN && simplejump_p (insn)) 103107590Sobrien || !flow_active_insn_p (insn)); 10490075Sobrien} 10590075Sobrien 10690075Sobrien/* Return nonzero if we can reach target from src by falling through. */ 10790075Sobrien 10890075Sobrienbool 10990075Sobriencan_fallthru (src, target) 11090075Sobrien basic_block src, target; 11190075Sobrien{ 11290075Sobrien rtx insn = src->end; 11390075Sobrien rtx insn2 = target->head; 11490075Sobrien 11590075Sobrien if (src->index + 1 == target->index && !active_insn_p (insn2)) 11690075Sobrien insn2 = next_active_insn (insn2); 11790075Sobrien 11890075Sobrien /* ??? Later we may add code to move jump tables offline. */ 11990075Sobrien return next_active_insn (insn) == insn2; 12090075Sobrien} 12190075Sobrien 12290075Sobrien/* Mark the back edges in DFS traversal. 12390075Sobrien Return non-zero if a loop (natural or otherwise) is present. 12490075Sobrien Inspired by Depth_First_Search_PP described in: 12590075Sobrien 12690075Sobrien Advanced Compiler Design and Implementation 12790075Sobrien Steven Muchnick 12890075Sobrien Morgan Kaufmann, 1997 12990075Sobrien 13090075Sobrien and heavily borrowed from flow_depth_first_order_compute. */ 13190075Sobrien 13290075Sobrienbool 13390075Sobrienmark_dfs_back_edges () 13490075Sobrien{ 13590075Sobrien edge *stack; 13690075Sobrien int *pre; 13790075Sobrien int *post; 13890075Sobrien int sp; 13990075Sobrien int prenum = 1; 14090075Sobrien int postnum = 1; 14190075Sobrien sbitmap visited; 14290075Sobrien bool found = false; 14390075Sobrien 14490075Sobrien /* Allocate the preorder and postorder number arrays. */ 14590075Sobrien pre = (int *) xcalloc (n_basic_blocks, sizeof (int)); 14690075Sobrien post = (int *) xcalloc (n_basic_blocks, sizeof (int)); 14790075Sobrien 14890075Sobrien /* Allocate stack for back-tracking up CFG. */ 14990075Sobrien stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); 15090075Sobrien sp = 0; 15190075Sobrien 15290075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 15390075Sobrien visited = sbitmap_alloc (n_basic_blocks); 15490075Sobrien 15590075Sobrien /* None of the nodes in the CFG have been visited yet. */ 15690075Sobrien sbitmap_zero (visited); 15790075Sobrien 15890075Sobrien /* Push the first edge on to the stack. */ 15990075Sobrien stack[sp++] = ENTRY_BLOCK_PTR->succ; 16090075Sobrien 16190075Sobrien while (sp) 16290075Sobrien { 16390075Sobrien edge e; 16490075Sobrien basic_block src; 16590075Sobrien basic_block dest; 16690075Sobrien 16790075Sobrien /* Look at the edge on the top of the stack. */ 16890075Sobrien e = stack[sp - 1]; 16990075Sobrien src = e->src; 17090075Sobrien dest = e->dest; 17190075Sobrien e->flags &= ~EDGE_DFS_BACK; 17290075Sobrien 17390075Sobrien /* Check if the edge destination has been visited yet. */ 17490075Sobrien if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 17590075Sobrien { 17690075Sobrien /* Mark that we have visited the destination. */ 17790075Sobrien SET_BIT (visited, dest->index); 17890075Sobrien 17990075Sobrien pre[dest->index] = prenum++; 18090075Sobrien if (dest->succ) 18190075Sobrien { 18290075Sobrien /* Since the DEST node has been visited for the first 18390075Sobrien time, check its successors. */ 18490075Sobrien stack[sp++] = dest->succ; 18590075Sobrien } 18690075Sobrien else 18790075Sobrien post[dest->index] = postnum++; 18890075Sobrien } 18990075Sobrien else 19090075Sobrien { 19190075Sobrien if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR 19290075Sobrien && pre[src->index] >= pre[dest->index] 19390075Sobrien && post[dest->index] == 0) 19490075Sobrien e->flags |= EDGE_DFS_BACK, found = true; 19590075Sobrien 19690075Sobrien if (! e->succ_next && src != ENTRY_BLOCK_PTR) 19790075Sobrien post[src->index] = postnum++; 19890075Sobrien 19990075Sobrien if (e->succ_next) 20090075Sobrien stack[sp - 1] = e->succ_next; 20190075Sobrien else 20290075Sobrien sp--; 20390075Sobrien } 20490075Sobrien } 20590075Sobrien 20690075Sobrien free (pre); 20790075Sobrien free (post); 20890075Sobrien free (stack); 20990075Sobrien sbitmap_free (visited); 21090075Sobrien 21190075Sobrien return found; 21290075Sobrien} 21390075Sobrien 21490075Sobrien/* Return true if we need to add fake edge to exit. 21590075Sobrien Helper function for the flow_call_edges_add. */ 21690075Sobrien 21790075Sobrienstatic bool 21890075Sobrienneed_fake_edge_p (insn) 21990075Sobrien rtx insn; 22090075Sobrien{ 22190075Sobrien if (!INSN_P (insn)) 22290075Sobrien return false; 22390075Sobrien 22490075Sobrien if ((GET_CODE (insn) == CALL_INSN 22590075Sobrien && !SIBLING_CALL_P (insn) 22690075Sobrien && !find_reg_note (insn, REG_NORETURN, NULL) 22790075Sobrien && !find_reg_note (insn, REG_ALWAYS_RETURN, NULL) 22890075Sobrien && !CONST_OR_PURE_CALL_P (insn))) 22990075Sobrien return true; 23090075Sobrien 23190075Sobrien return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS 23290075Sobrien && MEM_VOLATILE_P (PATTERN (insn))) 23390075Sobrien || (GET_CODE (PATTERN (insn)) == PARALLEL 23490075Sobrien && asm_noperands (insn) != -1 23590075Sobrien && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0))) 23690075Sobrien || GET_CODE (PATTERN (insn)) == ASM_INPUT); 23790075Sobrien} 23890075Sobrien 23996263Sobrien/* Return true if INSN should be kept in the same block as a preceding call. 24096263Sobrien This is done for a single-set whose destination is a fixed register or 24196263Sobrien whose source is the function return value. This is a helper function for 24296263Sobrien flow_call_edges_add. */ 24396263Sobrien 24496263Sobrienstatic bool 24596263Sobrienkeep_with_call_p (insn) 24696263Sobrien rtx insn; 24796263Sobrien{ 24896263Sobrien rtx set; 24996263Sobrien 25096263Sobrien if (INSN_P (insn) && (set = single_set (insn)) != NULL) 25196263Sobrien { 25296263Sobrien if (GET_CODE (SET_DEST (set)) == REG 25396263Sobrien && fixed_regs[REGNO (SET_DEST (set))] 25496263Sobrien && general_operand (SET_SRC (set), VOIDmode)) 25596263Sobrien return true; 25696263Sobrien if (GET_CODE (SET_SRC (set)) == REG 25796263Sobrien && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set))) 25896263Sobrien && GET_CODE (SET_DEST (set)) == REG 25996263Sobrien && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER) 26096263Sobrien return true; 26196263Sobrien } 26296263Sobrien return false; 26396263Sobrien} 26496263Sobrien 26590075Sobrien/* Add fake edges to the function exit for any non constant and non noreturn 26690075Sobrien calls, volatile inline assembly in the bitmap of blocks specified by 26790075Sobrien BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks 26890075Sobrien that were split. 26990075Sobrien 27090075Sobrien The goal is to expose cases in which entering a basic block does not imply 27190075Sobrien that all subsequent instructions must be executed. */ 27290075Sobrien 27390075Sobrienint 27490075Sobrienflow_call_edges_add (blocks) 27590075Sobrien sbitmap blocks; 27690075Sobrien{ 27790075Sobrien int i; 27890075Sobrien int blocks_split = 0; 27990075Sobrien int bb_num = 0; 28090075Sobrien basic_block *bbs; 28190075Sobrien bool check_last_block = false; 28290075Sobrien 28390075Sobrien /* Map bb indices into basic block pointers since split_block 28490075Sobrien will renumber the basic blocks. */ 28590075Sobrien 28690075Sobrien bbs = xmalloc (n_basic_blocks * sizeof (*bbs)); 28790075Sobrien 28890075Sobrien if (! blocks) 28990075Sobrien { 29090075Sobrien for (i = 0; i < n_basic_blocks; i++) 29190075Sobrien bbs[bb_num++] = BASIC_BLOCK (i); 29290075Sobrien 29390075Sobrien check_last_block = true; 29490075Sobrien } 29590075Sobrien else 29690075Sobrien EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, 29790075Sobrien { 29890075Sobrien bbs[bb_num++] = BASIC_BLOCK (i); 29990075Sobrien if (i == n_basic_blocks - 1) 30090075Sobrien check_last_block = true; 30190075Sobrien }); 30290075Sobrien 30390075Sobrien /* In the last basic block, before epilogue generation, there will be 30490075Sobrien a fallthru edge to EXIT. Special care is required if the last insn 30590075Sobrien of the last basic block is a call because make_edge folds duplicate 30690075Sobrien edges, which would result in the fallthru edge also being marked 30790075Sobrien fake, which would result in the fallthru edge being removed by 30890075Sobrien remove_fake_edges, which would result in an invalid CFG. 30990075Sobrien 31090075Sobrien Moreover, we can't elide the outgoing fake edge, since the block 31190075Sobrien profiler needs to take this into account in order to solve the minimal 31290075Sobrien spanning tree in the case that the call doesn't return. 31390075Sobrien 31490075Sobrien Handle this by adding a dummy instruction in a new last basic block. */ 31596263Sobrien if (check_last_block) 31690075Sobrien { 31796263Sobrien basic_block bb = BASIC_BLOCK (n_basic_blocks - 1); 31896263Sobrien rtx insn = bb->end; 31990075Sobrien 32096263Sobrien /* Back up past insns that must be kept in the same block as a call. */ 32196263Sobrien while (insn != bb->head 32296263Sobrien && keep_with_call_p (insn)) 32396263Sobrien insn = PREV_INSN (insn); 32490075Sobrien 32596263Sobrien if (need_fake_edge_p (insn)) 32696263Sobrien { 32796263Sobrien edge e; 32896263Sobrien 32996263Sobrien for (e = bb->succ; e; e = e->succ_next) 33096263Sobrien if (e->dest == EXIT_BLOCK_PTR) 33196263Sobrien break; 33296263Sobrien 33396263Sobrien insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e); 33496263Sobrien commit_edge_insertions (); 33596263Sobrien } 33690075Sobrien } 33790075Sobrien 33890075Sobrien /* Now add fake edges to the function exit for any non constant 33990075Sobrien calls since there is no way that we can determine if they will 34090075Sobrien return or not... */ 34190075Sobrien 34290075Sobrien for (i = 0; i < bb_num; i++) 34390075Sobrien { 34490075Sobrien basic_block bb = bbs[i]; 34590075Sobrien rtx insn; 34690075Sobrien rtx prev_insn; 34790075Sobrien 34890075Sobrien for (insn = bb->end; ; insn = prev_insn) 34990075Sobrien { 35090075Sobrien prev_insn = PREV_INSN (insn); 35190075Sobrien if (need_fake_edge_p (insn)) 35290075Sobrien { 35390075Sobrien edge e; 35496263Sobrien rtx split_at_insn = insn; 35590075Sobrien 35696263Sobrien /* Don't split the block between a call and an insn that should 35796263Sobrien remain in the same block as the call. */ 35896263Sobrien if (GET_CODE (insn) == CALL_INSN) 35996263Sobrien while (split_at_insn != bb->end 36096263Sobrien && keep_with_call_p (NEXT_INSN (split_at_insn))) 36196263Sobrien split_at_insn = NEXT_INSN (split_at_insn); 36290075Sobrien 36396263Sobrien /* The handling above of the final block before the epilogue 36496263Sobrien should be enough to verify that there is no edge to the exit 36596263Sobrien block in CFG already. Calling make_edge in such case would 36696263Sobrien cause us to mark that edge as fake and remove it later. */ 36796263Sobrien 36890075Sobrien#ifdef ENABLE_CHECKING 36996263Sobrien if (split_at_insn == bb->end) 37090075Sobrien for (e = bb->succ; e; e = e->succ_next) 37190075Sobrien if (e->dest == EXIT_BLOCK_PTR) 37290075Sobrien abort (); 37390075Sobrien#endif 37490075Sobrien 37590075Sobrien /* Note that the following may create a new basic block 37690075Sobrien and renumber the existing basic blocks. */ 37796263Sobrien e = split_block (bb, split_at_insn); 37890075Sobrien if (e) 37990075Sobrien blocks_split++; 38090075Sobrien 38190075Sobrien make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 38290075Sobrien } 38390075Sobrien 38490075Sobrien if (insn == bb->head) 38590075Sobrien break; 38690075Sobrien } 38790075Sobrien } 38890075Sobrien 38990075Sobrien if (blocks_split) 39090075Sobrien verify_flow_info (); 39190075Sobrien 39290075Sobrien free (bbs); 39390075Sobrien return blocks_split; 39490075Sobrien} 39590075Sobrien 39690075Sobrien/* Find unreachable blocks. An unreachable block will have 0 in 39790075Sobrien the reachable bit in block->flags. A non-zero value indicates the 39890075Sobrien block is reachable. */ 39990075Sobrien 40090075Sobrienvoid 40190075Sobrienfind_unreachable_blocks () 40290075Sobrien{ 40390075Sobrien edge e; 40490075Sobrien int i, n; 40590075Sobrien basic_block *tos, *worklist; 40690075Sobrien 40790075Sobrien n = n_basic_blocks; 40890075Sobrien tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n); 40990075Sobrien 41090075Sobrien /* Clear all the reachability flags. */ 41190075Sobrien 41290075Sobrien for (i = 0; i < n; ++i) 41390075Sobrien BASIC_BLOCK (i)->flags &= ~BB_REACHABLE; 41490075Sobrien 41590075Sobrien /* Add our starting points to the worklist. Almost always there will 41690075Sobrien be only one. It isn't inconceivable that we might one day directly 41790075Sobrien support Fortran alternate entry points. */ 41890075Sobrien 41990075Sobrien for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) 42090075Sobrien { 42190075Sobrien *tos++ = e->dest; 42290075Sobrien 42390075Sobrien /* Mark the block reachable. */ 42490075Sobrien e->dest->flags |= BB_REACHABLE; 42590075Sobrien } 42690075Sobrien 42790075Sobrien /* Iterate: find everything reachable from what we've already seen. */ 42890075Sobrien 42990075Sobrien while (tos != worklist) 43090075Sobrien { 43190075Sobrien basic_block b = *--tos; 43290075Sobrien 43390075Sobrien for (e = b->succ; e; e = e->succ_next) 43490075Sobrien if (!(e->dest->flags & BB_REACHABLE)) 43590075Sobrien { 43690075Sobrien *tos++ = e->dest; 43790075Sobrien e->dest->flags |= BB_REACHABLE; 43890075Sobrien } 43990075Sobrien } 44090075Sobrien 44190075Sobrien free (worklist); 44290075Sobrien} 44390075Sobrien 44490075Sobrien/* Functions to access an edge list with a vector representation. 44590075Sobrien Enough data is kept such that given an index number, the 44690075Sobrien pred and succ that edge represents can be determined, or 44790075Sobrien given a pred and a succ, its index number can be returned. 44890075Sobrien This allows algorithms which consume a lot of memory to 44990075Sobrien represent the normally full matrix of edge (pred,succ) with a 45090075Sobrien single indexed vector, edge (EDGE_INDEX (pred, succ)), with no 45190075Sobrien wasted space in the client code due to sparse flow graphs. */ 45290075Sobrien 45390075Sobrien/* This functions initializes the edge list. Basically the entire 45490075Sobrien flowgraph is processed, and all edges are assigned a number, 45590075Sobrien and the data structure is filled in. */ 45690075Sobrien 45790075Sobrienstruct edge_list * 45890075Sobriencreate_edge_list () 45990075Sobrien{ 46090075Sobrien struct edge_list *elist; 46190075Sobrien edge e; 46290075Sobrien int num_edges; 46390075Sobrien int x; 46490075Sobrien int block_count; 46590075Sobrien 46690075Sobrien block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */ 46790075Sobrien 46890075Sobrien num_edges = 0; 46990075Sobrien 47090075Sobrien /* Determine the number of edges in the flow graph by counting successor 47190075Sobrien edges on each basic block. */ 47290075Sobrien for (x = 0; x < n_basic_blocks; x++) 47390075Sobrien { 47490075Sobrien basic_block bb = BASIC_BLOCK (x); 47590075Sobrien 47690075Sobrien for (e = bb->succ; e; e = e->succ_next) 47790075Sobrien num_edges++; 47890075Sobrien } 47990075Sobrien 48090075Sobrien /* Don't forget successors of the entry block. */ 48190075Sobrien for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) 48290075Sobrien num_edges++; 48390075Sobrien 48490075Sobrien elist = (struct edge_list *) xmalloc (sizeof (struct edge_list)); 48590075Sobrien elist->num_blocks = block_count; 48690075Sobrien elist->num_edges = num_edges; 48790075Sobrien elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges); 48890075Sobrien 48990075Sobrien num_edges = 0; 49090075Sobrien 49190075Sobrien /* Follow successors of the entry block, and register these edges. */ 49290075Sobrien for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) 49390075Sobrien elist->index_to_edge[num_edges++] = e; 49490075Sobrien 49590075Sobrien for (x = 0; x < n_basic_blocks; x++) 49690075Sobrien { 49790075Sobrien basic_block bb = BASIC_BLOCK (x); 49890075Sobrien 49990075Sobrien /* Follow all successors of blocks, and register these edges. */ 50090075Sobrien for (e = bb->succ; e; e = e->succ_next) 50190075Sobrien elist->index_to_edge[num_edges++] = e; 50290075Sobrien } 50390075Sobrien 50490075Sobrien return elist; 50590075Sobrien} 50690075Sobrien 50790075Sobrien/* This function free's memory associated with an edge list. */ 50890075Sobrien 50990075Sobrienvoid 51090075Sobrienfree_edge_list (elist) 51190075Sobrien struct edge_list *elist; 51290075Sobrien{ 51390075Sobrien if (elist) 51490075Sobrien { 51590075Sobrien free (elist->index_to_edge); 51690075Sobrien free (elist); 51790075Sobrien } 51890075Sobrien} 51990075Sobrien 52090075Sobrien/* This function provides debug output showing an edge list. */ 52190075Sobrien 52290075Sobrienvoid 52390075Sobrienprint_edge_list (f, elist) 52490075Sobrien FILE *f; 52590075Sobrien struct edge_list *elist; 52690075Sobrien{ 52790075Sobrien int x; 52890075Sobrien 52990075Sobrien fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n", 53090075Sobrien elist->num_blocks - 2, elist->num_edges); 53190075Sobrien 53290075Sobrien for (x = 0; x < elist->num_edges; x++) 53390075Sobrien { 53490075Sobrien fprintf (f, " %-4d - edge(", x); 53590075Sobrien if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR) 53690075Sobrien fprintf (f, "entry,"); 53790075Sobrien else 53890075Sobrien fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index); 53990075Sobrien 54090075Sobrien if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR) 54190075Sobrien fprintf (f, "exit)\n"); 54290075Sobrien else 54390075Sobrien fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index); 54490075Sobrien } 54590075Sobrien} 54690075Sobrien 54790075Sobrien/* This function provides an internal consistency check of an edge list, 54890075Sobrien verifying that all edges are present, and that there are no 54990075Sobrien extra edges. */ 55090075Sobrien 55190075Sobrienvoid 55290075Sobrienverify_edge_list (f, elist) 55390075Sobrien FILE *f; 55490075Sobrien struct edge_list *elist; 55590075Sobrien{ 55690075Sobrien int x, pred, succ, index; 55790075Sobrien edge e; 55890075Sobrien 55990075Sobrien for (x = 0; x < n_basic_blocks; x++) 56090075Sobrien { 56190075Sobrien basic_block bb = BASIC_BLOCK (x); 56290075Sobrien 56390075Sobrien for (e = bb->succ; e; e = e->succ_next) 56490075Sobrien { 56590075Sobrien pred = e->src->index; 56690075Sobrien succ = e->dest->index; 56790075Sobrien index = EDGE_INDEX (elist, e->src, e->dest); 56890075Sobrien if (index == EDGE_INDEX_NO_EDGE) 56990075Sobrien { 57090075Sobrien fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ); 57190075Sobrien continue; 57290075Sobrien } 57390075Sobrien 57490075Sobrien if (INDEX_EDGE_PRED_BB (elist, index)->index != pred) 57590075Sobrien fprintf (f, "*p* Pred for index %d should be %d not %d\n", 57690075Sobrien index, pred, INDEX_EDGE_PRED_BB (elist, index)->index); 57790075Sobrien if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ) 57890075Sobrien fprintf (f, "*p* Succ for index %d should be %d not %d\n", 57990075Sobrien index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index); 58090075Sobrien } 58190075Sobrien } 58290075Sobrien 58390075Sobrien for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) 58490075Sobrien { 58590075Sobrien pred = e->src->index; 58690075Sobrien succ = e->dest->index; 58790075Sobrien index = EDGE_INDEX (elist, e->src, e->dest); 58890075Sobrien if (index == EDGE_INDEX_NO_EDGE) 58990075Sobrien { 59090075Sobrien fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ); 59190075Sobrien continue; 59290075Sobrien } 59390075Sobrien 59490075Sobrien if (INDEX_EDGE_PRED_BB (elist, index)->index != pred) 59590075Sobrien fprintf (f, "*p* Pred for index %d should be %d not %d\n", 59690075Sobrien index, pred, INDEX_EDGE_PRED_BB (elist, index)->index); 59790075Sobrien if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ) 59890075Sobrien fprintf (f, "*p* Succ for index %d should be %d not %d\n", 59990075Sobrien index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index); 60090075Sobrien } 60190075Sobrien 60290075Sobrien /* We've verified that all the edges are in the list, no lets make sure 60390075Sobrien there are no spurious edges in the list. */ 60490075Sobrien 60590075Sobrien for (pred = 0; pred < n_basic_blocks; pred++) 60690075Sobrien for (succ = 0; succ < n_basic_blocks; succ++) 60790075Sobrien { 60890075Sobrien basic_block p = BASIC_BLOCK (pred); 60990075Sobrien basic_block s = BASIC_BLOCK (succ); 61090075Sobrien int found_edge = 0; 61190075Sobrien 61290075Sobrien for (e = p->succ; e; e = e->succ_next) 61390075Sobrien if (e->dest == s) 61490075Sobrien { 61590075Sobrien found_edge = 1; 61690075Sobrien break; 61790075Sobrien } 61890075Sobrien 61990075Sobrien for (e = s->pred; e; e = e->pred_next) 62090075Sobrien if (e->src == p) 62190075Sobrien { 62290075Sobrien found_edge = 1; 62390075Sobrien break; 62490075Sobrien } 62590075Sobrien 62690075Sobrien if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ)) 62790075Sobrien == EDGE_INDEX_NO_EDGE && found_edge != 0) 62890075Sobrien fprintf (f, "*** Edge (%d, %d) appears to not have an index\n", 62990075Sobrien pred, succ); 63090075Sobrien if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ)) 63190075Sobrien != EDGE_INDEX_NO_EDGE && found_edge == 0) 63290075Sobrien fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n", 63390075Sobrien pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred), 63490075Sobrien BASIC_BLOCK (succ))); 63590075Sobrien } 63690075Sobrien 63790075Sobrien for (succ = 0; succ < n_basic_blocks; succ++) 63890075Sobrien { 63990075Sobrien basic_block p = ENTRY_BLOCK_PTR; 64090075Sobrien basic_block s = BASIC_BLOCK (succ); 64190075Sobrien int found_edge = 0; 64290075Sobrien 64390075Sobrien for (e = p->succ; e; e = e->succ_next) 64490075Sobrien if (e->dest == s) 64590075Sobrien { 64690075Sobrien found_edge = 1; 64790075Sobrien break; 64890075Sobrien } 64990075Sobrien 65090075Sobrien for (e = s->pred; e; e = e->pred_next) 65190075Sobrien if (e->src == p) 65290075Sobrien { 65390075Sobrien found_edge = 1; 65490075Sobrien break; 65590075Sobrien } 65690075Sobrien 65790075Sobrien if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ)) 65890075Sobrien == EDGE_INDEX_NO_EDGE && found_edge != 0) 65990075Sobrien fprintf (f, "*** Edge (entry, %d) appears to not have an index\n", 66090075Sobrien succ); 66190075Sobrien if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ)) 66290075Sobrien != EDGE_INDEX_NO_EDGE && found_edge == 0) 66390075Sobrien fprintf (f, "*** Edge (entry, %d) has index %d, but no edge exists\n", 66490075Sobrien succ, EDGE_INDEX (elist, ENTRY_BLOCK_PTR, 66590075Sobrien BASIC_BLOCK (succ))); 66690075Sobrien } 66790075Sobrien 66890075Sobrien for (pred = 0; pred < n_basic_blocks; pred++) 66990075Sobrien { 67090075Sobrien basic_block p = BASIC_BLOCK (pred); 67190075Sobrien basic_block s = EXIT_BLOCK_PTR; 67290075Sobrien int found_edge = 0; 67390075Sobrien 67490075Sobrien for (e = p->succ; e; e = e->succ_next) 67590075Sobrien if (e->dest == s) 67690075Sobrien { 67790075Sobrien found_edge = 1; 67890075Sobrien break; 67990075Sobrien } 68090075Sobrien 68190075Sobrien for (e = s->pred; e; e = e->pred_next) 68290075Sobrien if (e->src == p) 68390075Sobrien { 68490075Sobrien found_edge = 1; 68590075Sobrien break; 68690075Sobrien } 68790075Sobrien 68890075Sobrien if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR) 68990075Sobrien == EDGE_INDEX_NO_EDGE && found_edge != 0) 69090075Sobrien fprintf (f, "*** Edge (%d, exit) appears to not have an index\n", 69190075Sobrien pred); 69290075Sobrien if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR) 69390075Sobrien != EDGE_INDEX_NO_EDGE && found_edge == 0) 69490075Sobrien fprintf (f, "*** Edge (%d, exit) has index %d, but no edge exists\n", 69590075Sobrien pred, EDGE_INDEX (elist, BASIC_BLOCK (pred), 69690075Sobrien EXIT_BLOCK_PTR)); 69790075Sobrien } 69890075Sobrien} 69990075Sobrien 70090075Sobrien/* This routine will determine what, if any, edge there is between 70190075Sobrien a specified predecessor and successor. */ 70290075Sobrien 70390075Sobrienint 70490075Sobrienfind_edge_index (edge_list, pred, succ) 70590075Sobrien struct edge_list *edge_list; 70690075Sobrien basic_block pred, succ; 70790075Sobrien{ 70890075Sobrien int x; 70990075Sobrien 71090075Sobrien for (x = 0; x < NUM_EDGES (edge_list); x++) 71190075Sobrien if (INDEX_EDGE_PRED_BB (edge_list, x) == pred 71290075Sobrien && INDEX_EDGE_SUCC_BB (edge_list, x) == succ) 71390075Sobrien return x; 71490075Sobrien 71590075Sobrien return (EDGE_INDEX_NO_EDGE); 71690075Sobrien} 71790075Sobrien 71890075Sobrien/* Dump the list of basic blocks in the bitmap NODES. */ 71990075Sobrien 72090075Sobrienvoid 72190075Sobrienflow_nodes_print (str, nodes, file) 72290075Sobrien const char *str; 72390075Sobrien const sbitmap nodes; 72490075Sobrien FILE *file; 72590075Sobrien{ 72690075Sobrien int node; 72790075Sobrien 72890075Sobrien if (! nodes) 72990075Sobrien return; 73090075Sobrien 73190075Sobrien fprintf (file, "%s { ", str); 73290075Sobrien EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);}); 73390075Sobrien fputs ("}\n", file); 73490075Sobrien} 73590075Sobrien 73690075Sobrien/* Dump the list of edges in the array EDGE_LIST. */ 73790075Sobrien 73890075Sobrienvoid 73990075Sobrienflow_edge_list_print (str, edge_list, num_edges, file) 74090075Sobrien const char *str; 74190075Sobrien const edge *edge_list; 74290075Sobrien int num_edges; 74390075Sobrien FILE *file; 74490075Sobrien{ 74590075Sobrien int i; 74690075Sobrien 74790075Sobrien if (! edge_list) 74890075Sobrien return; 74990075Sobrien 75090075Sobrien fprintf (file, "%s { ", str); 75190075Sobrien for (i = 0; i < num_edges; i++) 75290075Sobrien fprintf (file, "%d->%d ", edge_list[i]->src->index, 75390075Sobrien edge_list[i]->dest->index); 75490075Sobrien 75590075Sobrien fputs ("}\n", file); 75690075Sobrien} 75790075Sobrien 75890075Sobrien 75990075Sobrien/* This routine will remove any fake successor edges for a basic block. 76090075Sobrien When the edge is removed, it is also removed from whatever predecessor 76190075Sobrien list it is in. */ 76290075Sobrien 76390075Sobrienstatic void 76490075Sobrienremove_fake_successors (bb) 76590075Sobrien basic_block bb; 76690075Sobrien{ 76790075Sobrien edge e; 76890075Sobrien 76990075Sobrien for (e = bb->succ; e;) 77090075Sobrien { 77190075Sobrien edge tmp = e; 77290075Sobrien 77390075Sobrien e = e->succ_next; 77490075Sobrien if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE) 77590075Sobrien remove_edge (tmp); 77690075Sobrien } 77790075Sobrien} 77890075Sobrien 77990075Sobrien/* This routine will remove all fake edges from the flow graph. If 78090075Sobrien we remove all fake successors, it will automatically remove all 78190075Sobrien fake predecessors. */ 78290075Sobrien 78390075Sobrienvoid 78490075Sobrienremove_fake_edges () 78590075Sobrien{ 78690075Sobrien int x; 78790075Sobrien 78890075Sobrien for (x = 0; x < n_basic_blocks; x++) 78990075Sobrien remove_fake_successors (BASIC_BLOCK (x)); 79090075Sobrien 79190075Sobrien /* We've handled all successors except the entry block's. */ 79290075Sobrien remove_fake_successors (ENTRY_BLOCK_PTR); 79390075Sobrien} 79490075Sobrien 79590075Sobrien/* This function will add a fake edge between any block which has no 79690075Sobrien successors, and the exit block. Some data flow equations require these 79790075Sobrien edges to exist. */ 79890075Sobrien 79990075Sobrienvoid 80090075Sobrienadd_noreturn_fake_exit_edges () 80190075Sobrien{ 80290075Sobrien int x; 80390075Sobrien 80490075Sobrien for (x = 0; x < n_basic_blocks; x++) 80590075Sobrien if (BASIC_BLOCK (x)->succ == NULL) 80690075Sobrien make_single_succ_edge (BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE); 80790075Sobrien} 80890075Sobrien 80990075Sobrien/* This function adds a fake edge between any infinite loops to the 81090075Sobrien exit block. Some optimizations require a path from each node to 81190075Sobrien the exit node. 81290075Sobrien 81390075Sobrien See also Morgan, Figure 3.10, pp. 82-83. 81490075Sobrien 81590075Sobrien The current implementation is ugly, not attempting to minimize the 81690075Sobrien number of inserted fake edges. To reduce the number of fake edges 81790075Sobrien to insert, add fake edges from _innermost_ loops containing only 81890075Sobrien nodes not reachable from the exit block. */ 81990075Sobrien 82090075Sobrienvoid 82190075Sobrienconnect_infinite_loops_to_exit () 82290075Sobrien{ 82390075Sobrien basic_block unvisited_block; 82490075Sobrien struct depth_first_search_dsS dfs_ds; 82590075Sobrien 82690075Sobrien /* Perform depth-first search in the reverse graph to find nodes 82790075Sobrien reachable from the exit block. */ 82890075Sobrien flow_dfs_compute_reverse_init (&dfs_ds); 82990075Sobrien flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR); 83090075Sobrien 83190075Sobrien /* Repeatedly add fake edges, updating the unreachable nodes. */ 83290075Sobrien while (1) 83390075Sobrien { 83490075Sobrien unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds); 83590075Sobrien if (!unvisited_block) 83690075Sobrien break; 83790075Sobrien 83890075Sobrien make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE); 83990075Sobrien flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block); 84090075Sobrien } 84190075Sobrien 84290075Sobrien flow_dfs_compute_reverse_finish (&dfs_ds); 84390075Sobrien return; 84490075Sobrien} 84590075Sobrien 84690075Sobrien/* Compute reverse top sort order */ 84790075Sobrien 84890075Sobrienvoid 84990075Sobrienflow_reverse_top_sort_order_compute (rts_order) 85090075Sobrien int *rts_order; 85190075Sobrien{ 85290075Sobrien edge *stack; 85390075Sobrien int sp; 85490075Sobrien int postnum = 0; 85590075Sobrien sbitmap visited; 85690075Sobrien 85790075Sobrien /* Allocate stack for back-tracking up CFG. */ 85890075Sobrien stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); 85990075Sobrien sp = 0; 86090075Sobrien 86190075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 86290075Sobrien visited = sbitmap_alloc (n_basic_blocks); 86390075Sobrien 86490075Sobrien /* None of the nodes in the CFG have been visited yet. */ 86590075Sobrien sbitmap_zero (visited); 86690075Sobrien 86790075Sobrien /* Push the first edge on to the stack. */ 86890075Sobrien stack[sp++] = ENTRY_BLOCK_PTR->succ; 86990075Sobrien 87090075Sobrien while (sp) 87190075Sobrien { 87290075Sobrien edge e; 87390075Sobrien basic_block src; 87490075Sobrien basic_block dest; 87590075Sobrien 87690075Sobrien /* Look at the edge on the top of the stack. */ 87790075Sobrien e = stack[sp - 1]; 87890075Sobrien src = e->src; 87990075Sobrien dest = e->dest; 88090075Sobrien 88190075Sobrien /* Check if the edge destination has been visited yet. */ 88290075Sobrien if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 88390075Sobrien { 88490075Sobrien /* Mark that we have visited the destination. */ 88590075Sobrien SET_BIT (visited, dest->index); 88690075Sobrien 88790075Sobrien if (dest->succ) 88890075Sobrien /* Since the DEST node has been visited for the first 88990075Sobrien time, check its successors. */ 89090075Sobrien stack[sp++] = dest->succ; 89190075Sobrien else 89290075Sobrien rts_order[postnum++] = dest->index; 89390075Sobrien } 89490075Sobrien else 89590075Sobrien { 89690075Sobrien if (! e->succ_next && src != ENTRY_BLOCK_PTR) 89790075Sobrien rts_order[postnum++] = src->index; 89890075Sobrien 89990075Sobrien if (e->succ_next) 90090075Sobrien stack[sp - 1] = e->succ_next; 90190075Sobrien else 90290075Sobrien sp--; 90390075Sobrien } 90490075Sobrien } 90590075Sobrien 90690075Sobrien free (stack); 90790075Sobrien sbitmap_free (visited); 90890075Sobrien} 90990075Sobrien 91090075Sobrien/* Compute the depth first search order and store in the array 91190075Sobrien DFS_ORDER if non-zero, marking the nodes visited in VISITED. If 91290075Sobrien RC_ORDER is non-zero, return the reverse completion number for each 91390075Sobrien node. Returns the number of nodes visited. A depth first search 91490075Sobrien tries to get as far away from the starting point as quickly as 91590075Sobrien possible. */ 91690075Sobrien 91790075Sobrienint 91890075Sobrienflow_depth_first_order_compute (dfs_order, rc_order) 91990075Sobrien int *dfs_order; 92090075Sobrien int *rc_order; 92190075Sobrien{ 92290075Sobrien edge *stack; 92390075Sobrien int sp; 92490075Sobrien int dfsnum = 0; 92590075Sobrien int rcnum = n_basic_blocks - 1; 92690075Sobrien sbitmap visited; 92790075Sobrien 92890075Sobrien /* Allocate stack for back-tracking up CFG. */ 92990075Sobrien stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); 93090075Sobrien sp = 0; 93190075Sobrien 93290075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 93390075Sobrien visited = sbitmap_alloc (n_basic_blocks); 93490075Sobrien 93590075Sobrien /* None of the nodes in the CFG have been visited yet. */ 93690075Sobrien sbitmap_zero (visited); 93790075Sobrien 93890075Sobrien /* Push the first edge on to the stack. */ 93990075Sobrien stack[sp++] = ENTRY_BLOCK_PTR->succ; 94090075Sobrien 94190075Sobrien while (sp) 94290075Sobrien { 94390075Sobrien edge e; 94490075Sobrien basic_block src; 94590075Sobrien basic_block dest; 94690075Sobrien 94790075Sobrien /* Look at the edge on the top of the stack. */ 94890075Sobrien e = stack[sp - 1]; 94990075Sobrien src = e->src; 95090075Sobrien dest = e->dest; 95190075Sobrien 95290075Sobrien /* Check if the edge destination has been visited yet. */ 95390075Sobrien if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 95490075Sobrien { 95590075Sobrien /* Mark that we have visited the destination. */ 95690075Sobrien SET_BIT (visited, dest->index); 95790075Sobrien 95890075Sobrien if (dfs_order) 95990075Sobrien dfs_order[dfsnum] = dest->index; 96090075Sobrien 96190075Sobrien dfsnum++; 96290075Sobrien 96390075Sobrien if (dest->succ) 96490075Sobrien /* Since the DEST node has been visited for the first 96590075Sobrien time, check its successors. */ 96690075Sobrien stack[sp++] = dest->succ; 96790075Sobrien else if (rc_order) 96890075Sobrien /* There are no successors for the DEST node so assign 96990075Sobrien its reverse completion number. */ 97090075Sobrien rc_order[rcnum--] = dest->index; 97190075Sobrien } 97290075Sobrien else 97390075Sobrien { 97490075Sobrien if (! e->succ_next && src != ENTRY_BLOCK_PTR 97590075Sobrien && rc_order) 97690075Sobrien /* There are no more successors for the SRC node 97790075Sobrien so assign its reverse completion number. */ 97890075Sobrien rc_order[rcnum--] = src->index; 97990075Sobrien 98090075Sobrien if (e->succ_next) 98190075Sobrien stack[sp - 1] = e->succ_next; 98290075Sobrien else 98390075Sobrien sp--; 98490075Sobrien } 98590075Sobrien } 98690075Sobrien 98790075Sobrien free (stack); 98890075Sobrien sbitmap_free (visited); 98990075Sobrien 99090075Sobrien /* The number of nodes visited should not be greater than 99190075Sobrien n_basic_blocks. */ 99290075Sobrien if (dfsnum > n_basic_blocks) 99390075Sobrien abort (); 99490075Sobrien 99590075Sobrien /* There are some nodes left in the CFG that are unreachable. */ 99690075Sobrien if (dfsnum < n_basic_blocks) 99790075Sobrien abort (); 99890075Sobrien 99990075Sobrien return dfsnum; 100090075Sobrien} 100190075Sobrien 100290075Sobrienstruct dfst_node 100390075Sobrien{ 100490075Sobrien unsigned nnodes; 100590075Sobrien struct dfst_node **node; 100690075Sobrien struct dfst_node *up; 100790075Sobrien}; 100890075Sobrien 100990075Sobrien/* Compute a preorder transversal ordering such that a sub-tree which 101090075Sobrien is the source of a cross edge appears before the sub-tree which is 101190075Sobrien the destination of the cross edge. This allows for easy detection 101290075Sobrien of all the entry blocks for a loop. 101390075Sobrien 101490075Sobrien The ordering is compute by: 101590075Sobrien 101690075Sobrien 1) Generating a depth first spanning tree. 101790075Sobrien 101890075Sobrien 2) Walking the resulting tree from right to left. */ 101990075Sobrien 102090075Sobrienvoid 102190075Sobrienflow_preorder_transversal_compute (pot_order) 102290075Sobrien int *pot_order; 102390075Sobrien{ 102490075Sobrien edge e; 102590075Sobrien edge *stack; 102690075Sobrien int i; 102790075Sobrien int max_successors; 102890075Sobrien int sp; 102990075Sobrien sbitmap visited; 103090075Sobrien struct dfst_node *node; 103190075Sobrien struct dfst_node *dfst; 103290075Sobrien 103390075Sobrien /* Allocate stack for back-tracking up CFG. */ 103490075Sobrien stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge)); 103590075Sobrien sp = 0; 103690075Sobrien 103790075Sobrien /* Allocate the tree. */ 103890075Sobrien dfst = (struct dfst_node *) xcalloc (n_basic_blocks, 103990075Sobrien sizeof (struct dfst_node)); 104090075Sobrien 104190075Sobrien for (i = 0; i < n_basic_blocks; i++) 104290075Sobrien { 104390075Sobrien max_successors = 0; 104490075Sobrien for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next) 104590075Sobrien max_successors++; 104690075Sobrien 104790075Sobrien dfst[i].node 104890075Sobrien = (max_successors 104990075Sobrien ? (struct dfst_node **) xcalloc (max_successors, 105090075Sobrien sizeof (struct dfst_node *)) 105190075Sobrien : NULL); 105290075Sobrien } 105390075Sobrien 105490075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 105590075Sobrien visited = sbitmap_alloc (n_basic_blocks); 105690075Sobrien 105790075Sobrien /* None of the nodes in the CFG have been visited yet. */ 105890075Sobrien sbitmap_zero (visited); 105990075Sobrien 106090075Sobrien /* Push the first edge on to the stack. */ 106190075Sobrien stack[sp++] = ENTRY_BLOCK_PTR->succ; 106290075Sobrien 106390075Sobrien while (sp) 106490075Sobrien { 106590075Sobrien basic_block src; 106690075Sobrien basic_block dest; 106790075Sobrien 106890075Sobrien /* Look at the edge on the top of the stack. */ 106990075Sobrien e = stack[sp - 1]; 107090075Sobrien src = e->src; 107190075Sobrien dest = e->dest; 107290075Sobrien 107390075Sobrien /* Check if the edge destination has been visited yet. */ 107490075Sobrien if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)) 107590075Sobrien { 107690075Sobrien /* Mark that we have visited the destination. */ 107790075Sobrien SET_BIT (visited, dest->index); 107890075Sobrien 107990075Sobrien /* Add the destination to the preorder tree. */ 108090075Sobrien if (src != ENTRY_BLOCK_PTR) 108190075Sobrien { 108290075Sobrien dfst[src->index].node[dfst[src->index].nnodes++] 108390075Sobrien = &dfst[dest->index]; 108490075Sobrien dfst[dest->index].up = &dfst[src->index]; 108590075Sobrien } 108690075Sobrien 108790075Sobrien if (dest->succ) 108890075Sobrien /* Since the DEST node has been visited for the first 108990075Sobrien time, check its successors. */ 109090075Sobrien stack[sp++] = dest->succ; 109190075Sobrien } 109290075Sobrien 109390075Sobrien else if (e->succ_next) 109490075Sobrien stack[sp - 1] = e->succ_next; 109590075Sobrien else 109690075Sobrien sp--; 109790075Sobrien } 109890075Sobrien 109990075Sobrien free (stack); 110090075Sobrien sbitmap_free (visited); 110190075Sobrien 110290075Sobrien /* Record the preorder transversal order by 110390075Sobrien walking the tree from right to left. */ 110490075Sobrien 110590075Sobrien i = 0; 110690075Sobrien node = &dfst[0]; 110790075Sobrien pot_order[i++] = 0; 110890075Sobrien 110990075Sobrien while (node) 111090075Sobrien { 111190075Sobrien if (node->nnodes) 111290075Sobrien { 111390075Sobrien node = node->node[--node->nnodes]; 111490075Sobrien pot_order[i++] = node - dfst; 111590075Sobrien } 111690075Sobrien else 111790075Sobrien node = node->up; 111890075Sobrien } 111990075Sobrien 112090075Sobrien /* Free the tree. */ 112190075Sobrien 112290075Sobrien for (i = 0; i < n_basic_blocks; i++) 112390075Sobrien if (dfst[i].node) 112490075Sobrien free (dfst[i].node); 112590075Sobrien 112690075Sobrien free (dfst); 112790075Sobrien} 112890075Sobrien 112990075Sobrien/* Compute the depth first search order on the _reverse_ graph and 113090075Sobrien store in the array DFS_ORDER, marking the nodes visited in VISITED. 113190075Sobrien Returns the number of nodes visited. 113290075Sobrien 113390075Sobrien The computation is split into three pieces: 113490075Sobrien 113590075Sobrien flow_dfs_compute_reverse_init () creates the necessary data 113690075Sobrien structures. 113790075Sobrien 113890075Sobrien flow_dfs_compute_reverse_add_bb () adds a basic block to the data 113990075Sobrien structures. The block will start the search. 114090075Sobrien 114190075Sobrien flow_dfs_compute_reverse_execute () continues (or starts) the 114290075Sobrien search using the block on the top of the stack, stopping when the 114390075Sobrien stack is empty. 114490075Sobrien 114590075Sobrien flow_dfs_compute_reverse_finish () destroys the necessary data 114690075Sobrien structures. 114790075Sobrien 114890075Sobrien Thus, the user will probably call ..._init(), call ..._add_bb() to 114990075Sobrien add a beginning basic block to the stack, call ..._execute(), 115090075Sobrien possibly add another bb to the stack and again call ..._execute(), 115190075Sobrien ..., and finally call _finish(). */ 115290075Sobrien 115390075Sobrien/* Initialize the data structures used for depth-first search on the 115490075Sobrien reverse graph. If INITIALIZE_STACK is nonzero, the exit block is 115590075Sobrien added to the basic block stack. DATA is the current depth-first 115690075Sobrien search context. If INITIALIZE_STACK is non-zero, there is an 115790075Sobrien element on the stack. */ 115890075Sobrien 115990075Sobrienstatic void 116090075Sobrienflow_dfs_compute_reverse_init (data) 116190075Sobrien depth_first_search_ds data; 116290075Sobrien{ 116390075Sobrien /* Allocate stack for back-tracking up CFG. */ 116490075Sobrien data->stack = (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1)) 116590075Sobrien * sizeof (basic_block)); 116690075Sobrien data->sp = 0; 116790075Sobrien 116890075Sobrien /* Allocate bitmap to track nodes that have been visited. */ 116990075Sobrien data->visited_blocks = sbitmap_alloc (n_basic_blocks - (INVALID_BLOCK + 1)); 117090075Sobrien 117190075Sobrien /* None of the nodes in the CFG have been visited yet. */ 117290075Sobrien sbitmap_zero (data->visited_blocks); 117390075Sobrien 117490075Sobrien return; 117590075Sobrien} 117690075Sobrien 117790075Sobrien/* Add the specified basic block to the top of the dfs data 117890075Sobrien structures. When the search continues, it will start at the 117990075Sobrien block. */ 118090075Sobrien 118190075Sobrienstatic void 118290075Sobrienflow_dfs_compute_reverse_add_bb (data, bb) 118390075Sobrien depth_first_search_ds data; 118490075Sobrien basic_block bb; 118590075Sobrien{ 118690075Sobrien data->stack[data->sp++] = bb; 118790075Sobrien SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)); 118890075Sobrien} 118990075Sobrien 119090075Sobrien/* Continue the depth-first search through the reverse graph starting with the 119190075Sobrien block at the stack's top and ending when the stack is empty. Visited nodes 119290075Sobrien are marked. Returns an unvisited basic block, or NULL if there is none 119390075Sobrien available. */ 119490075Sobrien 119590075Sobrienstatic basic_block 119690075Sobrienflow_dfs_compute_reverse_execute (data) 119790075Sobrien depth_first_search_ds data; 119890075Sobrien{ 119990075Sobrien basic_block bb; 120090075Sobrien edge e; 120190075Sobrien int i; 120290075Sobrien 120390075Sobrien while (data->sp > 0) 120490075Sobrien { 120590075Sobrien bb = data->stack[--data->sp]; 120690075Sobrien 120790075Sobrien /* Perform depth-first search on adjacent vertices. */ 120890075Sobrien for (e = bb->pred; e; e = e->pred_next) 120990075Sobrien if (!TEST_BIT (data->visited_blocks, 121090075Sobrien e->src->index - (INVALID_BLOCK + 1))) 121190075Sobrien flow_dfs_compute_reverse_add_bb (data, e->src); 121290075Sobrien } 121390075Sobrien 121490075Sobrien /* Determine if there are unvisited basic blocks. */ 121590075Sobrien for (i = n_basic_blocks - (INVALID_BLOCK + 1); --i >= 0; ) 121690075Sobrien if (!TEST_BIT (data->visited_blocks, i)) 121790075Sobrien return BASIC_BLOCK (i + (INVALID_BLOCK + 1)); 121890075Sobrien 121990075Sobrien return NULL; 122090075Sobrien} 122190075Sobrien 122290075Sobrien/* Destroy the data structures needed for depth-first search on the 122390075Sobrien reverse graph. */ 122490075Sobrien 122590075Sobrienstatic void 122690075Sobrienflow_dfs_compute_reverse_finish (data) 122790075Sobrien depth_first_search_ds data; 122890075Sobrien{ 122990075Sobrien free (data->stack); 123090075Sobrien sbitmap_free (data->visited_blocks); 123190075Sobrien} 1232