1*c87b03e5Sespie /* Control flow graph analysis code for GNU compiler.
2*c87b03e5Sespie Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3*c87b03e5Sespie 1999, 2000, 2001, 2003 Free Software Foundation, Inc.
4*c87b03e5Sespie
5*c87b03e5Sespie This file is part of GCC.
6*c87b03e5Sespie
7*c87b03e5Sespie GCC is free software; you can redistribute it and/or modify it under
8*c87b03e5Sespie the terms of the GNU General Public License as published by the Free
9*c87b03e5Sespie Software Foundation; either version 2, or (at your option) any later
10*c87b03e5Sespie version.
11*c87b03e5Sespie
12*c87b03e5Sespie GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13*c87b03e5Sespie WARRANTY; without even the implied warranty of MERCHANTABILITY or
14*c87b03e5Sespie FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15*c87b03e5Sespie for more details.
16*c87b03e5Sespie
17*c87b03e5Sespie You should have received a copy of the GNU General Public License
18*c87b03e5Sespie along with GCC; see the file COPYING. If not, write to the Free
19*c87b03e5Sespie Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20*c87b03e5Sespie 02111-1307, USA. */
21*c87b03e5Sespie
22*c87b03e5Sespie /* This file contains various simple utilities to analyze the CFG. */
23*c87b03e5Sespie #include "config.h"
24*c87b03e5Sespie #include "system.h"
25*c87b03e5Sespie #include "rtl.h"
26*c87b03e5Sespie #include "hard-reg-set.h"
27*c87b03e5Sespie #include "basic-block.h"
28*c87b03e5Sespie #include "insn-config.h"
29*c87b03e5Sespie #include "recog.h"
30*c87b03e5Sespie #include "toplev.h"
31*c87b03e5Sespie #include "tm_p.h"
32*c87b03e5Sespie
33*c87b03e5Sespie /* Store the data structures necessary for depth-first search. */
34*c87b03e5Sespie struct depth_first_search_dsS {
35*c87b03e5Sespie /* stack for backtracking during the algorithm */
36*c87b03e5Sespie basic_block *stack;
37*c87b03e5Sespie
38*c87b03e5Sespie /* number of edges in the stack. That is, positions 0, ..., sp-1
39*c87b03e5Sespie have edges. */
40*c87b03e5Sespie unsigned int sp;
41*c87b03e5Sespie
42*c87b03e5Sespie /* record of basic blocks already seen by depth-first search */
43*c87b03e5Sespie sbitmap visited_blocks;
44*c87b03e5Sespie };
45*c87b03e5Sespie typedef struct depth_first_search_dsS *depth_first_search_ds;
46*c87b03e5Sespie
47*c87b03e5Sespie static void flow_dfs_compute_reverse_init
48*c87b03e5Sespie PARAMS ((depth_first_search_ds));
49*c87b03e5Sespie static void flow_dfs_compute_reverse_add_bb
50*c87b03e5Sespie PARAMS ((depth_first_search_ds, basic_block));
51*c87b03e5Sespie static basic_block flow_dfs_compute_reverse_execute
52*c87b03e5Sespie PARAMS ((depth_first_search_ds));
53*c87b03e5Sespie static void flow_dfs_compute_reverse_finish
54*c87b03e5Sespie PARAMS ((depth_first_search_ds));
55*c87b03e5Sespie static void remove_fake_successors PARAMS ((basic_block));
56*c87b03e5Sespie static bool need_fake_edge_p PARAMS ((rtx));
57*c87b03e5Sespie static bool flow_active_insn_p PARAMS ((rtx));
58*c87b03e5Sespie
59*c87b03e5Sespie /* Like active_insn_p, except keep the return value clobber around
60*c87b03e5Sespie even after reload. */
61*c87b03e5Sespie
62*c87b03e5Sespie static bool
flow_active_insn_p(insn)63*c87b03e5Sespie flow_active_insn_p (insn)
64*c87b03e5Sespie rtx insn;
65*c87b03e5Sespie {
66*c87b03e5Sespie if (active_insn_p (insn))
67*c87b03e5Sespie return true;
68*c87b03e5Sespie
69*c87b03e5Sespie /* A clobber of the function return value exists for buggy
70*c87b03e5Sespie programs that fail to return a value. Its effect is to
71*c87b03e5Sespie keep the return value from being live across the entire
72*c87b03e5Sespie function. If we allow it to be skipped, we introduce the
73*c87b03e5Sespie possibility for register livetime aborts. */
74*c87b03e5Sespie if (GET_CODE (PATTERN (insn)) == CLOBBER
75*c87b03e5Sespie && GET_CODE (XEXP (PATTERN (insn), 0)) == REG
76*c87b03e5Sespie && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
77*c87b03e5Sespie return true;
78*c87b03e5Sespie
79*c87b03e5Sespie return false;
80*c87b03e5Sespie }
81*c87b03e5Sespie
82*c87b03e5Sespie /* Return true if the block has no effect and only forwards control flow to
83*c87b03e5Sespie its single destination. */
84*c87b03e5Sespie
85*c87b03e5Sespie bool
forwarder_block_p(bb)86*c87b03e5Sespie forwarder_block_p (bb)
87*c87b03e5Sespie basic_block bb;
88*c87b03e5Sespie {
89*c87b03e5Sespie rtx insn;
90*c87b03e5Sespie
91*c87b03e5Sespie if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
92*c87b03e5Sespie || !bb->succ || bb->succ->succ_next)
93*c87b03e5Sespie return false;
94*c87b03e5Sespie
95*c87b03e5Sespie for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn))
96*c87b03e5Sespie if (INSN_P (insn) && flow_active_insn_p (insn))
97*c87b03e5Sespie return false;
98*c87b03e5Sespie
99*c87b03e5Sespie return (!INSN_P (insn)
100*c87b03e5Sespie || (GET_CODE (insn) == JUMP_INSN && simplejump_p (insn))
101*c87b03e5Sespie || !flow_active_insn_p (insn));
102*c87b03e5Sespie }
103*c87b03e5Sespie
104*c87b03e5Sespie /* Return nonzero if we can reach target from src by falling through. */
105*c87b03e5Sespie
106*c87b03e5Sespie bool
can_fallthru(src,target)107*c87b03e5Sespie can_fallthru (src, target)
108*c87b03e5Sespie basic_block src, target;
109*c87b03e5Sespie {
110*c87b03e5Sespie rtx insn = src->end;
111*c87b03e5Sespie rtx insn2 = target->head;
112*c87b03e5Sespie
113*c87b03e5Sespie if (src->next_bb != target)
114*c87b03e5Sespie return 0;
115*c87b03e5Sespie
116*c87b03e5Sespie if (!active_insn_p (insn2))
117*c87b03e5Sespie insn2 = next_active_insn (insn2);
118*c87b03e5Sespie
119*c87b03e5Sespie /* ??? Later we may add code to move jump tables offline. */
120*c87b03e5Sespie return next_active_insn (insn) == insn2;
121*c87b03e5Sespie }
122*c87b03e5Sespie
123*c87b03e5Sespie /* Mark the back edges in DFS traversal.
124*c87b03e5Sespie Return nonzero if a loop (natural or otherwise) is present.
125*c87b03e5Sespie Inspired by Depth_First_Search_PP described in:
126*c87b03e5Sespie
127*c87b03e5Sespie Advanced Compiler Design and Implementation
128*c87b03e5Sespie Steven Muchnick
129*c87b03e5Sespie Morgan Kaufmann, 1997
130*c87b03e5Sespie
131*c87b03e5Sespie and heavily borrowed from flow_depth_first_order_compute. */
132*c87b03e5Sespie
133*c87b03e5Sespie bool
mark_dfs_back_edges()134*c87b03e5Sespie mark_dfs_back_edges ()
135*c87b03e5Sespie {
136*c87b03e5Sespie edge *stack;
137*c87b03e5Sespie int *pre;
138*c87b03e5Sespie int *post;
139*c87b03e5Sespie int sp;
140*c87b03e5Sespie int prenum = 1;
141*c87b03e5Sespie int postnum = 1;
142*c87b03e5Sespie sbitmap visited;
143*c87b03e5Sespie bool found = false;
144*c87b03e5Sespie
145*c87b03e5Sespie /* Allocate the preorder and postorder number arrays. */
146*c87b03e5Sespie pre = (int *) xcalloc (last_basic_block, sizeof (int));
147*c87b03e5Sespie post = (int *) xcalloc (last_basic_block, sizeof (int));
148*c87b03e5Sespie
149*c87b03e5Sespie /* Allocate stack for back-tracking up CFG. */
150*c87b03e5Sespie stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
151*c87b03e5Sespie sp = 0;
152*c87b03e5Sespie
153*c87b03e5Sespie /* Allocate bitmap to track nodes that have been visited. */
154*c87b03e5Sespie visited = sbitmap_alloc (last_basic_block);
155*c87b03e5Sespie
156*c87b03e5Sespie /* None of the nodes in the CFG have been visited yet. */
157*c87b03e5Sespie sbitmap_zero (visited);
158*c87b03e5Sespie
159*c87b03e5Sespie /* Push the first edge on to the stack. */
160*c87b03e5Sespie stack[sp++] = ENTRY_BLOCK_PTR->succ;
161*c87b03e5Sespie
162*c87b03e5Sespie while (sp)
163*c87b03e5Sespie {
164*c87b03e5Sespie edge e;
165*c87b03e5Sespie basic_block src;
166*c87b03e5Sespie basic_block dest;
167*c87b03e5Sespie
168*c87b03e5Sespie /* Look at the edge on the top of the stack. */
169*c87b03e5Sespie e = stack[sp - 1];
170*c87b03e5Sespie src = e->src;
171*c87b03e5Sespie dest = e->dest;
172*c87b03e5Sespie e->flags &= ~EDGE_DFS_BACK;
173*c87b03e5Sespie
174*c87b03e5Sespie /* Check if the edge destination has been visited yet. */
175*c87b03e5Sespie if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
176*c87b03e5Sespie {
177*c87b03e5Sespie /* Mark that we have visited the destination. */
178*c87b03e5Sespie SET_BIT (visited, dest->index);
179*c87b03e5Sespie
180*c87b03e5Sespie pre[dest->index] = prenum++;
181*c87b03e5Sespie if (dest->succ)
182*c87b03e5Sespie {
183*c87b03e5Sespie /* Since the DEST node has been visited for the first
184*c87b03e5Sespie time, check its successors. */
185*c87b03e5Sespie stack[sp++] = dest->succ;
186*c87b03e5Sespie }
187*c87b03e5Sespie else
188*c87b03e5Sespie post[dest->index] = postnum++;
189*c87b03e5Sespie }
190*c87b03e5Sespie else
191*c87b03e5Sespie {
192*c87b03e5Sespie if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
193*c87b03e5Sespie && pre[src->index] >= pre[dest->index]
194*c87b03e5Sespie && post[dest->index] == 0)
195*c87b03e5Sespie e->flags |= EDGE_DFS_BACK, found = true;
196*c87b03e5Sespie
197*c87b03e5Sespie if (! e->succ_next && src != ENTRY_BLOCK_PTR)
198*c87b03e5Sespie post[src->index] = postnum++;
199*c87b03e5Sespie
200*c87b03e5Sespie if (e->succ_next)
201*c87b03e5Sespie stack[sp - 1] = e->succ_next;
202*c87b03e5Sespie else
203*c87b03e5Sespie sp--;
204*c87b03e5Sespie }
205*c87b03e5Sespie }
206*c87b03e5Sespie
207*c87b03e5Sespie free (pre);
208*c87b03e5Sespie free (post);
209*c87b03e5Sespie free (stack);
210*c87b03e5Sespie sbitmap_free (visited);
211*c87b03e5Sespie
212*c87b03e5Sespie return found;
213*c87b03e5Sespie }
214*c87b03e5Sespie
215*c87b03e5Sespie /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
216*c87b03e5Sespie
217*c87b03e5Sespie void
set_edge_can_fallthru_flag()218*c87b03e5Sespie set_edge_can_fallthru_flag ()
219*c87b03e5Sespie {
220*c87b03e5Sespie basic_block bb;
221*c87b03e5Sespie
222*c87b03e5Sespie FOR_EACH_BB (bb)
223*c87b03e5Sespie {
224*c87b03e5Sespie edge e;
225*c87b03e5Sespie
226*c87b03e5Sespie for (e = bb->succ; e; e = e->succ_next)
227*c87b03e5Sespie {
228*c87b03e5Sespie e->flags &= ~EDGE_CAN_FALLTHRU;
229*c87b03e5Sespie
230*c87b03e5Sespie /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
231*c87b03e5Sespie if (e->flags & EDGE_FALLTHRU)
232*c87b03e5Sespie e->flags |= EDGE_CAN_FALLTHRU;
233*c87b03e5Sespie }
234*c87b03e5Sespie
235*c87b03e5Sespie /* If the BB ends with an invertable condjump all (2) edges are
236*c87b03e5Sespie CAN_FALLTHRU edges. */
237*c87b03e5Sespie if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next)
238*c87b03e5Sespie continue;
239*c87b03e5Sespie if (!any_condjump_p (bb->end))
240*c87b03e5Sespie continue;
241*c87b03e5Sespie if (!invert_jump (bb->end, JUMP_LABEL (bb->end), 0))
242*c87b03e5Sespie continue;
243*c87b03e5Sespie invert_jump (bb->end, JUMP_LABEL (bb->end), 0);
244*c87b03e5Sespie bb->succ->flags |= EDGE_CAN_FALLTHRU;
245*c87b03e5Sespie bb->succ->succ_next->flags |= EDGE_CAN_FALLTHRU;
246*c87b03e5Sespie }
247*c87b03e5Sespie }
248*c87b03e5Sespie
249*c87b03e5Sespie /* Return true if we need to add fake edge to exit.
250*c87b03e5Sespie Helper function for the flow_call_edges_add. */
251*c87b03e5Sespie
252*c87b03e5Sespie static bool
need_fake_edge_p(insn)253*c87b03e5Sespie need_fake_edge_p (insn)
254*c87b03e5Sespie rtx insn;
255*c87b03e5Sespie {
256*c87b03e5Sespie if (!INSN_P (insn))
257*c87b03e5Sespie return false;
258*c87b03e5Sespie
259*c87b03e5Sespie if ((GET_CODE (insn) == CALL_INSN
260*c87b03e5Sespie && !SIBLING_CALL_P (insn)
261*c87b03e5Sespie && !find_reg_note (insn, REG_NORETURN, NULL)
262*c87b03e5Sespie && !find_reg_note (insn, REG_ALWAYS_RETURN, NULL)
263*c87b03e5Sespie && !CONST_OR_PURE_CALL_P (insn)))
264*c87b03e5Sespie return true;
265*c87b03e5Sespie
266*c87b03e5Sespie return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
267*c87b03e5Sespie && MEM_VOLATILE_P (PATTERN (insn)))
268*c87b03e5Sespie || (GET_CODE (PATTERN (insn)) == PARALLEL
269*c87b03e5Sespie && asm_noperands (insn) != -1
270*c87b03e5Sespie && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
271*c87b03e5Sespie || GET_CODE (PATTERN (insn)) == ASM_INPUT);
272*c87b03e5Sespie }
273*c87b03e5Sespie
274*c87b03e5Sespie /* Add fake edges to the function exit for any non constant and non noreturn
275*c87b03e5Sespie calls, volatile inline assembly in the bitmap of blocks specified by
276*c87b03e5Sespie BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
277*c87b03e5Sespie that were split.
278*c87b03e5Sespie
279*c87b03e5Sespie The goal is to expose cases in which entering a basic block does not imply
280*c87b03e5Sespie that all subsequent instructions must be executed. */
281*c87b03e5Sespie
282*c87b03e5Sespie int
flow_call_edges_add(blocks)283*c87b03e5Sespie flow_call_edges_add (blocks)
284*c87b03e5Sespie sbitmap blocks;
285*c87b03e5Sespie {
286*c87b03e5Sespie int i;
287*c87b03e5Sespie int blocks_split = 0;
288*c87b03e5Sespie int last_bb = last_basic_block;
289*c87b03e5Sespie bool check_last_block = false;
290*c87b03e5Sespie
291*c87b03e5Sespie if (n_basic_blocks == 0)
292*c87b03e5Sespie return 0;
293*c87b03e5Sespie
294*c87b03e5Sespie if (! blocks)
295*c87b03e5Sespie check_last_block = true;
296*c87b03e5Sespie else
297*c87b03e5Sespie check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
298*c87b03e5Sespie
299*c87b03e5Sespie /* In the last basic block, before epilogue generation, there will be
300*c87b03e5Sespie a fallthru edge to EXIT. Special care is required if the last insn
301*c87b03e5Sespie of the last basic block is a call because make_edge folds duplicate
302*c87b03e5Sespie edges, which would result in the fallthru edge also being marked
303*c87b03e5Sespie fake, which would result in the fallthru edge being removed by
304*c87b03e5Sespie remove_fake_edges, which would result in an invalid CFG.
305*c87b03e5Sespie
306*c87b03e5Sespie Moreover, we can't elide the outgoing fake edge, since the block
307*c87b03e5Sespie profiler needs to take this into account in order to solve the minimal
308*c87b03e5Sespie spanning tree in the case that the call doesn't return.
309*c87b03e5Sespie
310*c87b03e5Sespie Handle this by adding a dummy instruction in a new last basic block. */
311*c87b03e5Sespie if (check_last_block)
312*c87b03e5Sespie {
313*c87b03e5Sespie basic_block bb = EXIT_BLOCK_PTR->prev_bb;
314*c87b03e5Sespie rtx insn = bb->end;
315*c87b03e5Sespie
316*c87b03e5Sespie /* Back up past insns that must be kept in the same block as a call. */
317*c87b03e5Sespie while (insn != bb->head
318*c87b03e5Sespie && keep_with_call_p (insn))
319*c87b03e5Sespie insn = PREV_INSN (insn);
320*c87b03e5Sespie
321*c87b03e5Sespie if (need_fake_edge_p (insn))
322*c87b03e5Sespie {
323*c87b03e5Sespie edge e;
324*c87b03e5Sespie
325*c87b03e5Sespie for (e = bb->succ; e; e = e->succ_next)
326*c87b03e5Sespie if (e->dest == EXIT_BLOCK_PTR)
327*c87b03e5Sespie {
328*c87b03e5Sespie insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
329*c87b03e5Sespie commit_edge_insertions ();
330*c87b03e5Sespie break;
331*c87b03e5Sespie }
332*c87b03e5Sespie }
333*c87b03e5Sespie }
334*c87b03e5Sespie
335*c87b03e5Sespie /* Now add fake edges to the function exit for any non constant
336*c87b03e5Sespie calls since there is no way that we can determine if they will
337*c87b03e5Sespie return or not... */
338*c87b03e5Sespie
339*c87b03e5Sespie for (i = 0; i < last_bb; i++)
340*c87b03e5Sespie {
341*c87b03e5Sespie basic_block bb = BASIC_BLOCK (i);
342*c87b03e5Sespie rtx insn;
343*c87b03e5Sespie rtx prev_insn;
344*c87b03e5Sespie
345*c87b03e5Sespie if (!bb)
346*c87b03e5Sespie continue;
347*c87b03e5Sespie
348*c87b03e5Sespie if (blocks && !TEST_BIT (blocks, i))
349*c87b03e5Sespie continue;
350*c87b03e5Sespie
351*c87b03e5Sespie for (insn = bb->end; ; insn = prev_insn)
352*c87b03e5Sespie {
353*c87b03e5Sespie prev_insn = PREV_INSN (insn);
354*c87b03e5Sespie if (need_fake_edge_p (insn))
355*c87b03e5Sespie {
356*c87b03e5Sespie edge e;
357*c87b03e5Sespie rtx split_at_insn = insn;
358*c87b03e5Sespie
359*c87b03e5Sespie /* Don't split the block between a call and an insn that should
360*c87b03e5Sespie remain in the same block as the call. */
361*c87b03e5Sespie if (GET_CODE (insn) == CALL_INSN)
362*c87b03e5Sespie while (split_at_insn != bb->end
363*c87b03e5Sespie && keep_with_call_p (NEXT_INSN (split_at_insn)))
364*c87b03e5Sespie split_at_insn = NEXT_INSN (split_at_insn);
365*c87b03e5Sespie
366*c87b03e5Sespie /* The handling above of the final block before the epilogue
367*c87b03e5Sespie should be enough to verify that there is no edge to the exit
368*c87b03e5Sespie block in CFG already. Calling make_edge in such case would
369*c87b03e5Sespie cause us to mark that edge as fake and remove it later. */
370*c87b03e5Sespie
371*c87b03e5Sespie #ifdef ENABLE_CHECKING
372*c87b03e5Sespie if (split_at_insn == bb->end)
373*c87b03e5Sespie for (e = bb->succ; e; e = e->succ_next)
374*c87b03e5Sespie if (e->dest == EXIT_BLOCK_PTR)
375*c87b03e5Sespie abort ();
376*c87b03e5Sespie #endif
377*c87b03e5Sespie
378*c87b03e5Sespie /* Note that the following may create a new basic block
379*c87b03e5Sespie and renumber the existing basic blocks. */
380*c87b03e5Sespie if (split_at_insn != bb->end)
381*c87b03e5Sespie {
382*c87b03e5Sespie e = split_block (bb, split_at_insn);
383*c87b03e5Sespie if (e)
384*c87b03e5Sespie blocks_split++;
385*c87b03e5Sespie }
386*c87b03e5Sespie
387*c87b03e5Sespie make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
388*c87b03e5Sespie }
389*c87b03e5Sespie
390*c87b03e5Sespie if (insn == bb->head)
391*c87b03e5Sespie break;
392*c87b03e5Sespie }
393*c87b03e5Sespie }
394*c87b03e5Sespie
395*c87b03e5Sespie if (blocks_split)
396*c87b03e5Sespie verify_flow_info ();
397*c87b03e5Sespie
398*c87b03e5Sespie return blocks_split;
399*c87b03e5Sespie }
400*c87b03e5Sespie
401*c87b03e5Sespie /* Find unreachable blocks. An unreachable block will have 0 in
402*c87b03e5Sespie the reachable bit in block->flags. A nonzero value indicates the
403*c87b03e5Sespie block is reachable. */
404*c87b03e5Sespie
405*c87b03e5Sespie void
find_unreachable_blocks()406*c87b03e5Sespie find_unreachable_blocks ()
407*c87b03e5Sespie {
408*c87b03e5Sespie edge e;
409*c87b03e5Sespie basic_block *tos, *worklist, bb;
410*c87b03e5Sespie
411*c87b03e5Sespie tos = worklist =
412*c87b03e5Sespie (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
413*c87b03e5Sespie
414*c87b03e5Sespie /* Clear all the reachability flags. */
415*c87b03e5Sespie
416*c87b03e5Sespie FOR_EACH_BB (bb)
417*c87b03e5Sespie bb->flags &= ~BB_REACHABLE;
418*c87b03e5Sespie
419*c87b03e5Sespie /* Add our starting points to the worklist. Almost always there will
420*c87b03e5Sespie be only one. It isn't inconceivable that we might one day directly
421*c87b03e5Sespie support Fortran alternate entry points. */
422*c87b03e5Sespie
423*c87b03e5Sespie for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
424*c87b03e5Sespie {
425*c87b03e5Sespie *tos++ = e->dest;
426*c87b03e5Sespie
427*c87b03e5Sespie /* Mark the block reachable. */
428*c87b03e5Sespie e->dest->flags |= BB_REACHABLE;
429*c87b03e5Sespie }
430*c87b03e5Sespie
431*c87b03e5Sespie /* Iterate: find everything reachable from what we've already seen. */
432*c87b03e5Sespie
433*c87b03e5Sespie while (tos != worklist)
434*c87b03e5Sespie {
435*c87b03e5Sespie basic_block b = *--tos;
436*c87b03e5Sespie
437*c87b03e5Sespie for (e = b->succ; e; e = e->succ_next)
438*c87b03e5Sespie if (!(e->dest->flags & BB_REACHABLE))
439*c87b03e5Sespie {
440*c87b03e5Sespie *tos++ = e->dest;
441*c87b03e5Sespie e->dest->flags |= BB_REACHABLE;
442*c87b03e5Sespie }
443*c87b03e5Sespie }
444*c87b03e5Sespie
445*c87b03e5Sespie free (worklist);
446*c87b03e5Sespie }
447*c87b03e5Sespie
448*c87b03e5Sespie /* Functions to access an edge list with a vector representation.
449*c87b03e5Sespie Enough data is kept such that given an index number, the
450*c87b03e5Sespie pred and succ that edge represents can be determined, or
451*c87b03e5Sespie given a pred and a succ, its index number can be returned.
452*c87b03e5Sespie This allows algorithms which consume a lot of memory to
453*c87b03e5Sespie represent the normally full matrix of edge (pred,succ) with a
454*c87b03e5Sespie single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
455*c87b03e5Sespie wasted space in the client code due to sparse flow graphs. */
456*c87b03e5Sespie
457*c87b03e5Sespie /* This functions initializes the edge list. Basically the entire
458*c87b03e5Sespie flowgraph is processed, and all edges are assigned a number,
459*c87b03e5Sespie and the data structure is filled in. */
460*c87b03e5Sespie
461*c87b03e5Sespie struct edge_list *
create_edge_list()462*c87b03e5Sespie create_edge_list ()
463*c87b03e5Sespie {
464*c87b03e5Sespie struct edge_list *elist;
465*c87b03e5Sespie edge e;
466*c87b03e5Sespie int num_edges;
467*c87b03e5Sespie int block_count;
468*c87b03e5Sespie basic_block bb;
469*c87b03e5Sespie
470*c87b03e5Sespie block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */
471*c87b03e5Sespie
472*c87b03e5Sespie num_edges = 0;
473*c87b03e5Sespie
474*c87b03e5Sespie /* Determine the number of edges in the flow graph by counting successor
475*c87b03e5Sespie edges on each basic block. */
476*c87b03e5Sespie FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
477*c87b03e5Sespie {
478*c87b03e5Sespie for (e = bb->succ; e; e = e->succ_next)
479*c87b03e5Sespie num_edges++;
480*c87b03e5Sespie }
481*c87b03e5Sespie
482*c87b03e5Sespie elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
483*c87b03e5Sespie elist->num_blocks = block_count;
484*c87b03e5Sespie elist->num_edges = num_edges;
485*c87b03e5Sespie elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
486*c87b03e5Sespie
487*c87b03e5Sespie num_edges = 0;
488*c87b03e5Sespie
489*c87b03e5Sespie /* Follow successors of blocks, and register these edges. */
490*c87b03e5Sespie FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
491*c87b03e5Sespie for (e = bb->succ; e; e = e->succ_next)
492*c87b03e5Sespie elist->index_to_edge[num_edges++] = e;
493*c87b03e5Sespie
494*c87b03e5Sespie return elist;
495*c87b03e5Sespie }
496*c87b03e5Sespie
497*c87b03e5Sespie /* This function free's memory associated with an edge list. */
498*c87b03e5Sespie
499*c87b03e5Sespie void
free_edge_list(elist)500*c87b03e5Sespie free_edge_list (elist)
501*c87b03e5Sespie struct edge_list *elist;
502*c87b03e5Sespie {
503*c87b03e5Sespie if (elist)
504*c87b03e5Sespie {
505*c87b03e5Sespie free (elist->index_to_edge);
506*c87b03e5Sespie free (elist);
507*c87b03e5Sespie }
508*c87b03e5Sespie }
509*c87b03e5Sespie
510*c87b03e5Sespie /* This function provides debug output showing an edge list. */
511*c87b03e5Sespie
512*c87b03e5Sespie void
print_edge_list(f,elist)513*c87b03e5Sespie print_edge_list (f, elist)
514*c87b03e5Sespie FILE *f;
515*c87b03e5Sespie struct edge_list *elist;
516*c87b03e5Sespie {
517*c87b03e5Sespie int x;
518*c87b03e5Sespie
519*c87b03e5Sespie fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
520*c87b03e5Sespie elist->num_blocks - 2, elist->num_edges);
521*c87b03e5Sespie
522*c87b03e5Sespie for (x = 0; x < elist->num_edges; x++)
523*c87b03e5Sespie {
524*c87b03e5Sespie fprintf (f, " %-4d - edge(", x);
525*c87b03e5Sespie if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
526*c87b03e5Sespie fprintf (f, "entry,");
527*c87b03e5Sespie else
528*c87b03e5Sespie fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
529*c87b03e5Sespie
530*c87b03e5Sespie if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
531*c87b03e5Sespie fprintf (f, "exit)\n");
532*c87b03e5Sespie else
533*c87b03e5Sespie fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
534*c87b03e5Sespie }
535*c87b03e5Sespie }
536*c87b03e5Sespie
537*c87b03e5Sespie /* This function provides an internal consistency check of an edge list,
538*c87b03e5Sespie verifying that all edges are present, and that there are no
539*c87b03e5Sespie extra edges. */
540*c87b03e5Sespie
541*c87b03e5Sespie void
verify_edge_list(f,elist)542*c87b03e5Sespie verify_edge_list (f, elist)
543*c87b03e5Sespie FILE *f;
544*c87b03e5Sespie struct edge_list *elist;
545*c87b03e5Sespie {
546*c87b03e5Sespie int pred, succ, index;
547*c87b03e5Sespie edge e;
548*c87b03e5Sespie basic_block bb, p, s;
549*c87b03e5Sespie
550*c87b03e5Sespie FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
551*c87b03e5Sespie {
552*c87b03e5Sespie for (e = bb->succ; e; e = e->succ_next)
553*c87b03e5Sespie {
554*c87b03e5Sespie pred = e->src->index;
555*c87b03e5Sespie succ = e->dest->index;
556*c87b03e5Sespie index = EDGE_INDEX (elist, e->src, e->dest);
557*c87b03e5Sespie if (index == EDGE_INDEX_NO_EDGE)
558*c87b03e5Sespie {
559*c87b03e5Sespie fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
560*c87b03e5Sespie continue;
561*c87b03e5Sespie }
562*c87b03e5Sespie
563*c87b03e5Sespie if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
564*c87b03e5Sespie fprintf (f, "*p* Pred for index %d should be %d not %d\n",
565*c87b03e5Sespie index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
566*c87b03e5Sespie if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
567*c87b03e5Sespie fprintf (f, "*p* Succ for index %d should be %d not %d\n",
568*c87b03e5Sespie index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
569*c87b03e5Sespie }
570*c87b03e5Sespie }
571*c87b03e5Sespie
572*c87b03e5Sespie /* We've verified that all the edges are in the list, now lets make sure
573*c87b03e5Sespie there are no spurious edges in the list. */
574*c87b03e5Sespie
575*c87b03e5Sespie FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
576*c87b03e5Sespie FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
577*c87b03e5Sespie {
578*c87b03e5Sespie int found_edge = 0;
579*c87b03e5Sespie
580*c87b03e5Sespie for (e = p->succ; e; e = e->succ_next)
581*c87b03e5Sespie if (e->dest == s)
582*c87b03e5Sespie {
583*c87b03e5Sespie found_edge = 1;
584*c87b03e5Sespie break;
585*c87b03e5Sespie }
586*c87b03e5Sespie
587*c87b03e5Sespie for (e = s->pred; e; e = e->pred_next)
588*c87b03e5Sespie if (e->src == p)
589*c87b03e5Sespie {
590*c87b03e5Sespie found_edge = 1;
591*c87b03e5Sespie break;
592*c87b03e5Sespie }
593*c87b03e5Sespie
594*c87b03e5Sespie if (EDGE_INDEX (elist, p, s)
595*c87b03e5Sespie == EDGE_INDEX_NO_EDGE && found_edge != 0)
596*c87b03e5Sespie fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
597*c87b03e5Sespie p->index, s->index);
598*c87b03e5Sespie if (EDGE_INDEX (elist, p, s)
599*c87b03e5Sespie != EDGE_INDEX_NO_EDGE && found_edge == 0)
600*c87b03e5Sespie fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
601*c87b03e5Sespie p->index, s->index, EDGE_INDEX (elist, p, s));
602*c87b03e5Sespie }
603*c87b03e5Sespie }
604*c87b03e5Sespie
605*c87b03e5Sespie /* This routine will determine what, if any, edge there is between
606*c87b03e5Sespie a specified predecessor and successor. */
607*c87b03e5Sespie
608*c87b03e5Sespie int
find_edge_index(edge_list,pred,succ)609*c87b03e5Sespie find_edge_index (edge_list, pred, succ)
610*c87b03e5Sespie struct edge_list *edge_list;
611*c87b03e5Sespie basic_block pred, succ;
612*c87b03e5Sespie {
613*c87b03e5Sespie int x;
614*c87b03e5Sespie
615*c87b03e5Sespie for (x = 0; x < NUM_EDGES (edge_list); x++)
616*c87b03e5Sespie if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
617*c87b03e5Sespie && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
618*c87b03e5Sespie return x;
619*c87b03e5Sespie
620*c87b03e5Sespie return (EDGE_INDEX_NO_EDGE);
621*c87b03e5Sespie }
622*c87b03e5Sespie
623*c87b03e5Sespie /* Dump the list of basic blocks in the bitmap NODES. */
624*c87b03e5Sespie
625*c87b03e5Sespie void
flow_nodes_print(str,nodes,file)626*c87b03e5Sespie flow_nodes_print (str, nodes, file)
627*c87b03e5Sespie const char *str;
628*c87b03e5Sespie const sbitmap nodes;
629*c87b03e5Sespie FILE *file;
630*c87b03e5Sespie {
631*c87b03e5Sespie int node;
632*c87b03e5Sespie
633*c87b03e5Sespie if (! nodes)
634*c87b03e5Sespie return;
635*c87b03e5Sespie
636*c87b03e5Sespie fprintf (file, "%s { ", str);
637*c87b03e5Sespie EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
638*c87b03e5Sespie fputs ("}\n", file);
639*c87b03e5Sespie }
640*c87b03e5Sespie
641*c87b03e5Sespie /* Dump the list of edges in the array EDGE_LIST. */
642*c87b03e5Sespie
643*c87b03e5Sespie void
flow_edge_list_print(str,edge_list,num_edges,file)644*c87b03e5Sespie flow_edge_list_print (str, edge_list, num_edges, file)
645*c87b03e5Sespie const char *str;
646*c87b03e5Sespie const edge *edge_list;
647*c87b03e5Sespie int num_edges;
648*c87b03e5Sespie FILE *file;
649*c87b03e5Sespie {
650*c87b03e5Sespie int i;
651*c87b03e5Sespie
652*c87b03e5Sespie if (! edge_list)
653*c87b03e5Sespie return;
654*c87b03e5Sespie
655*c87b03e5Sespie fprintf (file, "%s { ", str);
656*c87b03e5Sespie for (i = 0; i < num_edges; i++)
657*c87b03e5Sespie fprintf (file, "%d->%d ", edge_list[i]->src->index,
658*c87b03e5Sespie edge_list[i]->dest->index);
659*c87b03e5Sespie
660*c87b03e5Sespie fputs ("}\n", file);
661*c87b03e5Sespie }
662*c87b03e5Sespie
663*c87b03e5Sespie
664*c87b03e5Sespie /* This routine will remove any fake successor edges for a basic block.
665*c87b03e5Sespie When the edge is removed, it is also removed from whatever predecessor
666*c87b03e5Sespie list it is in. */
667*c87b03e5Sespie
668*c87b03e5Sespie static void
remove_fake_successors(bb)669*c87b03e5Sespie remove_fake_successors (bb)
670*c87b03e5Sespie basic_block bb;
671*c87b03e5Sespie {
672*c87b03e5Sespie edge e;
673*c87b03e5Sespie
674*c87b03e5Sespie for (e = bb->succ; e;)
675*c87b03e5Sespie {
676*c87b03e5Sespie edge tmp = e;
677*c87b03e5Sespie
678*c87b03e5Sespie e = e->succ_next;
679*c87b03e5Sespie if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
680*c87b03e5Sespie remove_edge (tmp);
681*c87b03e5Sespie }
682*c87b03e5Sespie }
683*c87b03e5Sespie
684*c87b03e5Sespie /* This routine will remove all fake edges from the flow graph. If
685*c87b03e5Sespie we remove all fake successors, it will automatically remove all
686*c87b03e5Sespie fake predecessors. */
687*c87b03e5Sespie
688*c87b03e5Sespie void
remove_fake_edges()689*c87b03e5Sespie remove_fake_edges ()
690*c87b03e5Sespie {
691*c87b03e5Sespie basic_block bb;
692*c87b03e5Sespie
693*c87b03e5Sespie FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
694*c87b03e5Sespie remove_fake_successors (bb);
695*c87b03e5Sespie }
696*c87b03e5Sespie
697*c87b03e5Sespie /* This function will add a fake edge between any block which has no
698*c87b03e5Sespie successors, and the exit block. Some data flow equations require these
699*c87b03e5Sespie edges to exist. */
700*c87b03e5Sespie
701*c87b03e5Sespie void
add_noreturn_fake_exit_edges()702*c87b03e5Sespie add_noreturn_fake_exit_edges ()
703*c87b03e5Sespie {
704*c87b03e5Sespie basic_block bb;
705*c87b03e5Sespie
706*c87b03e5Sespie FOR_EACH_BB (bb)
707*c87b03e5Sespie if (bb->succ == NULL)
708*c87b03e5Sespie make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
709*c87b03e5Sespie }
710*c87b03e5Sespie
711*c87b03e5Sespie /* This function adds a fake edge between any infinite loops to the
712*c87b03e5Sespie exit block. Some optimizations require a path from each node to
713*c87b03e5Sespie the exit node.
714*c87b03e5Sespie
715*c87b03e5Sespie See also Morgan, Figure 3.10, pp. 82-83.
716*c87b03e5Sespie
717*c87b03e5Sespie The current implementation is ugly, not attempting to minimize the
718*c87b03e5Sespie number of inserted fake edges. To reduce the number of fake edges
719*c87b03e5Sespie to insert, add fake edges from _innermost_ loops containing only
720*c87b03e5Sespie nodes not reachable from the exit block. */
721*c87b03e5Sespie
722*c87b03e5Sespie void
connect_infinite_loops_to_exit()723*c87b03e5Sespie connect_infinite_loops_to_exit ()
724*c87b03e5Sespie {
725*c87b03e5Sespie basic_block unvisited_block;
726*c87b03e5Sespie struct depth_first_search_dsS dfs_ds;
727*c87b03e5Sespie
728*c87b03e5Sespie /* Perform depth-first search in the reverse graph to find nodes
729*c87b03e5Sespie reachable from the exit block. */
730*c87b03e5Sespie flow_dfs_compute_reverse_init (&dfs_ds);
731*c87b03e5Sespie flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
732*c87b03e5Sespie
733*c87b03e5Sespie /* Repeatedly add fake edges, updating the unreachable nodes. */
734*c87b03e5Sespie while (1)
735*c87b03e5Sespie {
736*c87b03e5Sespie unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
737*c87b03e5Sespie if (!unvisited_block)
738*c87b03e5Sespie break;
739*c87b03e5Sespie
740*c87b03e5Sespie make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
741*c87b03e5Sespie flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
742*c87b03e5Sespie }
743*c87b03e5Sespie
744*c87b03e5Sespie flow_dfs_compute_reverse_finish (&dfs_ds);
745*c87b03e5Sespie return;
746*c87b03e5Sespie }
747*c87b03e5Sespie
748*c87b03e5Sespie /* Compute reverse top sort order */
749*c87b03e5Sespie
750*c87b03e5Sespie void
flow_reverse_top_sort_order_compute(rts_order)751*c87b03e5Sespie flow_reverse_top_sort_order_compute (rts_order)
752*c87b03e5Sespie int *rts_order;
753*c87b03e5Sespie {
754*c87b03e5Sespie edge *stack;
755*c87b03e5Sespie int sp;
756*c87b03e5Sespie int postnum = 0;
757*c87b03e5Sespie sbitmap visited;
758*c87b03e5Sespie
759*c87b03e5Sespie /* Allocate stack for back-tracking up CFG. */
760*c87b03e5Sespie stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
761*c87b03e5Sespie sp = 0;
762*c87b03e5Sespie
763*c87b03e5Sespie /* Allocate bitmap to track nodes that have been visited. */
764*c87b03e5Sespie visited = sbitmap_alloc (last_basic_block);
765*c87b03e5Sespie
766*c87b03e5Sespie /* None of the nodes in the CFG have been visited yet. */
767*c87b03e5Sespie sbitmap_zero (visited);
768*c87b03e5Sespie
769*c87b03e5Sespie /* Push the first edge on to the stack. */
770*c87b03e5Sespie stack[sp++] = ENTRY_BLOCK_PTR->succ;
771*c87b03e5Sespie
772*c87b03e5Sespie while (sp)
773*c87b03e5Sespie {
774*c87b03e5Sespie edge e;
775*c87b03e5Sespie basic_block src;
776*c87b03e5Sespie basic_block dest;
777*c87b03e5Sespie
778*c87b03e5Sespie /* Look at the edge on the top of the stack. */
779*c87b03e5Sespie e = stack[sp - 1];
780*c87b03e5Sespie src = e->src;
781*c87b03e5Sespie dest = e->dest;
782*c87b03e5Sespie
783*c87b03e5Sespie /* Check if the edge destination has been visited yet. */
784*c87b03e5Sespie if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
785*c87b03e5Sespie {
786*c87b03e5Sespie /* Mark that we have visited the destination. */
787*c87b03e5Sespie SET_BIT (visited, dest->index);
788*c87b03e5Sespie
789*c87b03e5Sespie if (dest->succ)
790*c87b03e5Sespie /* Since the DEST node has been visited for the first
791*c87b03e5Sespie time, check its successors. */
792*c87b03e5Sespie stack[sp++] = dest->succ;
793*c87b03e5Sespie else
794*c87b03e5Sespie rts_order[postnum++] = dest->index;
795*c87b03e5Sespie }
796*c87b03e5Sespie else
797*c87b03e5Sespie {
798*c87b03e5Sespie if (! e->succ_next && src != ENTRY_BLOCK_PTR)
799*c87b03e5Sespie rts_order[postnum++] = src->index;
800*c87b03e5Sespie
801*c87b03e5Sespie if (e->succ_next)
802*c87b03e5Sespie stack[sp - 1] = e->succ_next;
803*c87b03e5Sespie else
804*c87b03e5Sespie sp--;
805*c87b03e5Sespie }
806*c87b03e5Sespie }
807*c87b03e5Sespie
808*c87b03e5Sespie free (stack);
809*c87b03e5Sespie sbitmap_free (visited);
810*c87b03e5Sespie }
811*c87b03e5Sespie
812*c87b03e5Sespie /* Compute the depth first search order and store in the array
813*c87b03e5Sespie DFS_ORDER if nonzero, marking the nodes visited in VISITED. If
814*c87b03e5Sespie RC_ORDER is nonzero, return the reverse completion number for each
815*c87b03e5Sespie node. Returns the number of nodes visited. A depth first search
816*c87b03e5Sespie tries to get as far away from the starting point as quickly as
817*c87b03e5Sespie possible. */
818*c87b03e5Sespie
819*c87b03e5Sespie int
flow_depth_first_order_compute(dfs_order,rc_order)820*c87b03e5Sespie flow_depth_first_order_compute (dfs_order, rc_order)
821*c87b03e5Sespie int *dfs_order;
822*c87b03e5Sespie int *rc_order;
823*c87b03e5Sespie {
824*c87b03e5Sespie edge *stack;
825*c87b03e5Sespie int sp;
826*c87b03e5Sespie int dfsnum = 0;
827*c87b03e5Sespie int rcnum = n_basic_blocks - 1;
828*c87b03e5Sespie sbitmap visited;
829*c87b03e5Sespie
830*c87b03e5Sespie /* Allocate stack for back-tracking up CFG. */
831*c87b03e5Sespie stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
832*c87b03e5Sespie sp = 0;
833*c87b03e5Sespie
834*c87b03e5Sespie /* Allocate bitmap to track nodes that have been visited. */
835*c87b03e5Sespie visited = sbitmap_alloc (last_basic_block);
836*c87b03e5Sespie
837*c87b03e5Sespie /* None of the nodes in the CFG have been visited yet. */
838*c87b03e5Sespie sbitmap_zero (visited);
839*c87b03e5Sespie
840*c87b03e5Sespie /* Push the first edge on to the stack. */
841*c87b03e5Sespie stack[sp++] = ENTRY_BLOCK_PTR->succ;
842*c87b03e5Sespie
843*c87b03e5Sespie while (sp)
844*c87b03e5Sespie {
845*c87b03e5Sespie edge e;
846*c87b03e5Sespie basic_block src;
847*c87b03e5Sespie basic_block dest;
848*c87b03e5Sespie
849*c87b03e5Sespie /* Look at the edge on the top of the stack. */
850*c87b03e5Sespie e = stack[sp - 1];
851*c87b03e5Sespie src = e->src;
852*c87b03e5Sespie dest = e->dest;
853*c87b03e5Sespie
854*c87b03e5Sespie /* Check if the edge destination has been visited yet. */
855*c87b03e5Sespie if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
856*c87b03e5Sespie {
857*c87b03e5Sespie /* Mark that we have visited the destination. */
858*c87b03e5Sespie SET_BIT (visited, dest->index);
859*c87b03e5Sespie
860*c87b03e5Sespie if (dfs_order)
861*c87b03e5Sespie dfs_order[dfsnum] = dest->index;
862*c87b03e5Sespie
863*c87b03e5Sespie dfsnum++;
864*c87b03e5Sespie
865*c87b03e5Sespie if (dest->succ)
866*c87b03e5Sespie /* Since the DEST node has been visited for the first
867*c87b03e5Sespie time, check its successors. */
868*c87b03e5Sespie stack[sp++] = dest->succ;
869*c87b03e5Sespie else if (rc_order)
870*c87b03e5Sespie /* There are no successors for the DEST node so assign
871*c87b03e5Sespie its reverse completion number. */
872*c87b03e5Sespie rc_order[rcnum--] = dest->index;
873*c87b03e5Sespie }
874*c87b03e5Sespie else
875*c87b03e5Sespie {
876*c87b03e5Sespie if (! e->succ_next && src != ENTRY_BLOCK_PTR
877*c87b03e5Sespie && rc_order)
878*c87b03e5Sespie /* There are no more successors for the SRC node
879*c87b03e5Sespie so assign its reverse completion number. */
880*c87b03e5Sespie rc_order[rcnum--] = src->index;
881*c87b03e5Sespie
882*c87b03e5Sespie if (e->succ_next)
883*c87b03e5Sespie stack[sp - 1] = e->succ_next;
884*c87b03e5Sespie else
885*c87b03e5Sespie sp--;
886*c87b03e5Sespie }
887*c87b03e5Sespie }
888*c87b03e5Sespie
889*c87b03e5Sespie free (stack);
890*c87b03e5Sespie sbitmap_free (visited);
891*c87b03e5Sespie
892*c87b03e5Sespie /* The number of nodes visited should not be greater than
893*c87b03e5Sespie n_basic_blocks. */
894*c87b03e5Sespie if (dfsnum > n_basic_blocks)
895*c87b03e5Sespie abort ();
896*c87b03e5Sespie
897*c87b03e5Sespie /* There are some nodes left in the CFG that are unreachable. */
898*c87b03e5Sespie if (dfsnum < n_basic_blocks)
899*c87b03e5Sespie abort ();
900*c87b03e5Sespie
901*c87b03e5Sespie return dfsnum;
902*c87b03e5Sespie }
903*c87b03e5Sespie
904*c87b03e5Sespie struct dfst_node
905*c87b03e5Sespie {
906*c87b03e5Sespie unsigned nnodes;
907*c87b03e5Sespie struct dfst_node **node;
908*c87b03e5Sespie struct dfst_node *up;
909*c87b03e5Sespie };
910*c87b03e5Sespie
911*c87b03e5Sespie /* Compute a preorder transversal ordering such that a sub-tree which
912*c87b03e5Sespie is the source of a cross edge appears before the sub-tree which is
913*c87b03e5Sespie the destination of the cross edge. This allows for easy detection
914*c87b03e5Sespie of all the entry blocks for a loop.
915*c87b03e5Sespie
916*c87b03e5Sespie The ordering is compute by:
917*c87b03e5Sespie
918*c87b03e5Sespie 1) Generating a depth first spanning tree.
919*c87b03e5Sespie
920*c87b03e5Sespie 2) Walking the resulting tree from right to left. */
921*c87b03e5Sespie
922*c87b03e5Sespie void
flow_preorder_transversal_compute(pot_order)923*c87b03e5Sespie flow_preorder_transversal_compute (pot_order)
924*c87b03e5Sespie int *pot_order;
925*c87b03e5Sespie {
926*c87b03e5Sespie edge e;
927*c87b03e5Sespie edge *stack;
928*c87b03e5Sespie int i;
929*c87b03e5Sespie int max_successors;
930*c87b03e5Sespie int sp;
931*c87b03e5Sespie sbitmap visited;
932*c87b03e5Sespie struct dfst_node *node;
933*c87b03e5Sespie struct dfst_node *dfst;
934*c87b03e5Sespie basic_block bb;
935*c87b03e5Sespie
936*c87b03e5Sespie /* Allocate stack for back-tracking up CFG. */
937*c87b03e5Sespie stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
938*c87b03e5Sespie sp = 0;
939*c87b03e5Sespie
940*c87b03e5Sespie /* Allocate the tree. */
941*c87b03e5Sespie dfst = (struct dfst_node *) xcalloc (last_basic_block,
942*c87b03e5Sespie sizeof (struct dfst_node));
943*c87b03e5Sespie
944*c87b03e5Sespie FOR_EACH_BB (bb)
945*c87b03e5Sespie {
946*c87b03e5Sespie max_successors = 0;
947*c87b03e5Sespie for (e = bb->succ; e; e = e->succ_next)
948*c87b03e5Sespie max_successors++;
949*c87b03e5Sespie
950*c87b03e5Sespie dfst[bb->index].node
951*c87b03e5Sespie = (max_successors
952*c87b03e5Sespie ? (struct dfst_node **) xcalloc (max_successors,
953*c87b03e5Sespie sizeof (struct dfst_node *))
954*c87b03e5Sespie : NULL);
955*c87b03e5Sespie }
956*c87b03e5Sespie
957*c87b03e5Sespie /* Allocate bitmap to track nodes that have been visited. */
958*c87b03e5Sespie visited = sbitmap_alloc (last_basic_block);
959*c87b03e5Sespie
960*c87b03e5Sespie /* None of the nodes in the CFG have been visited yet. */
961*c87b03e5Sespie sbitmap_zero (visited);
962*c87b03e5Sespie
963*c87b03e5Sespie /* Push the first edge on to the stack. */
964*c87b03e5Sespie stack[sp++] = ENTRY_BLOCK_PTR->succ;
965*c87b03e5Sespie
966*c87b03e5Sespie while (sp)
967*c87b03e5Sespie {
968*c87b03e5Sespie basic_block src;
969*c87b03e5Sespie basic_block dest;
970*c87b03e5Sespie
971*c87b03e5Sespie /* Look at the edge on the top of the stack. */
972*c87b03e5Sespie e = stack[sp - 1];
973*c87b03e5Sespie src = e->src;
974*c87b03e5Sespie dest = e->dest;
975*c87b03e5Sespie
976*c87b03e5Sespie /* Check if the edge destination has been visited yet. */
977*c87b03e5Sespie if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
978*c87b03e5Sespie {
979*c87b03e5Sespie /* Mark that we have visited the destination. */
980*c87b03e5Sespie SET_BIT (visited, dest->index);
981*c87b03e5Sespie
982*c87b03e5Sespie /* Add the destination to the preorder tree. */
983*c87b03e5Sespie if (src != ENTRY_BLOCK_PTR)
984*c87b03e5Sespie {
985*c87b03e5Sespie dfst[src->index].node[dfst[src->index].nnodes++]
986*c87b03e5Sespie = &dfst[dest->index];
987*c87b03e5Sespie dfst[dest->index].up = &dfst[src->index];
988*c87b03e5Sespie }
989*c87b03e5Sespie
990*c87b03e5Sespie if (dest->succ)
991*c87b03e5Sespie /* Since the DEST node has been visited for the first
992*c87b03e5Sespie time, check its successors. */
993*c87b03e5Sespie stack[sp++] = dest->succ;
994*c87b03e5Sespie }
995*c87b03e5Sespie
996*c87b03e5Sespie else if (e->succ_next)
997*c87b03e5Sespie stack[sp - 1] = e->succ_next;
998*c87b03e5Sespie else
999*c87b03e5Sespie sp--;
1000*c87b03e5Sespie }
1001*c87b03e5Sespie
1002*c87b03e5Sespie free (stack);
1003*c87b03e5Sespie sbitmap_free (visited);
1004*c87b03e5Sespie
1005*c87b03e5Sespie /* Record the preorder transversal order by
1006*c87b03e5Sespie walking the tree from right to left. */
1007*c87b03e5Sespie
1008*c87b03e5Sespie i = 0;
1009*c87b03e5Sespie node = &dfst[ENTRY_BLOCK_PTR->next_bb->index];
1010*c87b03e5Sespie pot_order[i++] = 0;
1011*c87b03e5Sespie
1012*c87b03e5Sespie while (node)
1013*c87b03e5Sespie {
1014*c87b03e5Sespie if (node->nnodes)
1015*c87b03e5Sespie {
1016*c87b03e5Sespie node = node->node[--node->nnodes];
1017*c87b03e5Sespie pot_order[i++] = node - dfst;
1018*c87b03e5Sespie }
1019*c87b03e5Sespie else
1020*c87b03e5Sespie node = node->up;
1021*c87b03e5Sespie }
1022*c87b03e5Sespie
1023*c87b03e5Sespie /* Free the tree. */
1024*c87b03e5Sespie
1025*c87b03e5Sespie for (i = 0; i < last_basic_block; i++)
1026*c87b03e5Sespie if (dfst[i].node)
1027*c87b03e5Sespie free (dfst[i].node);
1028*c87b03e5Sespie
1029*c87b03e5Sespie free (dfst);
1030*c87b03e5Sespie }
1031*c87b03e5Sespie
1032*c87b03e5Sespie /* Compute the depth first search order on the _reverse_ graph and
1033*c87b03e5Sespie store in the array DFS_ORDER, marking the nodes visited in VISITED.
1034*c87b03e5Sespie Returns the number of nodes visited.
1035*c87b03e5Sespie
1036*c87b03e5Sespie The computation is split into three pieces:
1037*c87b03e5Sespie
1038*c87b03e5Sespie flow_dfs_compute_reverse_init () creates the necessary data
1039*c87b03e5Sespie structures.
1040*c87b03e5Sespie
1041*c87b03e5Sespie flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1042*c87b03e5Sespie structures. The block will start the search.
1043*c87b03e5Sespie
1044*c87b03e5Sespie flow_dfs_compute_reverse_execute () continues (or starts) the
1045*c87b03e5Sespie search using the block on the top of the stack, stopping when the
1046*c87b03e5Sespie stack is empty.
1047*c87b03e5Sespie
1048*c87b03e5Sespie flow_dfs_compute_reverse_finish () destroys the necessary data
1049*c87b03e5Sespie structures.
1050*c87b03e5Sespie
1051*c87b03e5Sespie Thus, the user will probably call ..._init(), call ..._add_bb() to
1052*c87b03e5Sespie add a beginning basic block to the stack, call ..._execute(),
1053*c87b03e5Sespie possibly add another bb to the stack and again call ..._execute(),
1054*c87b03e5Sespie ..., and finally call _finish(). */
1055*c87b03e5Sespie
1056*c87b03e5Sespie /* Initialize the data structures used for depth-first search on the
1057*c87b03e5Sespie reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1058*c87b03e5Sespie added to the basic block stack. DATA is the current depth-first
1059*c87b03e5Sespie search context. If INITIALIZE_STACK is nonzero, there is an
1060*c87b03e5Sespie element on the stack. */
1061*c87b03e5Sespie
1062*c87b03e5Sespie static void
flow_dfs_compute_reverse_init(data)1063*c87b03e5Sespie flow_dfs_compute_reverse_init (data)
1064*c87b03e5Sespie depth_first_search_ds data;
1065*c87b03e5Sespie {
1066*c87b03e5Sespie /* Allocate stack for back-tracking up CFG. */
1067*c87b03e5Sespie data->stack = (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
1068*c87b03e5Sespie * sizeof (basic_block));
1069*c87b03e5Sespie data->sp = 0;
1070*c87b03e5Sespie
1071*c87b03e5Sespie /* Allocate bitmap to track nodes that have been visited. */
1072*c87b03e5Sespie data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
1073*c87b03e5Sespie
1074*c87b03e5Sespie /* None of the nodes in the CFG have been visited yet. */
1075*c87b03e5Sespie sbitmap_zero (data->visited_blocks);
1076*c87b03e5Sespie
1077*c87b03e5Sespie return;
1078*c87b03e5Sespie }
1079*c87b03e5Sespie
1080*c87b03e5Sespie /* Add the specified basic block to the top of the dfs data
1081*c87b03e5Sespie structures. When the search continues, it will start at the
1082*c87b03e5Sespie block. */
1083*c87b03e5Sespie
1084*c87b03e5Sespie static void
flow_dfs_compute_reverse_add_bb(data,bb)1085*c87b03e5Sespie flow_dfs_compute_reverse_add_bb (data, bb)
1086*c87b03e5Sespie depth_first_search_ds data;
1087*c87b03e5Sespie basic_block bb;
1088*c87b03e5Sespie {
1089*c87b03e5Sespie data->stack[data->sp++] = bb;
1090*c87b03e5Sespie SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
1091*c87b03e5Sespie }
1092*c87b03e5Sespie
1093*c87b03e5Sespie /* Continue the depth-first search through the reverse graph starting with the
1094*c87b03e5Sespie block at the stack's top and ending when the stack is empty. Visited nodes
1095*c87b03e5Sespie are marked. Returns an unvisited basic block, or NULL if there is none
1096*c87b03e5Sespie available. */
1097*c87b03e5Sespie
1098*c87b03e5Sespie static basic_block
flow_dfs_compute_reverse_execute(data)1099*c87b03e5Sespie flow_dfs_compute_reverse_execute (data)
1100*c87b03e5Sespie depth_first_search_ds data;
1101*c87b03e5Sespie {
1102*c87b03e5Sespie basic_block bb;
1103*c87b03e5Sespie edge e;
1104*c87b03e5Sespie
1105*c87b03e5Sespie while (data->sp > 0)
1106*c87b03e5Sespie {
1107*c87b03e5Sespie bb = data->stack[--data->sp];
1108*c87b03e5Sespie
1109*c87b03e5Sespie /* Perform depth-first search on adjacent vertices. */
1110*c87b03e5Sespie for (e = bb->pred; e; e = e->pred_next)
1111*c87b03e5Sespie if (!TEST_BIT (data->visited_blocks,
1112*c87b03e5Sespie e->src->index - (INVALID_BLOCK + 1)))
1113*c87b03e5Sespie flow_dfs_compute_reverse_add_bb (data, e->src);
1114*c87b03e5Sespie }
1115*c87b03e5Sespie
1116*c87b03e5Sespie /* Determine if there are unvisited basic blocks. */
1117*c87b03e5Sespie FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
1118*c87b03e5Sespie if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
1119*c87b03e5Sespie return bb;
1120*c87b03e5Sespie
1121*c87b03e5Sespie return NULL;
1122*c87b03e5Sespie }
1123*c87b03e5Sespie
1124*c87b03e5Sespie /* Destroy the data structures needed for depth-first search on the
1125*c87b03e5Sespie reverse graph. */
1126*c87b03e5Sespie
1127*c87b03e5Sespie static void
flow_dfs_compute_reverse_finish(data)1128*c87b03e5Sespie flow_dfs_compute_reverse_finish (data)
1129*c87b03e5Sespie depth_first_search_ds data;
1130*c87b03e5Sespie {
1131*c87b03e5Sespie free (data->stack);
1132*c87b03e5Sespie sbitmap_free (data->visited_blocks);
1133*c87b03e5Sespie }
1134*c87b03e5Sespie
1135*c87b03e5Sespie /* Performs dfs search from BB over vertices satisfying PREDICATE;
1136*c87b03e5Sespie if REVERSE, go against direction of edges. Returns number of blocks
1137*c87b03e5Sespie found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1138*c87b03e5Sespie int
dfs_enumerate_from(bb,reverse,predicate,rslt,rslt_max,data)1139*c87b03e5Sespie dfs_enumerate_from (bb, reverse, predicate, rslt, rslt_max, data)
1140*c87b03e5Sespie basic_block bb;
1141*c87b03e5Sespie int reverse;
1142*c87b03e5Sespie bool (*predicate) PARAMS ((basic_block, void *));
1143*c87b03e5Sespie basic_block *rslt;
1144*c87b03e5Sespie int rslt_max;
1145*c87b03e5Sespie void *data;
1146*c87b03e5Sespie {
1147*c87b03e5Sespie basic_block *st, lbb;
1148*c87b03e5Sespie int sp = 0, tv = 0;
1149*c87b03e5Sespie
1150*c87b03e5Sespie st = xcalloc (rslt_max, sizeof (basic_block));
1151*c87b03e5Sespie rslt[tv++] = st[sp++] = bb;
1152*c87b03e5Sespie bb->flags |= BB_VISITED;
1153*c87b03e5Sespie while (sp)
1154*c87b03e5Sespie {
1155*c87b03e5Sespie edge e;
1156*c87b03e5Sespie lbb = st[--sp];
1157*c87b03e5Sespie if (reverse)
1158*c87b03e5Sespie {
1159*c87b03e5Sespie for (e = lbb->pred; e; e = e->pred_next)
1160*c87b03e5Sespie if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
1161*c87b03e5Sespie {
1162*c87b03e5Sespie if (tv == rslt_max)
1163*c87b03e5Sespie abort ();
1164*c87b03e5Sespie rslt[tv++] = st[sp++] = e->src;
1165*c87b03e5Sespie e->src->flags |= BB_VISITED;
1166*c87b03e5Sespie }
1167*c87b03e5Sespie }
1168*c87b03e5Sespie else
1169*c87b03e5Sespie {
1170*c87b03e5Sespie for (e = lbb->succ; e; e = e->succ_next)
1171*c87b03e5Sespie if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
1172*c87b03e5Sespie {
1173*c87b03e5Sespie if (tv == rslt_max)
1174*c87b03e5Sespie abort ();
1175*c87b03e5Sespie rslt[tv++] = st[sp++] = e->dest;
1176*c87b03e5Sespie e->dest->flags |= BB_VISITED;
1177*c87b03e5Sespie }
1178*c87b03e5Sespie }
1179*c87b03e5Sespie }
1180*c87b03e5Sespie free (st);
1181*c87b03e5Sespie for (sp = 0; sp < tv; sp++)
1182*c87b03e5Sespie rslt[sp]->flags &= ~BB_VISITED;
1183*c87b03e5Sespie return tv;
1184*c87b03e5Sespie }
1185