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