Mercurial > hg > CbC > CbC_gcc
annotate gcc/cfganal.c @ 158:494b0b89df80 default tip
...
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 25 May 2020 18:13:55 +0900 |
parents | 1830386684a0 |
children |
rev | line source |
---|---|
0 | 1 /* Control flow graph analysis code for GNU compiler. |
145 | 2 Copyright (C) 1987-2020 Free Software Foundation, Inc. |
0 | 3 |
4 This file is part of GCC. | |
5 | |
6 GCC is free software; you can redistribute it and/or modify it under | |
7 the terms of the GNU General Public License as published by the Free | |
8 Software Foundation; either version 3, or (at your option) any later | |
9 version. | |
10 | |
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 for more details. | |
15 | |
16 You should have received a copy of the GNU General Public License | |
17 along with GCC; see the file COPYING3. If not see | |
18 <http://www.gnu.org/licenses/>. */ | |
19 | |
20 /* This file contains various simple utilities to analyze the CFG. */ | |
111 | 21 |
0 | 22 #include "config.h" |
23 #include "system.h" | |
24 #include "coretypes.h" | |
111 | 25 #include "backend.h" |
26 #include "cfghooks.h" | |
0 | 27 #include "timevar.h" |
111 | 28 #include "cfganal.h" |
29 #include "cfgloop.h" | |
0 | 30 |
111 | 31 namespace { |
0 | 32 /* Store the data structures necessary for depth-first search. */ |
111 | 33 class depth_first_search |
34 { | |
35 public: | |
36 depth_first_search (); | |
37 | |
38 basic_block execute (basic_block); | |
39 void add_bb (basic_block); | |
40 | |
41 private: | |
0 | 42 /* stack for backtracking during the algorithm */ |
111 | 43 auto_vec<basic_block, 20> m_stack; |
0 | 44 |
45 /* record of basic blocks already seen by depth-first search */ | |
111 | 46 auto_sbitmap m_visited_blocks; |
0 | 47 }; |
48 } | |
49 | |
50 /* Mark the back edges in DFS traversal. | |
51 Return nonzero if a loop (natural or otherwise) is present. | |
52 Inspired by Depth_First_Search_PP described in: | |
53 | |
54 Advanced Compiler Design and Implementation | |
55 Steven Muchnick | |
56 Morgan Kaufmann, 1997 | |
57 | |
58 and heavily borrowed from pre_and_rev_post_order_compute. */ | |
59 | |
60 bool | |
61 mark_dfs_back_edges (void) | |
62 { | |
63 int *pre; | |
64 int *post; | |
65 int prenum = 1; | |
66 int postnum = 1; | |
67 bool found = false; | |
68 | |
69 /* Allocate the preorder and postorder number arrays. */ | |
111 | 70 pre = XCNEWVEC (int, last_basic_block_for_fn (cfun)); |
71 post = XCNEWVEC (int, last_basic_block_for_fn (cfun)); | |
0 | 72 |
73 /* Allocate stack for back-tracking up CFG. */ | |
111 | 74 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1); |
0 | 75 |
76 /* Allocate bitmap to track nodes that have been visited. */ | |
111 | 77 auto_sbitmap visited (last_basic_block_for_fn (cfun)); |
0 | 78 |
79 /* None of the nodes in the CFG have been visited yet. */ | |
111 | 80 bitmap_clear (visited); |
0 | 81 |
82 /* Push the first edge on to the stack. */ | |
111 | 83 stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)); |
0 | 84 |
111 | 85 while (!stack.is_empty ()) |
0 | 86 { |
87 basic_block src; | |
88 basic_block dest; | |
89 | |
90 /* Look at the edge on the top of the stack. */ | |
111 | 91 edge_iterator ei = stack.last (); |
0 | 92 src = ei_edge (ei)->src; |
93 dest = ei_edge (ei)->dest; | |
94 ei_edge (ei)->flags &= ~EDGE_DFS_BACK; | |
95 | |
96 /* Check if the edge destination has been visited yet. */ | |
111 | 97 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && ! bitmap_bit_p (visited, |
98 dest->index)) | |
0 | 99 { |
100 /* Mark that we have visited the destination. */ | |
111 | 101 bitmap_set_bit (visited, dest->index); |
0 | 102 |
103 pre[dest->index] = prenum++; | |
104 if (EDGE_COUNT (dest->succs) > 0) | |
105 { | |
106 /* Since the DEST node has been visited for the first | |
107 time, check its successors. */ | |
111 | 108 stack.quick_push (ei_start (dest->succs)); |
0 | 109 } |
110 else | |
111 post[dest->index] = postnum++; | |
112 } | |
113 else | |
114 { | |
111 | 115 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun) |
116 && src != ENTRY_BLOCK_PTR_FOR_FN (cfun) | |
0 | 117 && pre[src->index] >= pre[dest->index] |
118 && post[dest->index] == 0) | |
119 ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true; | |
120 | |
111 | 121 if (ei_one_before_end_p (ei) |
122 && src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) | |
0 | 123 post[src->index] = postnum++; |
124 | |
125 if (!ei_one_before_end_p (ei)) | |
111 | 126 ei_next (&stack.last ()); |
0 | 127 else |
111 | 128 stack.pop (); |
0 | 129 } |
130 } | |
131 | |
132 free (pre); | |
133 free (post); | |
134 | |
135 return found; | |
136 } | |
137 | |
138 /* Find unreachable blocks. An unreachable block will have 0 in | |
139 the reachable bit in block->flags. A nonzero value indicates the | |
140 block is reachable. */ | |
141 | |
142 void | |
143 find_unreachable_blocks (void) | |
144 { | |
145 edge e; | |
146 edge_iterator ei; | |
147 basic_block *tos, *worklist, bb; | |
148 | |
111 | 149 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); |
0 | 150 |
151 /* Clear all the reachability flags. */ | |
152 | |
111 | 153 FOR_EACH_BB_FN (bb, cfun) |
0 | 154 bb->flags &= ~BB_REACHABLE; |
155 | |
156 /* Add our starting points to the worklist. Almost always there will | |
157 be only one. It isn't inconceivable that we might one day directly | |
158 support Fortran alternate entry points. */ | |
159 | |
111 | 160 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) |
0 | 161 { |
162 *tos++ = e->dest; | |
163 | |
164 /* Mark the block reachable. */ | |
165 e->dest->flags |= BB_REACHABLE; | |
166 } | |
167 | |
168 /* Iterate: find everything reachable from what we've already seen. */ | |
169 | |
170 while (tos != worklist) | |
171 { | |
172 basic_block b = *--tos; | |
173 | |
174 FOR_EACH_EDGE (e, ei, b->succs) | |
175 { | |
176 basic_block dest = e->dest; | |
177 | |
178 if (!(dest->flags & BB_REACHABLE)) | |
179 { | |
180 *tos++ = dest; | |
181 dest->flags |= BB_REACHABLE; | |
182 } | |
183 } | |
184 } | |
185 | |
186 free (worklist); | |
187 } | |
111 | 188 |
189 /* Verify that there are no unreachable blocks in the current function. */ | |
190 | |
191 void | |
192 verify_no_unreachable_blocks (void) | |
193 { | |
194 find_unreachable_blocks (); | |
195 | |
196 basic_block bb; | |
197 FOR_EACH_BB_FN (bb, cfun) | |
198 gcc_assert ((bb->flags & BB_REACHABLE) != 0); | |
199 } | |
200 | |
0 | 201 |
202 /* Functions to access an edge list with a vector representation. | |
203 Enough data is kept such that given an index number, the | |
204 pred and succ that edge represents can be determined, or | |
205 given a pred and a succ, its index number can be returned. | |
206 This allows algorithms which consume a lot of memory to | |
207 represent the normally full matrix of edge (pred,succ) with a | |
208 single indexed vector, edge (EDGE_INDEX (pred, succ)), with no | |
209 wasted space in the client code due to sparse flow graphs. */ | |
210 | |
211 /* This functions initializes the edge list. Basically the entire | |
212 flowgraph is processed, and all edges are assigned a number, | |
213 and the data structure is filled in. */ | |
214 | |
215 struct edge_list * | |
216 create_edge_list (void) | |
217 { | |
218 struct edge_list *elist; | |
219 edge e; | |
220 int num_edges; | |
221 basic_block bb; | |
222 edge_iterator ei; | |
223 | |
224 /* Determine the number of edges in the flow graph by counting successor | |
225 edges on each basic block. */ | |
111 | 226 num_edges = 0; |
227 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), | |
228 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
0 | 229 { |
230 num_edges += EDGE_COUNT (bb->succs); | |
231 } | |
232 | |
233 elist = XNEW (struct edge_list); | |
234 elist->num_edges = num_edges; | |
235 elist->index_to_edge = XNEWVEC (edge, num_edges); | |
236 | |
237 num_edges = 0; | |
238 | |
239 /* Follow successors of blocks, and register these edges. */ | |
111 | 240 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), |
241 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
0 | 242 FOR_EACH_EDGE (e, ei, bb->succs) |
243 elist->index_to_edge[num_edges++] = e; | |
244 | |
245 return elist; | |
246 } | |
247 | |
248 /* This function free's memory associated with an edge list. */ | |
249 | |
250 void | |
251 free_edge_list (struct edge_list *elist) | |
252 { | |
253 if (elist) | |
254 { | |
255 free (elist->index_to_edge); | |
256 free (elist); | |
257 } | |
258 } | |
259 | |
260 /* This function provides debug output showing an edge list. */ | |
261 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
262 DEBUG_FUNCTION void |
0 | 263 print_edge_list (FILE *f, struct edge_list *elist) |
264 { | |
265 int x; | |
266 | |
267 fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n", | |
111 | 268 n_basic_blocks_for_fn (cfun), elist->num_edges); |
0 | 269 |
270 for (x = 0; x < elist->num_edges; x++) | |
271 { | |
272 fprintf (f, " %-4d - edge(", x); | |
111 | 273 if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
0 | 274 fprintf (f, "entry,"); |
275 else | |
276 fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index); | |
277 | |
111 | 278 if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR_FOR_FN (cfun)) |
0 | 279 fprintf (f, "exit)\n"); |
280 else | |
281 fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index); | |
282 } | |
283 } | |
284 | |
285 /* This function provides an internal consistency check of an edge list, | |
286 verifying that all edges are present, and that there are no | |
287 extra edges. */ | |
288 | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
289 DEBUG_FUNCTION void |
0 | 290 verify_edge_list (FILE *f, struct edge_list *elist) |
291 { | |
292 int pred, succ, index; | |
293 edge e; | |
294 basic_block bb, p, s; | |
295 edge_iterator ei; | |
296 | |
111 | 297 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), |
298 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
0 | 299 { |
300 FOR_EACH_EDGE (e, ei, bb->succs) | |
301 { | |
302 pred = e->src->index; | |
303 succ = e->dest->index; | |
304 index = EDGE_INDEX (elist, e->src, e->dest); | |
305 if (index == EDGE_INDEX_NO_EDGE) | |
306 { | |
307 fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ); | |
308 continue; | |
309 } | |
310 | |
311 if (INDEX_EDGE_PRED_BB (elist, index)->index != pred) | |
312 fprintf (f, "*p* Pred for index %d should be %d not %d\n", | |
313 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index); | |
314 if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ) | |
315 fprintf (f, "*p* Succ for index %d should be %d not %d\n", | |
316 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index); | |
317 } | |
318 } | |
319 | |
320 /* We've verified that all the edges are in the list, now lets make sure | |
111 | 321 there are no spurious edges in the list. This is an expensive check! */ |
0 | 322 |
111 | 323 FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR_FOR_FN (cfun), |
324 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
325 FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb) | |
0 | 326 { |
327 int found_edge = 0; | |
328 | |
329 FOR_EACH_EDGE (e, ei, p->succs) | |
330 if (e->dest == s) | |
331 { | |
332 found_edge = 1; | |
333 break; | |
334 } | |
335 | |
336 FOR_EACH_EDGE (e, ei, s->preds) | |
337 if (e->src == p) | |
338 { | |
339 found_edge = 1; | |
340 break; | |
341 } | |
342 | |
343 if (EDGE_INDEX (elist, p, s) | |
344 == EDGE_INDEX_NO_EDGE && found_edge != 0) | |
345 fprintf (f, "*** Edge (%d, %d) appears to not have an index\n", | |
346 p->index, s->index); | |
347 if (EDGE_INDEX (elist, p, s) | |
348 != EDGE_INDEX_NO_EDGE && found_edge == 0) | |
349 fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n", | |
350 p->index, s->index, EDGE_INDEX (elist, p, s)); | |
351 } | |
352 } | |
353 | |
111 | 354 |
355 /* Functions to compute control dependences. */ | |
356 | |
357 /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */ | |
358 void | |
359 control_dependences::set_control_dependence_map_bit (basic_block bb, | |
360 int edge_index) | |
361 { | |
362 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) | |
363 return; | |
364 gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
365 bitmap_set_bit (control_dependence_map[bb->index], edge_index); | |
366 } | |
367 | |
368 /* Clear all control dependences for block BB. */ | |
369 void | |
370 control_dependences::clear_control_dependence_bitmap (basic_block bb) | |
371 { | |
372 bitmap_clear (control_dependence_map[bb->index]); | |
373 } | |
374 | |
375 /* Find the immediate postdominator PDOM of the specified basic block BLOCK. | |
376 This function is necessary because some blocks have negative numbers. */ | |
377 | |
378 static inline basic_block | |
379 find_pdom (basic_block block) | |
380 { | |
381 gcc_assert (block != ENTRY_BLOCK_PTR_FOR_FN (cfun)); | |
382 | |
383 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
384 return EXIT_BLOCK_PTR_FOR_FN (cfun); | |
385 else | |
386 { | |
387 basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block); | |
388 if (! bb) | |
389 return EXIT_BLOCK_PTR_FOR_FN (cfun); | |
390 return bb; | |
391 } | |
392 } | |
393 | |
394 /* Determine all blocks' control dependences on the given edge with edge_list | |
395 EL index EDGE_INDEX, ala Morgan, Section 3.6. */ | |
396 | |
397 void | |
398 control_dependences::find_control_dependence (int edge_index) | |
399 { | |
400 basic_block current_block; | |
401 basic_block ending_block; | |
402 | |
403 gcc_assert (get_edge_src (edge_index) != EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
404 | |
405 /* For abnormal edges, we don't make current_block control | |
406 dependent because instructions that throw are always necessary | |
407 anyway. */ | |
408 edge e = find_edge (get_edge_src (edge_index), get_edge_dest (edge_index)); | |
409 if (e->flags & EDGE_ABNORMAL) | |
410 return; | |
411 | |
412 if (get_edge_src (edge_index) == ENTRY_BLOCK_PTR_FOR_FN (cfun)) | |
413 ending_block = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); | |
414 else | |
415 ending_block = find_pdom (get_edge_src (edge_index)); | |
416 | |
417 for (current_block = get_edge_dest (edge_index); | |
418 current_block != ending_block | |
419 && current_block != EXIT_BLOCK_PTR_FOR_FN (cfun); | |
420 current_block = find_pdom (current_block)) | |
421 set_control_dependence_map_bit (current_block, edge_index); | |
422 } | |
423 | |
424 /* Record all blocks' control dependences on all edges in the edge | |
425 list EL, ala Morgan, Section 3.6. */ | |
426 | |
427 control_dependences::control_dependences () | |
428 { | |
429 timevar_push (TV_CONTROL_DEPENDENCES); | |
430 | |
431 /* Initialize the edge list. */ | |
432 int num_edges = 0; | |
433 basic_block bb; | |
434 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), | |
435 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
436 num_edges += EDGE_COUNT (bb->succs); | |
437 m_el.create (num_edges); | |
438 edge e; | |
439 edge_iterator ei; | |
440 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), | |
441 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
442 FOR_EACH_EDGE (e, ei, bb->succs) | |
443 m_el.quick_push (std::make_pair (e->src->index, e->dest->index)); | |
444 | |
445 control_dependence_map.create (last_basic_block_for_fn (cfun)); | |
446 for (int i = 0; i < last_basic_block_for_fn (cfun); ++i) | |
447 control_dependence_map.quick_push (BITMAP_ALLOC (NULL)); | |
448 for (int i = 0; i < num_edges; ++i) | |
449 find_control_dependence (i); | |
450 | |
451 timevar_pop (TV_CONTROL_DEPENDENCES); | |
452 } | |
453 | |
454 /* Free control dependences and the associated edge list. */ | |
455 | |
456 control_dependences::~control_dependences () | |
457 { | |
458 for (unsigned i = 0; i < control_dependence_map.length (); ++i) | |
459 BITMAP_FREE (control_dependence_map[i]); | |
460 control_dependence_map.release (); | |
461 m_el.release (); | |
462 } | |
463 | |
464 /* Returns the bitmap of edges the basic-block I is dependent on. */ | |
465 | |
466 bitmap | |
467 control_dependences::get_edges_dependent_on (int i) | |
468 { | |
469 return control_dependence_map[i]; | |
470 } | |
471 | |
472 /* Returns the edge source with index I from the edge list. */ | |
473 | |
474 basic_block | |
475 control_dependences::get_edge_src (int i) | |
476 { | |
477 return BASIC_BLOCK_FOR_FN (cfun, m_el[i].first); | |
478 } | |
479 | |
480 /* Returns the edge destination with index I from the edge list. */ | |
481 | |
482 basic_block | |
483 control_dependences::get_edge_dest (int i) | |
484 { | |
485 return BASIC_BLOCK_FOR_FN (cfun, m_el[i].second); | |
486 } | |
487 | |
488 | |
0 | 489 /* Given PRED and SUCC blocks, return the edge which connects the blocks. |
490 If no such edge exists, return NULL. */ | |
491 | |
492 edge | |
493 find_edge (basic_block pred, basic_block succ) | |
494 { | |
495 edge e; | |
496 edge_iterator ei; | |
497 | |
498 if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds)) | |
499 { | |
500 FOR_EACH_EDGE (e, ei, pred->succs) | |
501 if (e->dest == succ) | |
502 return e; | |
503 } | |
504 else | |
505 { | |
506 FOR_EACH_EDGE (e, ei, succ->preds) | |
507 if (e->src == pred) | |
508 return e; | |
509 } | |
510 | |
511 return NULL; | |
512 } | |
513 | |
514 /* This routine will determine what, if any, edge there is between | |
515 a specified predecessor and successor. */ | |
516 | |
517 int | |
518 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ) | |
519 { | |
520 int x; | |
521 | |
522 for (x = 0; x < NUM_EDGES (edge_list); x++) | |
523 if (INDEX_EDGE_PRED_BB (edge_list, x) == pred | |
524 && INDEX_EDGE_SUCC_BB (edge_list, x) == succ) | |
525 return x; | |
526 | |
527 return (EDGE_INDEX_NO_EDGE); | |
528 } | |
529 | |
530 /* This routine will remove any fake predecessor edges for a basic block. | |
531 When the edge is removed, it is also removed from whatever successor | |
532 list it is in. */ | |
533 | |
534 static void | |
535 remove_fake_predecessors (basic_block bb) | |
536 { | |
537 edge e; | |
538 edge_iterator ei; | |
539 | |
540 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) | |
541 { | |
542 if ((e->flags & EDGE_FAKE) == EDGE_FAKE) | |
543 remove_edge (e); | |
544 else | |
545 ei_next (&ei); | |
546 } | |
547 } | |
548 | |
549 /* This routine will remove all fake edges from the flow graph. If | |
550 we remove all fake successors, it will automatically remove all | |
551 fake predecessors. */ | |
552 | |
553 void | |
554 remove_fake_edges (void) | |
555 { | |
556 basic_block bb; | |
557 | |
111 | 558 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb) |
0 | 559 remove_fake_predecessors (bb); |
560 } | |
561 | |
562 /* This routine will remove all fake edges to the EXIT_BLOCK. */ | |
563 | |
564 void | |
565 remove_fake_exit_edges (void) | |
566 { | |
111 | 567 remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun)); |
0 | 568 } |
569 | |
570 | |
571 /* This function will add a fake edge between any block which has no | |
572 successors, and the exit block. Some data flow equations require these | |
573 edges to exist. */ | |
574 | |
575 void | |
576 add_noreturn_fake_exit_edges (void) | |
577 { | |
578 basic_block bb; | |
579 | |
111 | 580 FOR_EACH_BB_FN (bb, cfun) |
0 | 581 if (EDGE_COUNT (bb->succs) == 0) |
111 | 582 make_single_succ_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE); |
0 | 583 } |
584 | |
585 /* This function adds a fake edge between any infinite loops to the | |
586 exit block. Some optimizations require a path from each node to | |
587 the exit node. | |
588 | |
589 See also Morgan, Figure 3.10, pp. 82-83. | |
590 | |
591 The current implementation is ugly, not attempting to minimize the | |
592 number of inserted fake edges. To reduce the number of fake edges | |
593 to insert, add fake edges from _innermost_ loops containing only | |
594 nodes not reachable from the exit block. */ | |
595 | |
596 void | |
597 connect_infinite_loops_to_exit (void) | |
598 { | |
599 /* Perform depth-first search in the reverse graph to find nodes | |
600 reachable from the exit block. */ | |
111 | 601 depth_first_search dfs; |
602 dfs.add_bb (EXIT_BLOCK_PTR_FOR_FN (cfun)); | |
0 | 603 |
604 /* Repeatedly add fake edges, updating the unreachable nodes. */ | |
111 | 605 basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun); |
0 | 606 while (1) |
607 { | |
111 | 608 unvisited_block = dfs.execute (unvisited_block); |
0 | 609 if (!unvisited_block) |
610 break; | |
611 | |
111 | 612 basic_block deadend_block = dfs_find_deadend (unvisited_block); |
613 edge e = make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun), | |
614 EDGE_FAKE); | |
615 e->probability = profile_probability::never (); | |
616 dfs.add_bb (deadend_block); | |
0 | 617 } |
618 } | |
619 | |
620 /* Compute reverse top sort order. This is computing a post order | |
111 | 621 numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then |
0 | 622 ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is |
623 true, unreachable blocks are deleted. */ | |
624 | |
625 int | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
626 post_order_compute (int *post_order, bool include_entry_exit, |
0 | 627 bool delete_unreachable) |
628 { | |
629 int post_order_num = 0; | |
630 int count; | |
631 | |
632 if (include_entry_exit) | |
633 post_order[post_order_num++] = EXIT_BLOCK; | |
634 | |
635 /* Allocate stack for back-tracking up CFG. */ | |
111 | 636 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1); |
0 | 637 |
638 /* Allocate bitmap to track nodes that have been visited. */ | |
111 | 639 auto_sbitmap visited (last_basic_block_for_fn (cfun)); |
0 | 640 |
641 /* None of the nodes in the CFG have been visited yet. */ | |
111 | 642 bitmap_clear (visited); |
0 | 643 |
644 /* Push the first edge on to the stack. */ | |
111 | 645 stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)); |
0 | 646 |
111 | 647 while (!stack.is_empty ()) |
0 | 648 { |
649 basic_block src; | |
650 basic_block dest; | |
651 | |
652 /* Look at the edge on the top of the stack. */ | |
111 | 653 edge_iterator ei = stack.last (); |
0 | 654 src = ei_edge (ei)->src; |
655 dest = ei_edge (ei)->dest; | |
656 | |
657 /* Check if the edge destination has been visited yet. */ | |
111 | 658 if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun) |
659 && ! bitmap_bit_p (visited, dest->index)) | |
0 | 660 { |
661 /* Mark that we have visited the destination. */ | |
111 | 662 bitmap_set_bit (visited, dest->index); |
0 | 663 |
664 if (EDGE_COUNT (dest->succs) > 0) | |
665 /* Since the DEST node has been visited for the first | |
666 time, check its successors. */ | |
111 | 667 stack.quick_push (ei_start (dest->succs)); |
0 | 668 else |
669 post_order[post_order_num++] = dest->index; | |
670 } | |
671 else | |
672 { | |
111 | 673 if (ei_one_before_end_p (ei) |
674 && src != ENTRY_BLOCK_PTR_FOR_FN (cfun)) | |
0 | 675 post_order[post_order_num++] = src->index; |
676 | |
677 if (!ei_one_before_end_p (ei)) | |
111 | 678 ei_next (&stack.last ()); |
0 | 679 else |
111 | 680 stack.pop (); |
0 | 681 } |
682 } | |
683 | |
684 if (include_entry_exit) | |
685 { | |
686 post_order[post_order_num++] = ENTRY_BLOCK; | |
687 count = post_order_num; | |
688 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
689 else |
0 | 690 count = post_order_num + 2; |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
691 |
0 | 692 /* Delete the unreachable blocks if some were found and we are |
693 supposed to do it. */ | |
111 | 694 if (delete_unreachable && (count != n_basic_blocks_for_fn (cfun))) |
0 | 695 { |
696 basic_block b; | |
697 basic_block next_bb; | |
111 | 698 for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b |
699 != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb) | |
0 | 700 { |
701 next_bb = b->next_bb; | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
702 |
111 | 703 if (!(bitmap_bit_p (visited, b->index))) |
0 | 704 delete_basic_block (b); |
705 } | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
706 |
0 | 707 tidy_fallthru_edges (); |
708 } | |
709 | |
710 return post_order_num; | |
711 } | |
712 | |
713 | |
111 | 714 /* Helper routine for inverted_post_order_compute |
715 flow_dfs_compute_reverse_execute, and the reverse-CFG | |
716 deapth first search in dominance.c. | |
0 | 717 BB has to belong to a region of CFG |
718 unreachable by inverted traversal from the exit. | |
719 i.e. there's no control flow path from ENTRY to EXIT | |
720 that contains this BB. | |
721 This can happen in two cases - if there's an infinite loop | |
722 or if there's a block that has no successor | |
723 (call to a function with no return). | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
724 Some RTL passes deal with this condition by |
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
725 calling connect_infinite_loops_to_exit () and/or |
0 | 726 add_noreturn_fake_exit_edges (). |
727 However, those methods involve modifying the CFG itself | |
728 which may not be desirable. | |
729 Hence, we deal with the infinite loop/no return cases | |
730 by identifying a unique basic block that can reach all blocks | |
731 in such a region by inverted traversal. | |
732 This function returns a basic block that guarantees | |
733 that all blocks in the region are reachable | |
734 by starting an inverted traversal from the returned block. */ | |
735 | |
111 | 736 basic_block |
0 | 737 dfs_find_deadend (basic_block bb) |
738 { | |
111 | 739 auto_bitmap visited; |
740 basic_block next = bb; | |
0 | 741 |
742 for (;;) | |
743 { | |
111 | 744 if (EDGE_COUNT (next->succs) == 0) |
745 return next; | |
746 | |
747 if (! bitmap_set_bit (visited, next->index)) | |
748 return bb; | |
0 | 749 |
111 | 750 bb = next; |
751 /* If we are in an analyzed cycle make sure to try exiting it. | |
752 Note this is a heuristic only and expected to work when loop | |
753 fixup is needed as well. */ | |
754 if (! bb->loop_father | |
755 || ! loop_outer (bb->loop_father)) | |
756 next = EDGE_SUCC (bb, 0)->dest; | |
757 else | |
758 { | |
759 edge_iterator ei; | |
760 edge e; | |
761 FOR_EACH_EDGE (e, ei, bb->succs) | |
762 if (loop_exit_edge_p (bb->loop_father, e)) | |
763 break; | |
764 next = e ? e->dest : EDGE_SUCC (bb, 0)->dest; | |
765 } | |
0 | 766 } |
767 | |
768 gcc_unreachable (); | |
769 } | |
770 | |
771 | |
772 /* Compute the reverse top sort order of the inverted CFG | |
773 i.e. starting from the exit block and following the edges backward | |
774 (from successors to predecessors). | |
775 This ordering can be used for forward dataflow problems among others. | |
776 | |
111 | 777 Optionally if START_POINTS is specified, start from exit block and all |
778 basic blocks in START_POINTS. This is used by CD-DCE. | |
779 | |
0 | 780 This function assumes that all blocks in the CFG are reachable |
781 from the ENTRY (but not necessarily from EXIT). | |
782 | |
783 If there's an infinite loop, | |
784 a simple inverted traversal starting from the blocks | |
785 with no successors can't visit all blocks. | |
786 To solve this problem, we first do inverted traversal | |
787 starting from the blocks with no successor. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
788 And if there's any block left that's not visited by the regular |
0 | 789 inverted traversal from EXIT, |
790 those blocks are in such problematic region. | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
791 Among those, we find one block that has |
0 | 792 any visited predecessor (which is an entry into such a region), |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
793 and start looking for a "dead end" from that block |
0 | 794 and do another inverted traversal from that block. */ |
795 | |
111 | 796 void |
797 inverted_post_order_compute (vec<int> *post_order, | |
798 sbitmap *start_points) | |
0 | 799 { |
800 basic_block bb; | |
111 | 801 post_order->reserve_exact (n_basic_blocks_for_fn (cfun)); |
802 | |
803 if (flag_checking) | |
804 verify_no_unreachable_blocks (); | |
0 | 805 |
806 /* Allocate stack for back-tracking up CFG. */ | |
111 | 807 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1); |
0 | 808 |
809 /* Allocate bitmap to track nodes that have been visited. */ | |
111 | 810 auto_sbitmap visited (last_basic_block_for_fn (cfun)); |
0 | 811 |
812 /* None of the nodes in the CFG have been visited yet. */ | |
111 | 813 bitmap_clear (visited); |
0 | 814 |
111 | 815 if (start_points) |
816 { | |
817 FOR_ALL_BB_FN (bb, cfun) | |
818 if (bitmap_bit_p (*start_points, bb->index) | |
819 && EDGE_COUNT (bb->preds) > 0) | |
820 { | |
821 stack.quick_push (ei_start (bb->preds)); | |
822 bitmap_set_bit (visited, bb->index); | |
823 } | |
824 if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)) | |
825 { | |
826 stack.quick_push (ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)); | |
827 bitmap_set_bit (visited, EXIT_BLOCK_PTR_FOR_FN (cfun)->index); | |
828 } | |
829 } | |
830 else | |
0 | 831 /* Put all blocks that have no successor into the initial work list. */ |
111 | 832 FOR_ALL_BB_FN (bb, cfun) |
0 | 833 if (EDGE_COUNT (bb->succs) == 0) |
834 { | |
835 /* Push the initial edge on to the stack. */ | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
836 if (EDGE_COUNT (bb->preds) > 0) |
0 | 837 { |
111 | 838 stack.quick_push (ei_start (bb->preds)); |
839 bitmap_set_bit (visited, bb->index); | |
0 | 840 } |
841 } | |
842 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
843 do |
0 | 844 { |
845 bool has_unvisited_bb = false; | |
846 | |
847 /* The inverted traversal loop. */ | |
111 | 848 while (!stack.is_empty ()) |
0 | 849 { |
850 edge_iterator ei; | |
851 basic_block pred; | |
852 | |
853 /* Look at the edge on the top of the stack. */ | |
111 | 854 ei = stack.last (); |
0 | 855 bb = ei_edge (ei)->dest; |
856 pred = ei_edge (ei)->src; | |
857 | |
858 /* Check if the predecessor has been visited yet. */ | |
111 | 859 if (! bitmap_bit_p (visited, pred->index)) |
0 | 860 { |
861 /* Mark that we have visited the destination. */ | |
111 | 862 bitmap_set_bit (visited, pred->index); |
0 | 863 |
864 if (EDGE_COUNT (pred->preds) > 0) | |
865 /* Since the predecessor node has been visited for the first | |
866 time, check its predecessors. */ | |
111 | 867 stack.quick_push (ei_start (pred->preds)); |
0 | 868 else |
111 | 869 post_order->quick_push (pred->index); |
0 | 870 } |
871 else | |
872 { | |
111 | 873 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun) |
874 && ei_one_before_end_p (ei)) | |
875 post_order->quick_push (bb->index); | |
0 | 876 |
877 if (!ei_one_before_end_p (ei)) | |
111 | 878 ei_next (&stack.last ()); |
0 | 879 else |
111 | 880 stack.pop (); |
0 | 881 } |
882 } | |
883 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
884 /* Detect any infinite loop and activate the kludge. |
0 | 885 Note that this doesn't check EXIT_BLOCK itself |
111 | 886 since EXIT_BLOCK is always added after the outer do-while loop. */ |
887 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), | |
888 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) | |
889 if (!bitmap_bit_p (visited, bb->index)) | |
0 | 890 { |
891 has_unvisited_bb = true; | |
892 | |
893 if (EDGE_COUNT (bb->preds) > 0) | |
894 { | |
895 edge_iterator ei; | |
896 edge e; | |
897 basic_block visited_pred = NULL; | |
898 | |
899 /* Find an already visited predecessor. */ | |
900 FOR_EACH_EDGE (e, ei, bb->preds) | |
901 { | |
111 | 902 if (bitmap_bit_p (visited, e->src->index)) |
0 | 903 visited_pred = e->src; |
904 } | |
905 | |
906 if (visited_pred) | |
907 { | |
908 basic_block be = dfs_find_deadend (bb); | |
909 gcc_assert (be != NULL); | |
111 | 910 bitmap_set_bit (visited, be->index); |
911 stack.quick_push (ei_start (be->preds)); | |
0 | 912 break; |
913 } | |
914 } | |
915 } | |
916 | |
111 | 917 if (has_unvisited_bb && stack.is_empty ()) |
0 | 918 { |
111 | 919 /* No blocks are reachable from EXIT at all. |
0 | 920 Find a dead-end from the ENTRY, and restart the iteration. */ |
111 | 921 basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun)); |
0 | 922 gcc_assert (be != NULL); |
111 | 923 bitmap_set_bit (visited, be->index); |
924 stack.quick_push (ei_start (be->preds)); | |
0 | 925 } |
926 | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
927 /* The only case the below while fires is |
0 | 928 when there's an infinite loop. */ |
929 } | |
111 | 930 while (!stack.is_empty ()); |
0 | 931 |
932 /* EXIT_BLOCK is always included. */ | |
111 | 933 post_order->quick_push (EXIT_BLOCK); |
0 | 934 } |
935 | |
111 | 936 /* Compute the depth first search order of FN and store in the array |
937 PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the | |
938 reverse completion number for each node. Returns the number of nodes | |
939 visited. A depth first search tries to get as far away from the starting | |
940 point as quickly as possible. | |
0 | 941 |
111 | 942 In case the function has unreachable blocks the number of nodes |
943 visited does not include them. | |
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. */ | |
0 | 947 |
948 int | |
111 | 949 pre_and_rev_post_order_compute_fn (struct function *fn, |
950 int *pre_order, int *rev_post_order, | |
951 bool include_entry_exit) | |
0 | 952 { |
953 int pre_order_num = 0; | |
145 | 954 int rev_post_order_num = n_basic_blocks_for_fn (fn) - 1; |
0 | 955 |
956 /* Allocate stack for back-tracking up CFG. */ | |
145 | 957 auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (fn) + 1); |
0 | 958 |
959 if (include_entry_exit) | |
960 { | |
961 if (pre_order) | |
962 pre_order[pre_order_num] = ENTRY_BLOCK; | |
963 pre_order_num++; | |
964 if (rev_post_order) | |
111 | 965 rev_post_order[rev_post_order_num--] = EXIT_BLOCK; |
0 | 966 } |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
967 else |
0 | 968 rev_post_order_num -= NUM_FIXED_BLOCKS; |
969 | |
145 | 970 /* BB flag to track nodes that have been visited. */ |
971 auto_bb_flag visited (fn); | |
0 | 972 |
973 /* Push the first edge on to the stack. */ | |
111 | 974 stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs)); |
0 | 975 |
111 | 976 while (!stack.is_empty ()) |
0 | 977 { |
978 basic_block src; | |
979 basic_block dest; | |
980 | |
981 /* Look at the edge on the top of the stack. */ | |
111 | 982 edge_iterator ei = stack.last (); |
0 | 983 src = ei_edge (ei)->src; |
984 dest = ei_edge (ei)->dest; | |
985 | |
986 /* Check if the edge destination has been visited yet. */ | |
111 | 987 if (dest != EXIT_BLOCK_PTR_FOR_FN (fn) |
145 | 988 && ! (dest->flags & visited)) |
0 | 989 { |
990 /* Mark that we have visited the destination. */ | |
145 | 991 dest->flags |= visited; |
0 | 992 |
993 if (pre_order) | |
994 pre_order[pre_order_num] = dest->index; | |
995 | |
996 pre_order_num++; | |
997 | |
998 if (EDGE_COUNT (dest->succs) > 0) | |
999 /* Since the DEST node has been visited for the first | |
1000 time, check its successors. */ | |
111 | 1001 stack.quick_push (ei_start (dest->succs)); |
0 | 1002 else if (rev_post_order) |
1003 /* There are no successors for the DEST node so assign | |
1004 its reverse completion number. */ | |
1005 rev_post_order[rev_post_order_num--] = dest->index; | |
1006 } | |
1007 else | |
1008 { | |
111 | 1009 if (ei_one_before_end_p (ei) |
1010 && src != ENTRY_BLOCK_PTR_FOR_FN (fn) | |
0 | 1011 && rev_post_order) |
1012 /* There are no more successors for the SRC node | |
1013 so assign its reverse completion number. */ | |
1014 rev_post_order[rev_post_order_num--] = src->index; | |
1015 | |
1016 if (!ei_one_before_end_p (ei)) | |
111 | 1017 ei_next (&stack.last ()); |
0 | 1018 else |
111 | 1019 stack.pop (); |
0 | 1020 } |
1021 } | |
1022 | |
1023 if (include_entry_exit) | |
1024 { | |
1025 if (pre_order) | |
1026 pre_order[pre_order_num] = EXIT_BLOCK; | |
1027 pre_order_num++; | |
1028 if (rev_post_order) | |
111 | 1029 rev_post_order[rev_post_order_num--] = ENTRY_BLOCK; |
0 | 1030 } |
111 | 1031 |
145 | 1032 /* Clear the temporarily allocated flag. */ |
1033 if (!rev_post_order) | |
1034 rev_post_order = pre_order; | |
1035 for (int i = 0; i < pre_order_num; ++i) | |
1036 BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags &= ~visited; | |
1037 | |
111 | 1038 return pre_order_num; |
1039 } | |
1040 | |
1041 /* Like pre_and_rev_post_order_compute_fn but operating on the | |
1042 current function and asserting that all nodes were visited. */ | |
1043 | |
1044 int | |
1045 pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, | |
1046 bool include_entry_exit) | |
1047 { | |
1048 int pre_order_num | |
1049 = pre_and_rev_post_order_compute_fn (cfun, pre_order, rev_post_order, | |
1050 include_entry_exit); | |
1051 if (include_entry_exit) | |
1052 /* The number of nodes visited should be the number of blocks. */ | |
1053 gcc_assert (pre_order_num == n_basic_blocks_for_fn (cfun)); | |
0 | 1054 else |
1055 /* The number of nodes visited should be the number of blocks minus | |
1056 the entry and exit blocks which are not visited here. */ | |
111 | 1057 gcc_assert (pre_order_num |
1058 == (n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)); | |
0 | 1059 |
1060 return pre_order_num; | |
1061 } | |
1062 | |
131 | 1063 /* Unlike pre_and_rev_post_order_compute we fill rev_post_order backwards |
1064 so iterating in RPO order needs to start with rev_post_order[n - 1] | |
1065 going to rev_post_order[0]. If FOR_ITERATION is true then try to | |
1066 make CFG cycles fit into small contiguous regions of the RPO order. | |
1067 When FOR_ITERATION is true this requires up-to-date loop structures. */ | |
1068 | |
1069 int | |
1070 rev_post_order_and_mark_dfs_back_seme (struct function *fn, edge entry, | |
1071 bitmap exit_bbs, bool for_iteration, | |
1072 int *rev_post_order) | |
1073 { | |
1074 int pre_order_num = 0; | |
1075 int rev_post_order_num = 0; | |
1076 | |
1077 /* Allocate stack for back-tracking up CFG. Worst case we need | |
1078 O(n^2) edges but the following should suffice in practice without | |
1079 a need to re-allocate. */ | |
1080 auto_vec<edge, 20> stack (2 * n_basic_blocks_for_fn (fn)); | |
1081 | |
1082 int *pre = XNEWVEC (int, 2 * last_basic_block_for_fn (fn)); | |
1083 int *post = pre + last_basic_block_for_fn (fn); | |
1084 | |
1085 /* BB flag to track nodes that have been visited. */ | |
1086 auto_bb_flag visited (fn); | |
1087 /* BB flag to track which nodes have post[] assigned to avoid | |
1088 zeroing post. */ | |
1089 auto_bb_flag post_assigned (fn); | |
1090 | |
1091 /* Push the first edge on to the stack. */ | |
1092 stack.quick_push (entry); | |
1093 | |
1094 while (!stack.is_empty ()) | |
1095 { | |
1096 basic_block src; | |
1097 basic_block dest; | |
1098 | |
1099 /* Look at the edge on the top of the stack. */ | |
1100 int idx = stack.length () - 1; | |
1101 edge e = stack[idx]; | |
1102 src = e->src; | |
1103 dest = e->dest; | |
1104 e->flags &= ~EDGE_DFS_BACK; | |
1105 | |
1106 /* Check if the edge destination has been visited yet. */ | |
1107 if (! bitmap_bit_p (exit_bbs, dest->index) | |
1108 && ! (dest->flags & visited)) | |
1109 { | |
1110 /* Mark that we have visited the destination. */ | |
1111 dest->flags |= visited; | |
1112 | |
1113 pre[dest->index] = pre_order_num++; | |
1114 | |
1115 if (EDGE_COUNT (dest->succs) > 0) | |
1116 { | |
1117 /* Since the DEST node has been visited for the first | |
1118 time, check its successors. */ | |
1119 /* Push the edge vector in reverse to match previous behavior. */ | |
1120 stack.reserve (EDGE_COUNT (dest->succs)); | |
1121 for (int i = EDGE_COUNT (dest->succs) - 1; i >= 0; --i) | |
1122 stack.quick_push (EDGE_SUCC (dest, i)); | |
1123 /* Generalize to handle more successors? */ | |
1124 if (for_iteration | |
1125 && EDGE_COUNT (dest->succs) == 2) | |
1126 { | |
1127 edge &e1 = stack[stack.length () - 2]; | |
1128 if (loop_exit_edge_p (e1->src->loop_father, e1)) | |
1129 std::swap (e1, stack.last ()); | |
1130 } | |
1131 } | |
1132 else | |
1133 { | |
1134 /* There are no successors for the DEST node so assign | |
1135 its reverse completion number. */ | |
1136 post[dest->index] = rev_post_order_num; | |
1137 dest->flags |= post_assigned; | |
1138 rev_post_order[rev_post_order_num] = dest->index; | |
1139 rev_post_order_num++; | |
1140 } | |
1141 } | |
1142 else | |
1143 { | |
1144 if (dest->flags & visited | |
1145 && src != entry->src | |
1146 && pre[src->index] >= pre[dest->index] | |
1147 && !(dest->flags & post_assigned)) | |
1148 e->flags |= EDGE_DFS_BACK; | |
1149 | |
1150 if (idx != 0 && stack[idx - 1]->src != src) | |
1151 { | |
1152 /* There are no more successors for the SRC node | |
1153 so assign its reverse completion number. */ | |
1154 post[src->index] = rev_post_order_num; | |
1155 src->flags |= post_assigned; | |
1156 rev_post_order[rev_post_order_num] = src->index; | |
1157 rev_post_order_num++; | |
1158 } | |
1159 | |
1160 stack.pop (); | |
1161 } | |
1162 } | |
1163 | |
1164 XDELETEVEC (pre); | |
1165 | |
1166 /* Clear the temporarily allocated flags. */ | |
1167 for (int i = 0; i < rev_post_order_num; ++i) | |
1168 BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags | |
1169 &= ~(post_assigned|visited); | |
1170 | |
1171 return rev_post_order_num; | |
1172 } | |
1173 | |
1174 | |
1175 | |
0 | 1176 /* Compute the depth first search order on the _reverse_ graph and |
131 | 1177 store it in the array DFS_ORDER, marking the nodes visited in VISITED. |
0 | 1178 Returns the number of nodes visited. |
1179 | |
1180 The computation is split into three pieces: | |
1181 | |
1182 flow_dfs_compute_reverse_init () creates the necessary data | |
1183 structures. | |
1184 | |
1185 flow_dfs_compute_reverse_add_bb () adds a basic block to the data | |
1186 structures. The block will start the search. | |
1187 | |
1188 flow_dfs_compute_reverse_execute () continues (or starts) the | |
1189 search using the block on the top of the stack, stopping when the | |
1190 stack is empty. | |
1191 | |
1192 flow_dfs_compute_reverse_finish () destroys the necessary data | |
1193 structures. | |
1194 | |
1195 Thus, the user will probably call ..._init(), call ..._add_bb() to | |
1196 add a beginning basic block to the stack, call ..._execute(), | |
1197 possibly add another bb to the stack and again call ..._execute(), | |
1198 ..., and finally call _finish(). */ | |
1199 | |
1200 /* Initialize the data structures used for depth-first search on the | |
1201 reverse graph. If INITIALIZE_STACK is nonzero, the exit block is | |
1202 added to the basic block stack. DATA is the current depth-first | |
1203 search context. If INITIALIZE_STACK is nonzero, there is an | |
1204 element on the stack. */ | |
1205 | |
111 | 1206 depth_first_search::depth_first_search () : |
1207 m_stack (n_basic_blocks_for_fn (cfun)), | |
1208 m_visited_blocks (last_basic_block_for_fn (cfun)) | |
0 | 1209 { |
111 | 1210 bitmap_clear (m_visited_blocks); |
0 | 1211 } |
1212 | |
1213 /* Add the specified basic block to the top of the dfs data | |
1214 structures. When the search continues, it will start at the | |
1215 block. */ | |
1216 | |
111 | 1217 void |
1218 depth_first_search::add_bb (basic_block bb) | |
0 | 1219 { |
111 | 1220 m_stack.quick_push (bb); |
1221 bitmap_set_bit (m_visited_blocks, bb->index); | |
0 | 1222 } |
1223 | |
1224 /* Continue the depth-first search through the reverse graph starting with the | |
1225 block at the stack's top and ending when the stack is empty. Visited nodes | |
1226 are marked. Returns an unvisited basic block, or NULL if there is none | |
1227 available. */ | |
1228 | |
111 | 1229 basic_block |
1230 depth_first_search::execute (basic_block last_unvisited) | |
0 | 1231 { |
1232 basic_block bb; | |
1233 edge e; | |
1234 edge_iterator ei; | |
1235 | |
111 | 1236 while (!m_stack.is_empty ()) |
0 | 1237 { |
111 | 1238 bb = m_stack.pop (); |
0 | 1239 |
1240 /* Perform depth-first search on adjacent vertices. */ | |
1241 FOR_EACH_EDGE (e, ei, bb->preds) | |
111 | 1242 if (!bitmap_bit_p (m_visited_blocks, e->src->index)) |
1243 add_bb (e->src); | |
0 | 1244 } |
1245 | |
1246 /* Determine if there are unvisited basic blocks. */ | |
1247 FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb) | |
111 | 1248 if (!bitmap_bit_p (m_visited_blocks, bb->index)) |
0 | 1249 return bb; |
1250 | |
1251 return NULL; | |
1252 } | |
1253 | |
1254 /* Performs dfs search from BB over vertices satisfying PREDICATE; | |
1255 if REVERSE, go against direction of edges. Returns number of blocks | |
1256 found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */ | |
1257 int | |
1258 dfs_enumerate_from (basic_block bb, int reverse, | |
1259 bool (*predicate) (const_basic_block, const void *), | |
1260 basic_block *rslt, int rslt_max, const void *data) | |
1261 { | |
1262 basic_block *st, lbb; | |
1263 int sp = 0, tv = 0; | |
1264 | |
131 | 1265 auto_bb_flag visited (cfun); |
0 | 1266 |
131 | 1267 #define MARK_VISITED(BB) ((BB)->flags |= visited) |
1268 #define UNMARK_VISITED(BB) ((BB)->flags &= ~visited) | |
1269 #define VISITED_P(BB) (((BB)->flags & visited) != 0) | |
0 | 1270 |
111 | 1271 st = XNEWVEC (basic_block, rslt_max); |
0 | 1272 rslt[tv++] = st[sp++] = bb; |
1273 MARK_VISITED (bb); | |
1274 while (sp) | |
1275 { | |
1276 edge e; | |
1277 edge_iterator ei; | |
1278 lbb = st[--sp]; | |
1279 if (reverse) | |
1280 { | |
1281 FOR_EACH_EDGE (e, ei, lbb->preds) | |
1282 if (!VISITED_P (e->src) && predicate (e->src, data)) | |
1283 { | |
1284 gcc_assert (tv != rslt_max); | |
1285 rslt[tv++] = st[sp++] = e->src; | |
1286 MARK_VISITED (e->src); | |
1287 } | |
1288 } | |
1289 else | |
1290 { | |
1291 FOR_EACH_EDGE (e, ei, lbb->succs) | |
1292 if (!VISITED_P (e->dest) && predicate (e->dest, data)) | |
1293 { | |
1294 gcc_assert (tv != rslt_max); | |
1295 rslt[tv++] = st[sp++] = e->dest; | |
1296 MARK_VISITED (e->dest); | |
1297 } | |
1298 } | |
1299 } | |
1300 free (st); | |
1301 for (sp = 0; sp < tv; sp++) | |
1302 UNMARK_VISITED (rslt[sp]); | |
1303 return tv; | |
1304 #undef MARK_VISITED | |
1305 #undef UNMARK_VISITED | |
1306 #undef VISITED_P | |
1307 } | |
1308 | |
1309 | |
1310 /* Compute dominance frontiers, ala Harvey, Ferrante, et al. | |
1311 | |
1312 This algorithm can be found in Timothy Harvey's PhD thesis, at | |
1313 http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative | |
1314 dominance algorithms. | |
1315 | |
1316 First, we identify each join point, j (any node with more than one | |
1317 incoming edge is a join point). | |
1318 | |
1319 We then examine each predecessor, p, of j and walk up the dominator tree | |
1320 starting at p. | |
1321 | |
1322 We stop the walk when we reach j's immediate dominator - j is in the | |
1323 dominance frontier of each of the nodes in the walk, except for j's | |
1324 immediate dominator. Intuitively, all of the rest of j's dominators are | |
1325 shared by j's predecessors as well. | |
1326 Since they dominate j, they will not have j in their dominance frontiers. | |
1327 | |
1328 The number of nodes touched by this algorithm is equal to the size | |
1329 of the dominance frontiers, no more, no less. | |
1330 */ | |
1331 | |
145 | 1332 void |
1333 compute_dominance_frontiers (bitmap_head *frontiers) | |
1334 { | |
1335 timevar_push (TV_DOM_FRONTIERS); | |
0 | 1336 |
1337 edge p; | |
1338 edge_iterator ei; | |
1339 basic_block b; | |
111 | 1340 FOR_EACH_BB_FN (b, cfun) |
0 | 1341 { |
1342 if (EDGE_COUNT (b->preds) >= 2) | |
1343 { | |
145 | 1344 basic_block domsb = get_immediate_dominator (CDI_DOMINATORS, b); |
0 | 1345 FOR_EACH_EDGE (p, ei, b->preds) |
1346 { | |
1347 basic_block runner = p->src; | |
111 | 1348 if (runner == ENTRY_BLOCK_PTR_FOR_FN (cfun)) |
0 | 1349 continue; |
1350 | |
1351 while (runner != domsb) | |
1352 { | |
145 | 1353 if (!bitmap_set_bit (&frontiers[runner->index], b->index)) |
0 | 1354 break; |
145 | 1355 runner = get_immediate_dominator (CDI_DOMINATORS, runner); |
0 | 1356 } |
1357 } | |
1358 } | |
1359 } | |
1360 | |
1361 timevar_pop (TV_DOM_FRONTIERS); | |
1362 } | |
1363 | |
1364 /* Given a set of blocks with variable definitions (DEF_BLOCKS), | |
1365 return a bitmap with all the blocks in the iterated dominance | |
1366 frontier of the blocks in DEF_BLOCKS. DFS contains dominance | |
1367 frontier information as returned by compute_dominance_frontiers. | |
1368 | |
1369 The resulting set of blocks are the potential sites where PHI nodes | |
1370 are needed. The caller is responsible for freeing the memory | |
1371 allocated for the return value. */ | |
1372 | |
1373 bitmap | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1374 compute_idf (bitmap def_blocks, bitmap_head *dfs) |
0 | 1375 { |
1376 bitmap_iterator bi; | |
1377 unsigned bb_index, i; | |
1378 bitmap phi_insertion_points; | |
1379 | |
1380 phi_insertion_points = BITMAP_ALLOC (NULL); | |
1381 | |
145 | 1382 /* Seed the work set with all the blocks in DEF_BLOCKS. */ |
1383 auto_bitmap work_set; | |
1384 bitmap_copy (work_set, def_blocks); | |
1385 bitmap_tree_view (work_set); | |
0 | 1386 |
145 | 1387 /* Pop a block off the workset, add every block that appears in |
0 | 1388 the original block's DF that we have not already processed to |
145 | 1389 the workset. Iterate until the workset is empty. Blocks |
1390 which are added to the workset are potential sites for | |
0 | 1391 PHI nodes. */ |
145 | 1392 while (!bitmap_empty_p (work_set)) |
0 | 1393 { |
145 | 1394 /* The dominance frontier of a block is blocks after it so iterating |
1395 on earlier blocks first is better. | |
1396 ??? Basic blocks are by no means guaranteed to be ordered in | |
1397 optimal order for this iteration. */ | |
1398 bb_index = bitmap_first_set_bit (work_set); | |
1399 bitmap_clear_bit (work_set, bb_index); | |
0 | 1400 |
1401 /* Since the registration of NEW -> OLD name mappings is done | |
1402 separately from the call to update_ssa, when updating the SSA | |
1403 form, the basic blocks where new and/or old names are defined | |
1404 may have disappeared by CFG cleanup calls. In this case, | |
1405 we may pull a non-existing block from the work stack. */ | |
111 | 1406 gcc_checking_assert (bb_index |
1407 < (unsigned) last_basic_block_for_fn (cfun)); | |
0 | 1408 |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1409 EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points, |
0 | 1410 0, i, bi) |
1411 { | |
145 | 1412 bitmap_set_bit (work_set, i); |
0 | 1413 bitmap_set_bit (phi_insertion_points, i); |
1414 } | |
1415 } | |
1416 | |
1417 return phi_insertion_points; | |
1418 } | |
1419 | |
111 | 1420 /* Intersection and union of preds/succs for sbitmap based data flow |
1421 solvers. All four functions defined below take the same arguments: | |
1422 B is the basic block to perform the operation for. DST is the | |
1423 target sbitmap, i.e. the result. SRC is an sbitmap vector of size | |
1424 last_basic_block so that it can be indexed with basic block indices. | |
1425 DST may be (but does not have to be) SRC[B->index]. */ | |
0 | 1426 |
111 | 1427 /* Set the bitmap DST to the intersection of SRC of successors of |
1428 basic block B. */ | |
1429 | |
1430 void | |
1431 bitmap_intersection_of_succs (sbitmap dst, sbitmap *src, basic_block b) | |
1432 { | |
1433 unsigned int set_size = dst->size; | |
1434 edge e; | |
1435 unsigned ix; | |
1436 | |
1437 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++) | |
1438 { | |
1439 e = EDGE_SUCC (b, ix); | |
1440 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
1441 continue; | |
1442 | |
1443 bitmap_copy (dst, src[e->dest->index]); | |
1444 break; | |
1445 } | |
1446 | |
1447 if (e == 0) | |
1448 bitmap_ones (dst); | |
1449 else | |
1450 for (++ix; ix < EDGE_COUNT (b->succs); ix++) | |
1451 { | |
1452 unsigned int i; | |
1453 SBITMAP_ELT_TYPE *p, *r; | |
1454 | |
1455 e = EDGE_SUCC (b, ix); | |
1456 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
1457 continue; | |
1458 | |
1459 p = src[e->dest->index]->elms; | |
1460 r = dst->elms; | |
1461 for (i = 0; i < set_size; i++) | |
1462 *r++ &= *p++; | |
1463 } | |
1464 } | |
1465 | |
1466 /* Set the bitmap DST to the intersection of SRC of predecessors of | |
1467 basic block B. */ | |
1468 | |
1469 void | |
1470 bitmap_intersection_of_preds (sbitmap dst, sbitmap *src, basic_block b) | |
1471 { | |
1472 unsigned int set_size = dst->size; | |
1473 edge e; | |
1474 unsigned ix; | |
1475 | |
1476 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++) | |
1477 { | |
1478 e = EDGE_PRED (b, ix); | |
1479 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) | |
1480 continue; | |
1481 | |
1482 bitmap_copy (dst, src[e->src->index]); | |
1483 break; | |
1484 } | |
1485 | |
1486 if (e == 0) | |
1487 bitmap_ones (dst); | |
1488 else | |
1489 for (++ix; ix < EDGE_COUNT (b->preds); ix++) | |
1490 { | |
1491 unsigned int i; | |
1492 SBITMAP_ELT_TYPE *p, *r; | |
1493 | |
1494 e = EDGE_PRED (b, ix); | |
1495 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) | |
1496 continue; | |
1497 | |
1498 p = src[e->src->index]->elms; | |
1499 r = dst->elms; | |
1500 for (i = 0; i < set_size; i++) | |
1501 *r++ &= *p++; | |
1502 } | |
1503 } | |
1504 | |
1505 /* Set the bitmap DST to the union of SRC of successors of | |
1506 basic block B. */ | |
1507 | |
1508 void | |
1509 bitmap_union_of_succs (sbitmap dst, sbitmap *src, basic_block b) | |
1510 { | |
1511 unsigned int set_size = dst->size; | |
1512 edge e; | |
1513 unsigned ix; | |
1514 | |
1515 for (ix = 0; ix < EDGE_COUNT (b->succs); ix++) | |
1516 { | |
1517 e = EDGE_SUCC (b, ix); | |
1518 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
1519 continue; | |
1520 | |
1521 bitmap_copy (dst, src[e->dest->index]); | |
1522 break; | |
1523 } | |
1524 | |
1525 if (ix == EDGE_COUNT (b->succs)) | |
1526 bitmap_clear (dst); | |
1527 else | |
1528 for (ix++; ix < EDGE_COUNT (b->succs); ix++) | |
1529 { | |
1530 unsigned int i; | |
1531 SBITMAP_ELT_TYPE *p, *r; | |
1532 | |
1533 e = EDGE_SUCC (b, ix); | |
1534 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)) | |
1535 continue; | |
1536 | |
1537 p = src[e->dest->index]->elms; | |
1538 r = dst->elms; | |
1539 for (i = 0; i < set_size; i++) | |
1540 *r++ |= *p++; | |
1541 } | |
1542 } | |
1543 | |
1544 /* Set the bitmap DST to the union of SRC of predecessors of | |
1545 basic block B. */ | |
1546 | |
1547 void | |
1548 bitmap_union_of_preds (sbitmap dst, sbitmap *src, basic_block b) | |
1549 { | |
1550 unsigned int set_size = dst->size; | |
1551 edge e; | |
1552 unsigned ix; | |
1553 | |
1554 for (ix = 0; ix < EDGE_COUNT (b->preds); ix++) | |
1555 { | |
1556 e = EDGE_PRED (b, ix); | |
1557 if (e->src== ENTRY_BLOCK_PTR_FOR_FN (cfun)) | |
1558 continue; | |
1559 | |
1560 bitmap_copy (dst, src[e->src->index]); | |
1561 break; | |
1562 } | |
1563 | |
1564 if (ix == EDGE_COUNT (b->preds)) | |
1565 bitmap_clear (dst); | |
1566 else | |
1567 for (ix++; ix < EDGE_COUNT (b->preds); ix++) | |
1568 { | |
1569 unsigned int i; | |
1570 SBITMAP_ELT_TYPE *p, *r; | |
1571 | |
1572 e = EDGE_PRED (b, ix); | |
1573 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) | |
1574 continue; | |
1575 | |
1576 p = src[e->src->index]->elms; | |
1577 r = dst->elms; | |
1578 for (i = 0; i < set_size; i++) | |
1579 *r++ |= *p++; | |
1580 } | |
1581 } | |
1582 | |
1583 /* Returns the list of basic blocks in the function in an order that guarantees | |
1584 that if a block X has just a single predecessor Y, then Y is after X in the | |
1585 ordering. */ | |
1586 | |
1587 basic_block * | |
1588 single_pred_before_succ_order (void) | |
1589 { | |
1590 basic_block x, y; | |
1591 basic_block *order = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun)); | |
1592 unsigned n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; | |
1593 unsigned np, i; | |
1594 auto_sbitmap visited (last_basic_block_for_fn (cfun)); | |
1595 | |
1596 #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index)) | |
1597 #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index)) | |
1598 | |
1599 bitmap_clear (visited); | |
1600 | |
1601 MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun)); | |
1602 FOR_EACH_BB_FN (x, cfun) | |
1603 { | |
1604 if (VISITED_P (x)) | |
1605 continue; | |
1606 | |
1607 /* Walk the predecessors of x as long as they have precisely one | |
1608 predecessor and add them to the list, so that they get stored | |
1609 after x. */ | |
1610 for (y = x, np = 1; | |
1611 single_pred_p (y) && !VISITED_P (single_pred (y)); | |
1612 y = single_pred (y)) | |
1613 np++; | |
1614 for (y = x, i = n - np; | |
1615 single_pred_p (y) && !VISITED_P (single_pred (y)); | |
1616 y = single_pred (y), i++) | |
1617 { | |
1618 order[i] = y; | |
1619 MARK_VISITED (y); | |
1620 } | |
1621 order[i] = y; | |
1622 MARK_VISITED (y); | |
1623 | |
1624 gcc_assert (i == n - 1); | |
1625 n -= np; | |
1626 } | |
1627 | |
1628 gcc_assert (n == 0); | |
1629 return order; | |
1630 | |
1631 #undef MARK_VISITED | |
1632 #undef VISITED_P | |
1633 } | |
131 | 1634 |
1635 /* Ignoring loop backedges, if BB has precisely one incoming edge then | |
1636 return that edge. Otherwise return NULL. | |
1637 | |
1638 When IGNORE_NOT_EXECUTABLE is true, also ignore edges that are not marked | |
1639 as executable. */ | |
1640 | |
1641 edge | |
1642 single_pred_edge_ignoring_loop_edges (basic_block bb, | |
1643 bool ignore_not_executable) | |
1644 { | |
1645 edge retval = NULL; | |
1646 edge e; | |
1647 edge_iterator ei; | |
1648 | |
1649 FOR_EACH_EDGE (e, ei, bb->preds) | |
1650 { | |
1651 /* A loop back edge can be identified by the destination of | |
1652 the edge dominating the source of the edge. */ | |
1653 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest)) | |
1654 continue; | |
1655 | |
1656 /* We can safely ignore edges that are not executable. */ | |
1657 if (ignore_not_executable | |
1658 && (e->flags & EDGE_EXECUTABLE) == 0) | |
1659 continue; | |
1660 | |
1661 /* If we have already seen a non-loop edge, then we must have | |
1662 multiple incoming non-loop edges and thus we return NULL. */ | |
1663 if (retval) | |
1664 return NULL; | |
1665 | |
1666 /* This is the first non-loop incoming edge we have found. Record | |
1667 it. */ | |
1668 retval = e; | |
1669 } | |
1670 | |
1671 return retval; | |
1672 } |