Branch data Line data Source code
1 : : /* Control flow graph analysis code for GNU compiler.
2 : : Copyright (C) 1987-2024 Free Software Foundation, Inc.
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. */
21 : :
22 : : #include "config.h"
23 : : #include "system.h"
24 : : #include "coretypes.h"
25 : : #include "backend.h"
26 : : #include "cfghooks.h"
27 : : #include "timevar.h"
28 : : #include "cfganal.h"
29 : : #include "cfgloop.h"
30 : : #include "diagnostic.h"
31 : :
32 : : namespace {
33 : : /* Store the data structures necessary for depth-first search. */
34 : : class depth_first_search
35 : : {
36 : : public:
37 : : depth_first_search ();
38 : :
39 : : basic_block execute (basic_block);
40 : : void add_bb (basic_block);
41 : :
42 : : private:
43 : : /* stack for backtracking during the algorithm */
44 : : auto_vec<basic_block, 20> m_stack;
45 : :
46 : : /* record of basic blocks already seen by depth-first search */
47 : : auto_sbitmap m_visited_blocks;
48 : : };
49 : : }
50 : :
51 : : /* Mark the back edges in DFS traversal.
52 : : Return nonzero if a loop (natural or otherwise) is present.
53 : : Inspired by Depth_First_Search_PP described in:
54 : :
55 : : Advanced Compiler Design and Implementation
56 : : Steven Muchnick
57 : : Morgan Kaufmann, 1997
58 : :
59 : : and heavily borrowed from pre_and_rev_post_order_compute. */
60 : :
61 : : bool
62 : 31732349 : mark_dfs_back_edges (struct function *fun)
63 : : {
64 : 31732349 : int *pre;
65 : 31732349 : int *post;
66 : 31732349 : int prenum = 1;
67 : 31732349 : int postnum = 1;
68 : 31732349 : bool found = false;
69 : :
70 : : /* Allocate the preorder and postorder number arrays. */
71 : 31732349 : pre = XCNEWVEC (int, last_basic_block_for_fn (fun));
72 : 31732349 : post = XCNEWVEC (int, last_basic_block_for_fn (fun));
73 : :
74 : : /* Allocate stack for back-tracking up CFG. */
75 : 31732349 : auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (fun) + 1);
76 : :
77 : : /* Allocate bitmap to track nodes that have been visited. */
78 : 31732349 : auto_sbitmap visited (last_basic_block_for_fn (fun));
79 : :
80 : : /* None of the nodes in the CFG have been visited yet. */
81 : 31732349 : bitmap_clear (visited);
82 : :
83 : : /* Push the first edge on to the stack. */
84 : 31732349 : stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (fun)->succs));
85 : :
86 : 845316255 : while (!stack.is_empty ())
87 : : {
88 : 813583906 : basic_block src;
89 : 813583906 : basic_block dest;
90 : :
91 : : /* Look at the edge on the top of the stack. */
92 : 813583906 : edge_iterator ei = stack.last ();
93 : 813583906 : src = ei_edge (ei)->src;
94 : 813583906 : dest = ei_edge (ei)->dest;
95 : 813583906 : ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
96 : :
97 : : /* Check if the edge destination has been visited yet. */
98 : 780123932 : if (dest != EXIT_BLOCK_PTR_FOR_FN (fun) && ! bitmap_bit_p (visited,
99 : : dest->index))
100 : : {
101 : : /* Mark that we have visited the destination. */
102 : 326911199 : bitmap_set_bit (visited, dest->index);
103 : :
104 : 326911199 : pre[dest->index] = prenum++;
105 : 326911199 : if (EDGE_COUNT (dest->succs) > 0)
106 : : {
107 : : /* Since the DEST node has been visited for the first
108 : : time, check its successors. */
109 : 310340405 : stack.quick_push (ei_start (dest->succs));
110 : : }
111 : : else
112 : 16570794 : post[dest->index] = postnum++;
113 : : }
114 : : else
115 : : {
116 : 486672707 : if (dest != EXIT_BLOCK_PTR_FOR_FN (fun)
117 : 453212733 : && src != ENTRY_BLOCK_PTR_FOR_FN (fun)
118 : 421480384 : && pre[src->index] >= pre[dest->index]
119 : 104326189 : && post[dest->index] == 0)
120 : 17235018 : ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
121 : :
122 : 486672707 : if (ei_one_before_end_p (ei)
123 : 486672707 : && src != ENTRY_BLOCK_PTR_FOR_FN (fun))
124 : 310340405 : post[src->index] = postnum++;
125 : :
126 : 486672707 : if (!ei_one_before_end_p (ei))
127 : 144599953 : ei_next (&stack.last ());
128 : : else
129 : 342072754 : stack.pop ();
130 : : }
131 : : }
132 : :
133 : 31732349 : free (pre);
134 : 31732349 : free (post);
135 : :
136 : 31732349 : return found;
137 : 31732349 : }
138 : :
139 : : bool
140 : 24549796 : mark_dfs_back_edges (void)
141 : : {
142 : 24549796 : return mark_dfs_back_edges (cfun);
143 : : }
144 : :
145 : : /* Return TRUE if EDGE_DFS_BACK is up to date for CFUN. */
146 : :
147 : : void
148 : 0 : verify_marked_backedges (struct function *fun)
149 : : {
150 : 0 : auto_edge_flag saved_dfs_back (fun);
151 : 0 : basic_block bb;
152 : 0 : edge e;
153 : 0 : edge_iterator ei;
154 : :
155 : : // Save all the back edges...
156 : 0 : FOR_EACH_BB_FN (bb, fun)
157 : 0 : FOR_EACH_EDGE (e, ei, bb->succs)
158 : : {
159 : 0 : if (e->flags & EDGE_DFS_BACK)
160 : : {
161 : 0 : e->flags |= saved_dfs_back;
162 : 0 : e->flags &= ~EDGE_DFS_BACK;
163 : : }
164 : : }
165 : :
166 : : // ...and verify that recalculating them agrees with the saved ones.
167 : 0 : mark_dfs_back_edges ();
168 : 0 : FOR_EACH_BB_FN (bb, fun)
169 : 0 : FOR_EACH_EDGE (e, ei, bb->succs)
170 : : {
171 : 0 : if (((e->flags & EDGE_DFS_BACK) != 0)
172 : 0 : != ((e->flags & saved_dfs_back) != 0))
173 : 0 : internal_error ("%<verify_marked_backedges%> failed");
174 : :
175 : 0 : e->flags &= ~saved_dfs_back;
176 : : }
177 : 0 : }
178 : :
179 : : /* Find unreachable blocks. An unreachable block will have 0 in
180 : : the reachable bit in block->flags. A nonzero value indicates the
181 : : block is reachable. */
182 : :
183 : : void
184 : 67271237 : find_unreachable_blocks (void)
185 : : {
186 : 67271237 : edge e;
187 : 67271237 : edge_iterator ei;
188 : 67271237 : basic_block *tos, *worklist, bb;
189 : :
190 : 67271237 : tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
191 : :
192 : : /* Clear all the reachability flags. */
193 : :
194 : 911576422 : FOR_EACH_BB_FN (bb, cfun)
195 : 844305185 : bb->flags &= ~BB_REACHABLE;
196 : :
197 : : /* Add our starting points to the worklist. Almost always there will
198 : : be only one. It isn't inconceivable that we might one day directly
199 : : support Fortran alternate entry points. */
200 : :
201 : 134542474 : FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
202 : : {
203 : 67271237 : *tos++ = e->dest;
204 : :
205 : : /* Mark the block reachable. */
206 : 67271237 : e->dest->flags |= BB_REACHABLE;
207 : : }
208 : :
209 : : /* Iterate: find everything reachable from what we've already seen. */
210 : :
211 : 916516702 : while (tos != worklist)
212 : : {
213 : 849245465 : basic_block b = *--tos;
214 : :
215 : 2071658777 : FOR_EACH_EDGE (e, ei, b->succs)
216 : : {
217 : 1222413312 : basic_block dest = e->dest;
218 : :
219 : 1222413312 : if (!(dest->flags & BB_REACHABLE))
220 : : {
221 : 781974228 : *tos++ = dest;
222 : 781974228 : dest->flags |= BB_REACHABLE;
223 : : }
224 : : }
225 : : }
226 : :
227 : 67271237 : free (worklist);
228 : 67271237 : }
229 : :
230 : : /* Verify that there are no unreachable blocks in the current function. */
231 : :
232 : : void
233 : 39165031 : verify_no_unreachable_blocks (void)
234 : : {
235 : 39165031 : find_unreachable_blocks ();
236 : :
237 : 39165031 : basic_block bb;
238 : 509905618 : FOR_EACH_BB_FN (bb, cfun)
239 : 470740587 : gcc_assert ((bb->flags & BB_REACHABLE) != 0);
240 : 39165031 : }
241 : :
242 : :
243 : : /* Functions to access an edge list with a vector representation.
244 : : Enough data is kept such that given an index number, the
245 : : pred and succ that edge represents can be determined, or
246 : : given a pred and a succ, its index number can be returned.
247 : : This allows algorithms which consume a lot of memory to
248 : : represent the normally full matrix of edge (pred,succ) with a
249 : : single indexed vector, edge (EDGE_INDEX (pred, succ)), with no
250 : : wasted space in the client code due to sparse flow graphs. */
251 : :
252 : : /* This functions initializes the edge list. Basically the entire
253 : : flowgraph is processed, and all edges are assigned a number,
254 : : and the data structure is filled in. */
255 : :
256 : : struct edge_list *
257 : 462556 : create_edge_list (void)
258 : : {
259 : 462556 : struct edge_list *elist;
260 : 462556 : edge e;
261 : 462556 : int num_edges;
262 : 462556 : basic_block bb;
263 : 462556 : edge_iterator ei;
264 : :
265 : : /* Determine the number of edges in the flow graph by counting successor
266 : : edges on each basic block. */
267 : 462556 : num_edges = 0;
268 : 9630165 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
269 : : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
270 : : {
271 : 18334605 : num_edges += EDGE_COUNT (bb->succs);
272 : : }
273 : :
274 : 462556 : elist = XNEW (struct edge_list);
275 : 462556 : elist->num_edges = num_edges;
276 : 462556 : elist->index_to_edge = XNEWVEC (edge, num_edges);
277 : :
278 : 462556 : num_edges = 0;
279 : :
280 : : /* Follow successors of blocks, and register these edges. */
281 : 9630165 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
282 : : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
283 : 22894576 : FOR_EACH_EDGE (e, ei, bb->succs)
284 : 13726967 : elist->index_to_edge[num_edges++] = e;
285 : :
286 : 462556 : return elist;
287 : : }
288 : :
289 : : /* This function free's memory associated with an edge list. */
290 : :
291 : : void
292 : 462556 : free_edge_list (struct edge_list *elist)
293 : : {
294 : 462556 : if (elist)
295 : : {
296 : 462556 : free (elist->index_to_edge);
297 : 462556 : free (elist);
298 : : }
299 : 462556 : }
300 : :
301 : : /* This function provides debug output showing an edge list. */
302 : :
303 : : DEBUG_FUNCTION void
304 : 0 : print_edge_list (FILE *f, struct edge_list *elist)
305 : : {
306 : 0 : int x;
307 : :
308 : 0 : fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
309 : 0 : n_basic_blocks_for_fn (cfun), elist->num_edges);
310 : :
311 : 0 : for (x = 0; x < elist->num_edges; x++)
312 : : {
313 : 0 : fprintf (f, " %-4d - edge(", x);
314 : 0 : if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
315 : 0 : fprintf (f, "entry,");
316 : : else
317 : 0 : fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
318 : :
319 : 0 : if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR_FOR_FN (cfun))
320 : 0 : fprintf (f, "exit)\n");
321 : : else
322 : 0 : fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
323 : : }
324 : 0 : }
325 : :
326 : : /* This function provides an internal consistency check of an edge list,
327 : : verifying that all edges are present, and that there are no
328 : : extra edges. */
329 : :
330 : : DEBUG_FUNCTION void
331 : 0 : verify_edge_list (FILE *f, struct edge_list *elist)
332 : : {
333 : 0 : int pred, succ, index;
334 : 0 : edge e;
335 : 0 : basic_block bb, p, s;
336 : 0 : edge_iterator ei;
337 : :
338 : 0 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
339 : : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
340 : : {
341 : 0 : FOR_EACH_EDGE (e, ei, bb->succs)
342 : : {
343 : 0 : pred = e->src->index;
344 : 0 : succ = e->dest->index;
345 : 0 : index = EDGE_INDEX (elist, e->src, e->dest);
346 : 0 : if (index == EDGE_INDEX_NO_EDGE)
347 : : {
348 : 0 : fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
349 : 0 : continue;
350 : : }
351 : :
352 : 0 : if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
353 : 0 : fprintf (f, "*p* Pred for index %d should be %d not %d\n",
354 : : index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
355 : 0 : if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
356 : 0 : fprintf (f, "*p* Succ for index %d should be %d not %d\n",
357 : : index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
358 : : }
359 : : }
360 : :
361 : : /* We've verified that all the edges are in the list, now lets make sure
362 : : there are no spurious edges in the list. This is an expensive check! */
363 : :
364 : 0 : FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR_FOR_FN (cfun),
365 : : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
366 : 0 : FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
367 : : {
368 : 0 : int found_edge = 0;
369 : :
370 : 0 : FOR_EACH_EDGE (e, ei, p->succs)
371 : 0 : if (e->dest == s)
372 : : {
373 : : found_edge = 1;
374 : : break;
375 : : }
376 : :
377 : 0 : FOR_EACH_EDGE (e, ei, s->preds)
378 : 0 : if (e->src == p)
379 : : {
380 : : found_edge = 1;
381 : : break;
382 : : }
383 : :
384 : 0 : if (EDGE_INDEX (elist, p, s)
385 : 0 : == EDGE_INDEX_NO_EDGE && found_edge != 0)
386 : 0 : fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
387 : : p->index, s->index);
388 : 0 : if (EDGE_INDEX (elist, p, s)
389 : 0 : != EDGE_INDEX_NO_EDGE && found_edge == 0)
390 : 0 : fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
391 : : p->index, s->index, EDGE_INDEX (elist, p, s));
392 : : }
393 : 0 : }
394 : :
395 : :
396 : : /* Functions to compute control dependences. */
397 : :
398 : : /* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */
399 : : void
400 : 42633576 : control_dependences::set_control_dependence_map_bit (basic_block bb,
401 : : int edge_index)
402 : : {
403 : 42633576 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
404 : : return;
405 : 42633576 : gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
406 : 42633576 : bitmap_set_bit (&control_dependence_map[bb->index], edge_index);
407 : : }
408 : :
409 : : /* Clear all control dependences for block BB. */
410 : : void
411 : 0 : control_dependences::clear_control_dependence_bitmap (basic_block bb)
412 : : {
413 : 0 : bitmap_clear (&control_dependence_map[bb->index]);
414 : 0 : }
415 : :
416 : : /* Determine all blocks' control dependences on the given edge with edge_list
417 : : EL index EDGE_INDEX, ala Morgan, Section 3.6. */
418 : :
419 : : void
420 : 43722489 : control_dependences::find_control_dependence (int edge_index)
421 : : {
422 : 43722489 : basic_block current_block;
423 : 43722489 : basic_block ending_block;
424 : :
425 : 43722489 : gcc_assert (get_edge_src (edge_index) != EXIT_BLOCK_PTR_FOR_FN (cfun));
426 : :
427 : 43722489 : ending_block = get_immediate_dominator (CDI_POST_DOMINATORS,
428 : : get_edge_src (edge_index));
429 : :
430 : 43722489 : for (current_block = get_edge_dest (edge_index);
431 : : current_block != ending_block
432 : 86356065 : && current_block != EXIT_BLOCK_PTR_FOR_FN (cfun);
433 : 42633576 : current_block = get_immediate_dominator (CDI_POST_DOMINATORS,
434 : : current_block))
435 : 42633576 : set_control_dependence_map_bit (current_block, edge_index);
436 : 43722489 : }
437 : :
438 : : /* Record all blocks' control dependences on all edges in the edge
439 : : list EL, ala Morgan, Section 3.6. */
440 : :
441 : 3301179 : control_dependences::control_dependences ()
442 : : {
443 : 3301179 : timevar_push (TV_CONTROL_DEPENDENCES);
444 : :
445 : : /* Initialize the edge list. */
446 : 3301179 : int num_edges = 0;
447 : 3301179 : basic_block bb;
448 : 35521960 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
449 : : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
450 : 63725126 : num_edges += EDGE_COUNT (bb->succs);
451 : 3301179 : m_el.create (num_edges);
452 : 3301179 : edge e;
453 : 3301179 : edge_iterator ei;
454 : 35521960 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
455 : : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
456 : 75956002 : FOR_EACH_EDGE (e, ei, bb->succs)
457 : : {
458 : : /* For abnormal edges, we don't make current_block control
459 : : dependent because instructions that throw are always necessary
460 : : anyway. */
461 : 43735221 : if (e->flags & EDGE_ABNORMAL)
462 : : {
463 : 12732 : num_edges--;
464 : 12732 : continue;
465 : : }
466 : 43722489 : m_el.quick_push (std::make_pair (e->src->index, e->dest->index));
467 : : }
468 : :
469 : 3301179 : bitmap_obstack_initialize (&m_bitmaps);
470 : 3301179 : control_dependence_map.create (last_basic_block_for_fn (cfun));
471 : 3301179 : control_dependence_map.quick_grow_cleared (last_basic_block_for_fn (cfun));
472 : 39725891 : for (int i = 0; i < last_basic_block_for_fn (cfun); ++i)
473 : 36424712 : bitmap_initialize (&control_dependence_map[i], &m_bitmaps);
474 : 47023668 : for (int i = 0; i < num_edges; ++i)
475 : 43722489 : find_control_dependence (i);
476 : :
477 : 3301179 : timevar_pop (TV_CONTROL_DEPENDENCES);
478 : 3301179 : }
479 : :
480 : : /* Free control dependences and the associated edge list. */
481 : :
482 : 3301179 : control_dependences::~control_dependences ()
483 : : {
484 : 3301179 : control_dependence_map.release ();
485 : 3301179 : m_el.release ();
486 : 3301179 : bitmap_obstack_release (&m_bitmaps);
487 : 3301179 : }
488 : :
489 : : /* Returns the bitmap of edges the basic-block I is dependent on. */
490 : :
491 : : bitmap
492 : 27295485 : control_dependences::get_edges_dependent_on (int i)
493 : : {
494 : 27295485 : return &control_dependence_map[i];
495 : : }
496 : :
497 : : /* Returns the edge source with index I from the edge list. */
498 : :
499 : : basic_block
500 : 128691368 : control_dependences::get_edge_src (int i)
501 : : {
502 : 128691368 : return BASIC_BLOCK_FOR_FN (cfun, m_el[i].first);
503 : : }
504 : :
505 : : /* Returns the edge destination with index I from the edge list. */
506 : :
507 : : basic_block
508 : 43722489 : control_dependences::get_edge_dest (int i)
509 : : {
510 : 43722489 : return BASIC_BLOCK_FOR_FN (cfun, m_el[i].second);
511 : : }
512 : :
513 : :
514 : : /* Given PRED and SUCC blocks, return the edge which connects the blocks.
515 : : If no such edge exists, return NULL. */
516 : :
517 : : edge
518 : 687807589 : find_edge (basic_block pred, basic_block succ)
519 : : {
520 : 687807589 : edge e;
521 : 687807589 : edge_iterator ei;
522 : :
523 : 1900628724 : if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
524 : : {
525 : 719422544 : FOR_EACH_EDGE (e, ei, pred->succs)
526 : 553681155 : if (e->dest == succ)
527 : 351600157 : return e;
528 : : }
529 : : else
530 : : {
531 : 187852293 : FOR_EACH_EDGE (e, ei, succ->preds)
532 : 115033166 : if (e->src == pred)
533 : 97646916 : return e;
534 : : }
535 : :
536 : : return NULL;
537 : : }
538 : :
539 : : /* This routine will determine what, if any, edge there is between
540 : : a specified predecessor and successor. */
541 : :
542 : : int
543 : 26 : find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
544 : : {
545 : 26 : int x;
546 : :
547 : 149 : for (x = 0; x < NUM_EDGES (edge_list); x++)
548 : 149 : if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
549 : 52 : && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
550 : 26 : return x;
551 : :
552 : : return (EDGE_INDEX_NO_EDGE);
553 : : }
554 : :
555 : : /* This routine will remove any fake predecessor edges for a basic block.
556 : : When the edge is removed, it is also removed from whatever successor
557 : : list it is in. */
558 : :
559 : : static void
560 : 6542978 : remove_fake_predecessors (basic_block bb)
561 : : {
562 : 6542978 : edge e;
563 : 6542978 : edge_iterator ei;
564 : :
565 : 16627275 : for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
566 : : {
567 : 10084297 : if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
568 : 3540115 : remove_edge (e);
569 : : else
570 : 6544182 : ei_next (&ei);
571 : : }
572 : 6542978 : }
573 : :
574 : : /* This routine will remove all fake edges from the flow graph. If
575 : : we remove all fake successors, it will automatically remove all
576 : : fake predecessors. */
577 : :
578 : : void
579 : 2276 : remove_fake_edges (void)
580 : : {
581 : 2276 : basic_block bb;
582 : :
583 : 16531 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
584 : 14255 : remove_fake_predecessors (bb);
585 : 2276 : }
586 : :
587 : : /* This routine will remove all fake edges to the EXIT_BLOCK. */
588 : :
589 : : void
590 : 6528723 : remove_fake_exit_edges (void)
591 : : {
592 : 6528723 : remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun));
593 : 6528723 : }
594 : :
595 : :
596 : : /* This function will add a fake edge between any block which has no
597 : : successors, and the exit block. Some data flow equations require these
598 : : edges to exist. */
599 : :
600 : : void
601 : 6530999 : add_noreturn_fake_exit_edges (void)
602 : : {
603 : 6530999 : basic_block bb;
604 : :
605 : 74321049 : FOR_EACH_BB_FN (bb, cfun)
606 : 67790050 : if (EDGE_COUNT (bb->succs) == 0)
607 : 3555952 : make_single_succ_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
608 : 6530999 : }
609 : :
610 : : /* This function adds a fake edge between any noreturn block and
611 : : infinite loops to the exit block. Some optimizations require a path
612 : : from each node to the exit node.
613 : :
614 : : See also Morgan, Figure 3.10, pp. 82-83.
615 : :
616 : : The current implementation is ugly, not attempting to minimize the
617 : : number of inserted fake edges. To reduce the number of fake edges
618 : : to insert, add fake edges from _innermost_ loops containing only
619 : : nodes not reachable from the exit block. */
620 : :
621 : : void
622 : 5160926 : connect_infinite_loops_to_exit (void)
623 : : {
624 : : /* First add fake exits to noreturn blocks, this is required to
625 : : discover only truly infinite loops below. */
626 : 5160926 : add_noreturn_fake_exit_edges ();
627 : :
628 : : /* Perform depth-first search in the reverse graph to find nodes
629 : : reachable from the exit block. */
630 : 5160926 : depth_first_search dfs;
631 : 5160926 : dfs.add_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
632 : :
633 : : /* Repeatedly add fake edges, updating the unreachable nodes. */
634 : 5160926 : basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
635 : 5209264 : while (1)
636 : : {
637 : 5185095 : unvisited_block = dfs.execute (unvisited_block);
638 : 5185095 : if (!unvisited_block)
639 : : break;
640 : :
641 : 24169 : basic_block deadend_block = dfs_find_deadend (unvisited_block);
642 : 24169 : edge e = make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun),
643 : : EDGE_FAKE);
644 : 24169 : e->probability = profile_probability::never ();
645 : 24169 : dfs.add_bb (deadend_block);
646 : 24169 : }
647 : 5160926 : }
648 : :
649 : : /* Compute reverse top sort order. This is computing a post order
650 : : numbering of the graph. If INCLUDE_ENTRY_EXIT is true, then
651 : : ENTRY_BLOCK and EXIT_BLOCK are included. If DELETE_UNREACHABLE is
652 : : true, unreachable blocks are deleted. */
653 : :
654 : : int
655 : 35440849 : post_order_compute (int *post_order, bool include_entry_exit,
656 : : bool delete_unreachable)
657 : : {
658 : 35440849 : int post_order_num = 0;
659 : 35440849 : int count;
660 : :
661 : 35440849 : if (include_entry_exit)
662 : 34334017 : post_order[post_order_num++] = EXIT_BLOCK;
663 : :
664 : : /* Allocate stack for back-tracking up CFG. */
665 : 35440849 : auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
666 : :
667 : : /* Allocate bitmap to track nodes that have been visited. */
668 : 35440849 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
669 : :
670 : : /* None of the nodes in the CFG have been visited yet. */
671 : 35440849 : bitmap_clear (visited);
672 : :
673 : : /* Push the first edge on to the stack. */
674 : 35440849 : stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
675 : :
676 : 1085580587 : while (!stack.is_empty ())
677 : : {
678 : 1050139738 : basic_block src;
679 : 1050139738 : basic_block dest;
680 : :
681 : : /* Look at the edge on the top of the stack. */
682 : 1050139738 : edge_iterator ei = stack.last ();
683 : 1050139738 : src = ei_edge (ei)->src;
684 : 1050139738 : dest = ei_edge (ei)->dest;
685 : :
686 : : /* Check if the edge destination has been visited yet. */
687 : 1050139738 : if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
688 : 1050139738 : && ! bitmap_bit_p (visited, dest->index))
689 : : {
690 : : /* Mark that we have visited the destination. */
691 : 412398161 : bitmap_set_bit (visited, dest->index);
692 : :
693 : 412398161 : if (EDGE_COUNT (dest->succs) > 0)
694 : : /* Since the DEST node has been visited for the first
695 : : time, check its successors. */
696 : 392459303 : stack.quick_push (ei_start (dest->succs));
697 : : else
698 : 19938858 : post_order[post_order_num++] = dest->index;
699 : : }
700 : : else
701 : : {
702 : 637741577 : if (ei_one_before_end_p (ei)
703 : 637741577 : && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
704 : 392459303 : post_order[post_order_num++] = src->index;
705 : :
706 : 637741577 : if (!ei_one_before_end_p (ei))
707 : 209841425 : ei_next (&stack.last ());
708 : : else
709 : 427900152 : stack.pop ();
710 : : }
711 : : }
712 : :
713 : 35440849 : if (include_entry_exit)
714 : : {
715 : 34334017 : post_order[post_order_num++] = ENTRY_BLOCK;
716 : 34334017 : count = post_order_num;
717 : : }
718 : : else
719 : 1106832 : count = post_order_num + 2;
720 : :
721 : : /* Delete the unreachable blocks if some were found and we are
722 : : supposed to do it. */
723 : 35440849 : if (delete_unreachable && (count != n_basic_blocks_for_fn (cfun)))
724 : : {
725 : 11767 : basic_block b;
726 : 11767 : basic_block next_bb;
727 : 11767 : for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
728 : 2051301 : != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb)
729 : : {
730 : 2039534 : next_bb = b->next_bb;
731 : :
732 : 2039534 : if (!(bitmap_bit_p (visited, b->index)))
733 : 23902 : delete_basic_block (b);
734 : : }
735 : :
736 : 11767 : tidy_fallthru_edges ();
737 : : }
738 : :
739 : 35440849 : return post_order_num;
740 : 35440849 : }
741 : :
742 : :
743 : : /* Helper routine for inverted_rev_post_order_compute
744 : : flow_dfs_compute_reverse_execute, and the reverse-CFG
745 : : deapth first search in dominance.cc.
746 : : BB has to belong to a region of CFG
747 : : unreachable by inverted traversal from the exit.
748 : : i.e. there's no control flow path from ENTRY to EXIT
749 : : that contains this BB.
750 : : This can happen in two cases - if there's an infinite loop
751 : : or if there's a block that has no successor
752 : : (call to a function with no return).
753 : : Some RTL passes deal with this condition by
754 : : calling connect_infinite_loops_to_exit () and/or
755 : : add_noreturn_fake_exit_edges ().
756 : : However, those methods involve modifying the CFG itself
757 : : which may not be desirable.
758 : : Hence, we deal with the infinite loop/no return cases
759 : : by identifying a unique basic block that can reach all blocks
760 : : in such a region by inverted traversal.
761 : : This function returns a basic block that guarantees
762 : : that all blocks in the region are reachable
763 : : by starting an inverted traversal from the returned block. */
764 : :
765 : : basic_block
766 : 385303 : dfs_find_deadend (basic_block bb)
767 : : {
768 : 385303 : auto_bitmap visited;
769 : 385303 : basic_block next = bb;
770 : :
771 : 1375531 : for (;;)
772 : : {
773 : 1375531 : if (EDGE_COUNT (next->succs) == 0)
774 : 0 : return next;
775 : :
776 : 1375531 : if (! bitmap_set_bit (visited, next->index))
777 : 385303 : return bb;
778 : :
779 : 990228 : bb = next;
780 : : /* If we are in an analyzed cycle make sure to try exiting it.
781 : : Note this is a heuristic only and expected to work when loop
782 : : fixup is needed as well. */
783 : 990228 : if (! bb->loop_father
784 : 990228 : || ! loop_outer (bb->loop_father))
785 : 640948 : next = EDGE_SUCC (bb, 0)->dest;
786 : : else
787 : : {
788 : 349280 : edge_iterator ei;
789 : 349280 : edge e;
790 : 726177 : FOR_EACH_EDGE (e, ei, bb->succs)
791 : 421579 : if (loop_exit_edge_p (bb->loop_father, e))
792 : : break;
793 : 349280 : next = e ? e->dest : EDGE_SUCC (bb, 0)->dest;
794 : : }
795 : : }
796 : 385303 : }
797 : :
798 : :
799 : : /* Compute the reverse top sort order of the inverted CFG
800 : : i.e. starting from the exit block and following the edges backward
801 : : (from successors to predecessors).
802 : : This ordering can be used for forward dataflow problems among others.
803 : :
804 : : Optionally if START_POINTS is specified, start from exit block and all
805 : : basic blocks in START_POINTS. This is used by CD-DCE.
806 : :
807 : : This function assumes that all blocks in the CFG are reachable
808 : : from the ENTRY (but not necessarily from EXIT).
809 : :
810 : : If there's an infinite loop,
811 : : a simple inverted traversal starting from the blocks
812 : : with no successors can't visit all blocks.
813 : : To solve this problem, we first do inverted traversal
814 : : starting from the blocks with no successor.
815 : : And if there's any block left that's not visited by the regular
816 : : inverted traversal from EXIT,
817 : : those blocks are in such problematic region.
818 : : Among those, we find one block that has
819 : : any visited predecessor (which is an entry into such a region),
820 : : and start looking for a "dead end" from that block
821 : : and do another inverted traversal from that block. */
822 : :
823 : : int
824 : 39165814 : inverted_rev_post_order_compute (struct function *fn,
825 : : int *rev_post_order,
826 : : sbitmap *start_points)
827 : : {
828 : 39165814 : basic_block bb;
829 : :
830 : 39165814 : int rev_post_order_num = n_basic_blocks_for_fn (fn) - 1;
831 : :
832 : 39165814 : if (flag_checking)
833 : 39165031 : verify_no_unreachable_blocks ();
834 : :
835 : : /* Allocate stack for back-tracking up CFG. */
836 : 39165814 : auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
837 : :
838 : : /* Allocate bitmap to track nodes that have been visited. */
839 : 39165814 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
840 : :
841 : : /* None of the nodes in the CFG have been visited yet. */
842 : 39165814 : bitmap_clear (visited);
843 : :
844 : 39165814 : if (start_points)
845 : : {
846 : 633176 : FOR_ALL_BB_FN (bb, cfun)
847 : 616340 : if (bitmap_bit_p (*start_points, bb->index)
848 : 1049268 : && EDGE_COUNT (bb->preds) > 0)
849 : : {
850 : 432928 : stack.quick_push (ei_start (bb->preds));
851 : 432928 : bitmap_set_bit (visited, bb->index);
852 : : }
853 : 16836 : if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds))
854 : : {
855 : 15635 : stack.quick_push (ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds));
856 : 15635 : bitmap_set_bit (visited, EXIT_BLOCK_PTR_FOR_FN (cfun)->index);
857 : : }
858 : : }
859 : : else
860 : : /* Put all blocks that have no successor into the initial work list. */
861 : 587607927 : FOR_ALL_BB_FN (bb, cfun)
862 : 548458949 : if (EDGE_COUNT (bb->succs) == 0)
863 : : {
864 : : /* Push the initial edge on to the stack. */
865 : 606683293 : if (EDGE_COUNT (bb->preds) > 0)
866 : : {
867 : 58224344 : stack.quick_push (ei_start (bb->preds));
868 : 58224344 : bitmap_set_bit (visited, bb->index);
869 : : }
870 : : }
871 : :
872 : 39443265 : do
873 : : {
874 : 39443265 : bool has_unvisited_bb = false;
875 : :
876 : : /* The inverted traversal loop. */
877 : 1253189164 : while (!stack.is_empty ())
878 : : {
879 : 1213745899 : edge_iterator ei;
880 : 1213745899 : basic_block pred;
881 : :
882 : : /* Look at the edge on the top of the stack. */
883 : 1213745899 : ei = stack.last ();
884 : 1213745899 : bb = ei_edge (ei)->dest;
885 : 1213745899 : pred = ei_edge (ei)->src;
886 : :
887 : : /* Check if the predecessor has been visited yet. */
888 : 1213745899 : if (! bitmap_bit_p (visited, pred->index))
889 : : {
890 : : /* Mark that we have visited the destination. */
891 : 489279662 : bitmap_set_bit (visited, pred->index);
892 : :
893 : 489279662 : if (EDGE_COUNT (pred->preds) > 0)
894 : : /* Since the predecessor node has been visited for the first
895 : : time, check its predecessors. */
896 : 450113848 : stack.quick_push (ei_start (pred->preds));
897 : : else
898 : 39165814 : rev_post_order[rev_post_order_num--] = pred->index;
899 : : }
900 : : else
901 : : {
902 : 724466237 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
903 : 724466237 : && ei_one_before_end_p (ei))
904 : 470743661 : rev_post_order[rev_post_order_num--] = bb->index;
905 : :
906 : 724466237 : if (!ei_one_before_end_p (ei))
907 : 215402031 : ei_next (&stack.last ());
908 : : else
909 : 509064206 : stack.pop ();
910 : : }
911 : : }
912 : :
913 : : /* Detect any infinite loop and activate the kludge.
914 : : Note that this doesn't check EXIT_BLOCK itself
915 : : since EXIT_BLOCK is always added after the outer do-while loop. */
916 : 553159982 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
917 : : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
918 : 513918898 : if (!bitmap_bit_p (visited, bb->index))
919 : : {
920 : 762727 : has_unvisited_bb = true;
921 : :
922 : 514479444 : if (EDGE_COUNT (bb->preds) > 0)
923 : : {
924 : 687457 : edge_iterator ei;
925 : 687457 : edge e;
926 : 687457 : basic_block visited_pred = NULL;
927 : :
928 : : /* Find an already visited predecessor. */
929 : 1699591 : FOR_EACH_EDGE (e, ei, bb->preds)
930 : : {
931 : 1012134 : if (bitmap_bit_p (visited, e->src->index))
932 : 219130 : visited_pred = e->src;
933 : : }
934 : :
935 : 687457 : if (visited_pred)
936 : : {
937 : 202181 : basic_block be = dfs_find_deadend (bb);
938 : 202181 : gcc_assert (be != NULL);
939 : 202181 : bitmap_set_bit (visited, be->index);
940 : 202181 : stack.quick_push (ei_start (be->preds));
941 : 202181 : break;
942 : : }
943 : : }
944 : : }
945 : :
946 : 39443265 : if (has_unvisited_bb && stack.is_empty ())
947 : : {
948 : : /* No blocks are reachable from EXIT at all.
949 : : Find a dead-end from the ENTRY, and restart the iteration. */
950 : 75270 : basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun));
951 : 75270 : gcc_assert (be != NULL);
952 : 75270 : bitmap_set_bit (visited, be->index);
953 : 75270 : stack.quick_push (ei_start (be->preds));
954 : : }
955 : :
956 : : /* The only case the below while fires is
957 : : when there's an infinite loop. */
958 : : }
959 : 78886530 : while (!stack.is_empty ());
960 : :
961 : : /* EXIT_BLOCK is always included. */
962 : 39165814 : rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
963 : 39165814 : return n_basic_blocks_for_fn (fn);
964 : 39165814 : }
965 : :
966 : : /* Compute the depth first search order of FN and store in the array
967 : : PRE_ORDER if nonzero. If REV_POST_ORDER is nonzero, return the
968 : : reverse completion number for each node. Returns the number of nodes
969 : : visited. A depth first search tries to get as far away from the starting
970 : : point as quickly as possible.
971 : :
972 : : In case the function has unreachable blocks the number of nodes
973 : : visited does not include them.
974 : :
975 : : pre_order is a really a preorder numbering of the graph.
976 : : rev_post_order is really a reverse postorder numbering of the graph. */
977 : :
978 : : int
979 : 93727399 : pre_and_rev_post_order_compute_fn (struct function *fn,
980 : : int *pre_order, int *rev_post_order,
981 : : bool include_entry_exit)
982 : : {
983 : 93727399 : int pre_order_num = 0;
984 : 93727399 : int rev_post_order_num = n_basic_blocks_for_fn (fn) - 1;
985 : :
986 : : /* Allocate stack for back-tracking up CFG. */
987 : 93727399 : auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (fn) + 1);
988 : :
989 : 93727399 : if (include_entry_exit)
990 : : {
991 : 31863687 : if (pre_order)
992 : 0 : pre_order[pre_order_num] = ENTRY_BLOCK;
993 : 31863687 : pre_order_num++;
994 : 31863687 : if (rev_post_order)
995 : 31863687 : rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
996 : : }
997 : : else
998 : 61863712 : rev_post_order_num -= NUM_FIXED_BLOCKS;
999 : :
1000 : : /* BB flag to track nodes that have been visited. */
1001 : 93727399 : auto_bb_flag visited (fn);
1002 : :
1003 : : /* Push the first edge on to the stack. */
1004 : 93727399 : stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs));
1005 : :
1006 : 2634240119 : while (!stack.is_empty ())
1007 : : {
1008 : 2540512720 : basic_block src;
1009 : 2540512720 : basic_block dest;
1010 : :
1011 : : /* Look at the edge on the top of the stack. */
1012 : 2540512720 : edge_iterator ei = stack.last ();
1013 : 2540512720 : src = ei_edge (ei)->src;
1014 : 2540512720 : dest = ei_edge (ei)->dest;
1015 : :
1016 : : /* Check if the edge destination has been visited yet. */
1017 : 2540512720 : if (dest != EXIT_BLOCK_PTR_FOR_FN (fn)
1018 : 2540512720 : && ! (dest->flags & visited))
1019 : : {
1020 : : /* Mark that we have visited the destination. */
1021 : 1005200457 : dest->flags |= visited;
1022 : :
1023 : 1005200457 : if (pre_order)
1024 : 0 : pre_order[pre_order_num] = dest->index;
1025 : :
1026 : 1005200457 : pre_order_num++;
1027 : :
1028 : 1005200457 : if (EDGE_COUNT (dest->succs) > 0)
1029 : : /* Since the DEST node has been visited for the first
1030 : : time, check its successors. */
1031 : 944730334 : stack.quick_push (ei_start (dest->succs));
1032 : 60470123 : else if (rev_post_order)
1033 : : /* There are no successors for the DEST node so assign
1034 : : its reverse completion number. */
1035 : 60470123 : rev_post_order[rev_post_order_num--] = dest->index;
1036 : : }
1037 : : else
1038 : : {
1039 : 1535312263 : if (ei_one_before_end_p (ei)
1040 : 1038457733 : && src != ENTRY_BLOCK_PTR_FOR_FN (fn)
1041 : 2480042597 : && rev_post_order)
1042 : : /* There are no more successors for the SRC node
1043 : : so assign its reverse completion number. */
1044 : 944730334 : rev_post_order[rev_post_order_num--] = src->index;
1045 : :
1046 : 1535312263 : if (!ei_one_before_end_p (ei))
1047 : 496854530 : ei_next (&stack.last ());
1048 : : else
1049 : 1038457733 : stack.pop ();
1050 : : }
1051 : : }
1052 : :
1053 : 93727399 : if (include_entry_exit)
1054 : : {
1055 : 31863687 : if (pre_order)
1056 : 0 : pre_order[pre_order_num] = EXIT_BLOCK;
1057 : 31863687 : pre_order_num++;
1058 : 31863687 : if (rev_post_order)
1059 : 31863687 : rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
1060 : : }
1061 : :
1062 : : /* Clear the temporarily allocated flag. */
1063 : 93727399 : if (!rev_post_order)
1064 : : rev_post_order = pre_order;
1065 : 1162655230 : for (int i = 0; i < pre_order_num; ++i)
1066 : 1068927831 : BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags &= ~visited;
1067 : :
1068 : 93727399 : return pre_order_num;
1069 : 93727399 : }
1070 : :
1071 : : /* Like pre_and_rev_post_order_compute_fn but operating on the
1072 : : current function and asserting that all nodes were visited. */
1073 : :
1074 : : int
1075 : 72084153 : pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
1076 : : bool include_entry_exit)
1077 : : {
1078 : 72084153 : int pre_order_num
1079 : 72084153 : = pre_and_rev_post_order_compute_fn (cfun, pre_order, rev_post_order,
1080 : : include_entry_exit);
1081 : 72084153 : if (include_entry_exit)
1082 : : /* The number of nodes visited should be the number of blocks. */
1083 : 31863594 : gcc_assert (pre_order_num == n_basic_blocks_for_fn (cfun));
1084 : : else
1085 : : /* The number of nodes visited should be the number of blocks minus
1086 : : the entry and exit blocks which are not visited here. */
1087 : 40220559 : gcc_assert (pre_order_num
1088 : : == (n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS));
1089 : :
1090 : 72084153 : return pre_order_num;
1091 : : }
1092 : :
1093 : :
1094 : : /* Per basic-block data for rev_post_order_and_mark_dfs_back_seme,
1095 : : element of a sparsely populated array indexed by basic-block number. */
1096 : : typedef auto_vec<int, 2> scc_exit_vec_t;
1097 : : struct rpoamdbs_bb_data {
1098 : : int depth;
1099 : : int bb_to_pre;
1100 : : /* The basic-block index of the SCC entry of the block visited first
1101 : : (the SCC leader). */
1102 : : int scc;
1103 : : /* The index into the RPO array where the blocks SCC entries end
1104 : : (only valid for the SCC leader). */
1105 : : int scc_end;
1106 : : /* The indexes of the exits destinations of this SCC (only valid
1107 : : for the SCC leader). Initialized upon discovery of SCC leaders. */
1108 : : scc_exit_vec_t scc_exits;
1109 : : };
1110 : :
1111 : : /* Tag H as a header of B, weaving H and its loop header list into the
1112 : : current loop header list of B. */
1113 : :
1114 : : static void
1115 : 67054059 : tag_header (int b, int h, rpoamdbs_bb_data *bb_data)
1116 : : {
1117 : 67054059 : if (h == -1 || b == h)
1118 : : return;
1119 : : int cur1 = b;
1120 : : int cur2 = h;
1121 : 17751084 : while (bb_data[cur1].scc != -1)
1122 : : {
1123 : 3273171 : int ih = bb_data[cur1].scc;
1124 : 3273171 : if (ih == cur2)
1125 : : return;
1126 : 446272 : if (bb_data[ih].depth < bb_data[cur2].depth)
1127 : : {
1128 : 154571 : bb_data[cur1].scc = cur2;
1129 : 154571 : cur1 = cur2;
1130 : 154571 : cur2 = ih;
1131 : : }
1132 : : else
1133 : : cur1 = ih;
1134 : : }
1135 : 14477913 : bb_data[cur1].scc = cur2;
1136 : : }
1137 : :
1138 : : /* Comparator for a sort of two edges destinations E1 and E2 after their index
1139 : : in the PRE array as specified by BB_TO_PRE. */
1140 : :
1141 : : static int
1142 : 53737476 : cmp_edge_dest_pre (const void *e1_, const void *e2_, void *data_)
1143 : : {
1144 : 53737476 : const int *e1 = (const int *)e1_;
1145 : 53737476 : const int *e2 = (const int *)e2_;
1146 : 53737476 : rpoamdbs_bb_data *bb_data = (rpoamdbs_bb_data *)data_;
1147 : 53737476 : return (bb_data[*e1].bb_to_pre - bb_data[*e2].bb_to_pre);
1148 : : }
1149 : :
1150 : : /* Compute the reverse completion number of a depth first search
1151 : : on the SEME region denoted by the ENTRY edge and the EXIT_BBS set of
1152 : : exit block indexes and store it in the array REV_POST_ORDER.
1153 : : Also sets the EDGE_DFS_BACK edge flags according to this visitation
1154 : : order.
1155 : : Returns the number of nodes visited.
1156 : :
1157 : : In case the function has unreachable blocks the number of nodes
1158 : : visited does not include them.
1159 : :
1160 : : If FOR_ITERATION is true then compute an RPO where SCCs form a
1161 : : contiguous region in the RPO array.
1162 : : *TOPLEVEL_SCC_EXTENTS if not NULL is filled with pairs of
1163 : : *REV_POST_ORDER indexes denoting extents of the toplevel SCCs in
1164 : : this region. */
1165 : :
1166 : : int
1167 : 7161042 : rev_post_order_and_mark_dfs_back_seme (struct function *fn, edge entry,
1168 : : bitmap exit_bbs, bool for_iteration,
1169 : : int *rev_post_order,
1170 : : vec<std::pair<int, int> >
1171 : : *toplevel_scc_extents)
1172 : : {
1173 : 7161042 : int rev_post_order_num = 0;
1174 : :
1175 : : /* BB flag to track nodes that have been visited. */
1176 : 7161042 : auto_bb_flag visited (fn);
1177 : :
1178 : : /* Lazily initialized per-BB data for the two DFS walks below. */
1179 : 7161042 : rpoamdbs_bb_data *bb_data
1180 : 7161042 : = XNEWVEC (rpoamdbs_bb_data, last_basic_block_for_fn (fn));
1181 : :
1182 : : /* First DFS walk, loop discovery according to
1183 : : A New Algorithm for Identifying Loops in Decompilation
1184 : : by Tao Wei, Jian Mao, Wei Zou and You Chen of the Institute of
1185 : : Computer Science and Technology of the Peking University. */
1186 : 7161042 : auto_vec<edge_iterator, 20> ei_stack (n_basic_blocks_for_fn (fn) + 1);
1187 : 7161042 : auto_bb_flag is_header (fn);
1188 : 7161042 : int depth = 1;
1189 : 7161042 : unsigned n_sccs = 0;
1190 : :
1191 : 7161042 : basic_block dest = entry->dest;
1192 : 7161042 : edge_iterator ei;
1193 : 7161042 : int pre_num = 0;
1194 : :
1195 : : /* DFS process DEST. */
1196 : 67272400 : find_loops:
1197 : 67272400 : bb_data[dest->index].bb_to_pre = pre_num++;
1198 : 67272400 : bb_data[dest->index].depth = depth;
1199 : 67272400 : bb_data[dest->index].scc = -1;
1200 : 67272400 : depth++;
1201 : 67272400 : gcc_assert ((dest->flags & (is_header|visited)) == 0);
1202 : 67272400 : dest->flags |= visited;
1203 : 67272400 : ei = ei_start (dest->succs);
1204 : 160928987 : while (!ei_end_p (ei))
1205 : : {
1206 : 93656587 : ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
1207 : 93656587 : if (bitmap_bit_p (exit_bbs, ei_edge (ei)->dest->index))
1208 : : ;
1209 : 85975407 : else if (!(ei_edge (ei)->dest->flags & visited))
1210 : : {
1211 : 60111358 : ei_stack.quick_push (ei);
1212 : 60111358 : dest = ei_edge (ei)->dest;
1213 : : /* DFS recurse on DEST. */
1214 : 60111358 : goto find_loops;
1215 : :
1216 : 60111358 : ret_from_find_loops:
1217 : : /* Return point of DFS recursion. */
1218 : 120222716 : ei = ei_stack.pop ();
1219 : 60111358 : dest = ei_edge (ei)->src;
1220 : 60111358 : int header = bb_data[ei_edge (ei)->dest->index].scc;
1221 : 60111358 : tag_header (dest->index, header, bb_data);
1222 : 60111358 : depth = bb_data[dest->index].depth + 1;
1223 : : }
1224 : : else
1225 : : {
1226 : 25864049 : if (bb_data[ei_edge (ei)->dest->index].depth > 0) /* on the stack */
1227 : : {
1228 : 3533734 : ei_edge (ei)->flags |= EDGE_DFS_BACK;
1229 : 3533734 : n_sccs++;
1230 : 3533734 : ei_edge (ei)->dest->flags |= is_header;
1231 : 3533734 : ::new (&bb_data[ei_edge (ei)->dest->index].scc_exits)
1232 : 3533734 : auto_vec<int, 2> ();
1233 : 3533734 : tag_header (dest->index, ei_edge (ei)->dest->index, bb_data);
1234 : : }
1235 : 22330315 : else if (bb_data[ei_edge (ei)->dest->index].scc == -1)
1236 : : ;
1237 : : else
1238 : : {
1239 : 3418466 : int header = bb_data[ei_edge (ei)->dest->index].scc;
1240 : 3418466 : if (bb_data[header].depth > 0)
1241 : 3402816 : tag_header (dest->index, header, bb_data);
1242 : : else
1243 : : {
1244 : : /* A re-entry into an existing loop. */
1245 : : /* ??? Need to mark is_header? */
1246 : 21936 : while (bb_data[header].scc != -1)
1247 : : {
1248 : 12437 : header = bb_data[header].scc;
1249 : 12437 : if (bb_data[header].depth > 0)
1250 : : {
1251 : 6151 : tag_header (dest->index, header, bb_data);
1252 : 6151 : break;
1253 : : }
1254 : : }
1255 : : }
1256 : : }
1257 : : }
1258 : 93656587 : ei_next (&ei);
1259 : : }
1260 : 67272400 : rev_post_order[rev_post_order_num++] = dest->index;
1261 : : /* not on the stack anymore */
1262 : 67272400 : bb_data[dest->index].depth = -bb_data[dest->index].depth;
1263 : 67272400 : if (!ei_stack.is_empty ())
1264 : : /* Return from DFS recursion. */
1265 : 60111358 : goto ret_from_find_loops;
1266 : :
1267 : : /* Optimize for no SCCs found or !for_iteration. */
1268 : 7161042 : if (n_sccs == 0 || !for_iteration)
1269 : : {
1270 : : /* Clear the temporarily allocated flags. */
1271 : 31529847 : for (int i = 0; i < rev_post_order_num; ++i)
1272 : 51387876 : BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags
1273 : 25693938 : &= ~(is_header|visited);
1274 : : /* And swap elements. */
1275 : 16146431 : for (int i = 0; i < rev_post_order_num/2; ++i)
1276 : 10310522 : std::swap (rev_post_order[i], rev_post_order[rev_post_order_num-i-1]);
1277 : 5835909 : XDELETEVEC (bb_data);
1278 : :
1279 : 5835909 : return rev_post_order_num;
1280 : : }
1281 : :
1282 : : /* Next find SCC exits, clear the visited flag and compute an upper bound
1283 : : for the edge stack below. */
1284 : : unsigned edge_count = 0;
1285 : 42903595 : for (int i = 0; i < rev_post_order_num; ++i)
1286 : : {
1287 : 41578462 : int bb = rev_post_order[i];
1288 : 41578462 : BASIC_BLOCK_FOR_FN (fn, bb)->flags &= ~visited;
1289 : 41578462 : edge e;
1290 : 101169758 : FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (fn, bb)->succs)
1291 : : {
1292 : 59591296 : if (bitmap_bit_p (exit_bbs, e->dest->index))
1293 : 1395897 : continue;
1294 : 58195399 : edge_count++;
1295 : : /* if e is an exit from e->src, record it for
1296 : : bb_data[e->src].scc. */
1297 : 58195399 : int src_scc = e->src->index;
1298 : 58195399 : if (!(e->src->flags & is_header))
1299 : 51452367 : src_scc = bb_data[src_scc].scc;
1300 : 58195399 : if (src_scc == -1)
1301 : 30968188 : continue;
1302 : 27227211 : int dest_scc = e->dest->index;
1303 : 27227211 : if (!(e->dest->flags & is_header))
1304 : 22846981 : dest_scc = bb_data[dest_scc].scc;
1305 : 27227211 : if (src_scc == dest_scc)
1306 : 19756300 : continue;
1307 : : /* When dest_scc is nested insde src_scc it's not an
1308 : : exit. */
1309 : : int tem_dest_scc = dest_scc;
1310 : : unsigned dest_scc_depth = 0;
1311 : 8962036 : while (tem_dest_scc != -1)
1312 : : {
1313 : 2266006 : dest_scc_depth++;
1314 : 2266006 : if ((tem_dest_scc = bb_data[tem_dest_scc].scc) == src_scc)
1315 : : break;
1316 : : }
1317 : 7470911 : if (tem_dest_scc != -1)
1318 : 774881 : continue;
1319 : : /* When src_scc is nested inside dest_scc record an
1320 : : exit from the outermost SCC this edge exits. */
1321 : : int tem_src_scc = src_scc;
1322 : : unsigned src_scc_depth = 0;
1323 : 7401635 : while (tem_src_scc != -1)
1324 : : {
1325 : 7324231 : if (bb_data[tem_src_scc].scc == dest_scc)
1326 : : {
1327 : 6618626 : edge_count++;
1328 : 6618626 : bb_data[tem_src_scc].scc_exits.safe_push (e->dest->index);
1329 : 6618626 : break;
1330 : : }
1331 : 705605 : tem_src_scc = bb_data[tem_src_scc].scc;
1332 : 705605 : src_scc_depth++;
1333 : : }
1334 : : /* Else find the outermost SCC this edge exits (exits
1335 : : from the inner SCCs are not important for the DFS
1336 : : walk adjustment). Do so by computing the common
1337 : : ancestor SCC where the immediate child it to the source
1338 : : SCC is the exited SCC. */
1339 : 6696030 : if (tem_src_scc == -1)
1340 : : {
1341 : 77404 : edge_count++;
1342 : 77977 : while (src_scc_depth > dest_scc_depth)
1343 : : {
1344 : 573 : src_scc = bb_data[src_scc].scc;
1345 : 573 : src_scc_depth--;
1346 : : }
1347 : 77472 : while (dest_scc_depth > src_scc_depth)
1348 : : {
1349 : 68 : dest_scc = bb_data[dest_scc].scc;
1350 : 68 : dest_scc_depth--;
1351 : : }
1352 : 77406 : while (bb_data[src_scc].scc != bb_data[dest_scc].scc)
1353 : : {
1354 : : src_scc = bb_data[src_scc].scc;
1355 : : dest_scc = bb_data[dest_scc].scc;
1356 : : }
1357 : 77404 : bb_data[src_scc].scc_exits.safe_push (e->dest->index);
1358 : : }
1359 : : }
1360 : : }
1361 : :
1362 : : /* Now the second DFS walk to compute a RPO where the extent of SCCs
1363 : : is minimized thus SCC members are adjacent in the RPO array.
1364 : : This is done by performing a DFS walk computing RPO with first visiting
1365 : : extra direct edges from SCC entry to its exits.
1366 : : That simulates a DFS walk over the graph with SCCs collapsed and
1367 : : walking the SCCs themselves only when all outgoing edges from the
1368 : : SCCs have been visited.
1369 : : SCC_END[scc-header-index] is the position in the RPO array of the
1370 : : last member of the SCC. */
1371 : 2650266 : auto_vec<std::pair<basic_block, basic_block>, 20> estack (edge_count + 1);
1372 : 1325133 : int idx = rev_post_order_num;
1373 : 1325133 : basic_block edest;
1374 : 1325133 : dest = entry->dest;
1375 : :
1376 : : /* DFS process DEST. */
1377 : 41578462 : dfs_rpo:
1378 : 41578462 : gcc_checking_assert ((dest->flags & visited) == 0);
1379 : : /* Verify we enter SCCs through the same header and SCC nesting appears
1380 : : the same. */
1381 : 41578462 : gcc_assert (bb_data[dest->index].scc == -1
1382 : : || (BASIC_BLOCK_FOR_FN (fn, bb_data[dest->index].scc)->flags
1383 : : & visited));
1384 : 41578462 : dest->flags |= visited;
1385 : 41578462 : bb_data[dest->index].scc_end = -1;
1386 : 41578462 : if ((dest->flags & is_header)
1387 : 41578462 : && !bb_data[dest->index].scc_exits.is_empty ())
1388 : : {
1389 : : /* Push the all SCC exits as outgoing edges from its header to
1390 : : be visited first.
1391 : : To process exits in the same relative order as in the first
1392 : : DFS walk sort them after their destination PRE order index. */
1393 : 3365695 : gcc_sort_r (&bb_data[dest->index].scc_exits[0],
1394 : 3365695 : bb_data[dest->index].scc_exits.length (),
1395 : : sizeof (int), cmp_edge_dest_pre, bb_data);
1396 : : /* Process edges in reverse to match previous DFS walk order. */
1397 : 13427420 : for (int i = bb_data[dest->index].scc_exits.length () - 1; i >= 0; --i)
1398 : 13392060 : estack.quick_push (std::make_pair
1399 : 6696030 : (dest, BASIC_BLOCK_FOR_FN (fn, bb_data[dest->index].scc_exits[i])));
1400 : : }
1401 : : else
1402 : : {
1403 : 38212767 : if (dest->flags & is_header)
1404 : 116390 : bb_data[dest->index].scc_end = idx - 1;
1405 : : /* Push the edge vector in reverse to match the iteration order
1406 : : from the DFS walk above. */
1407 : 128886997 : for (int i = EDGE_COUNT (dest->succs) - 1; i >= 0; --i)
1408 : 52972341 : if (!bitmap_bit_p (exit_bbs, EDGE_SUCC (dest, i)->dest->index))
1409 : 51576725 : estack.quick_push (std::make_pair (dest,
1410 : 51576725 : EDGE_SUCC (dest, i)->dest));
1411 : : }
1412 : 105144758 : while (!estack.is_empty ()
1413 : 211614649 : && estack.last ().first == dest)
1414 : : {
1415 : 64891429 : edest = estack.last ().second;
1416 : 64891429 : if (!(edest->flags & visited))
1417 : : {
1418 : 40253329 : dest = edest;
1419 : : /* DFS recurse on DEST. */
1420 : 40253329 : goto dfs_rpo;
1421 : :
1422 : 40253329 : ret_from_dfs_rpo:
1423 : : /* Return point of DFS recursion. */
1424 : 40253329 : dest = estack.last ().first;
1425 : : }
1426 : 64891429 : estack.pop ();
1427 : : /* If we processed all SCC exits from DEST mark the SCC end
1428 : : since all RPO entries up to DEST itself will now belong
1429 : : to its SCC. The special-case of no SCC exits is already
1430 : : dealt with above. */
1431 : 64891429 : if (dest->flags & is_header
1432 : : /* When the last exit edge was processed mark the SCC end
1433 : : and push the regular edges. */
1434 : 13439062 : && bb_data[dest->index].scc_end == -1
1435 : 71585176 : && (estack.is_empty ()
1436 : 6693747 : || estack.last ().first != dest))
1437 : : {
1438 : 3365695 : bb_data[dest->index].scc_end = idx - 1;
1439 : : /* Push the edge vector in reverse to match the iteration order
1440 : : from the DFS walk above. */
1441 : 13350345 : for (int i = EDGE_COUNT (dest->succs) - 1; i >= 0; --i)
1442 : 6618955 : if (!bitmap_bit_p (exit_bbs, EDGE_SUCC (dest, i)->dest->index))
1443 : 6618674 : estack.quick_push (std::make_pair (dest,
1444 : 6618674 : EDGE_SUCC (dest, i)->dest));
1445 : : }
1446 : : }
1447 : 41578462 : rev_post_order[--idx] = dest->index;
1448 : 41578462 : if (!estack.is_empty ())
1449 : : /* Return from DFS recursion. */
1450 : 40253329 : goto ret_from_dfs_rpo;
1451 : :
1452 : : /* Each SCC extends are from the position of the header inside
1453 : : the RPO array up to RPO array index scc_end[header-index]. */
1454 : 1325133 : if (toplevel_scc_extents)
1455 : 7733497 : for (int i = 0; i < rev_post_order_num; i++)
1456 : : {
1457 : 7331809 : basic_block bb = BASIC_BLOCK_FOR_FN (fn, rev_post_order[i]);
1458 : 7331809 : if (bb->flags & is_header)
1459 : : {
1460 : 783847 : toplevel_scc_extents->safe_push
1461 : 783847 : (std::make_pair (i, bb_data[bb->index].scc_end));
1462 : 783847 : i = bb_data[bb->index].scc_end;
1463 : : }
1464 : : }
1465 : :
1466 : : /* Clear the temporarily allocated flags and free memory. */
1467 : 42903595 : for (int i = 0; i < rev_post_order_num; ++i)
1468 : : {
1469 : 41578462 : basic_block bb = BASIC_BLOCK_FOR_FN (fn, rev_post_order[i]);
1470 : 41578462 : if (bb->flags & is_header)
1471 : 3482085 : bb_data[bb->index].scc_exits.~scc_exit_vec_t ();
1472 : 41578462 : bb->flags &= ~(visited|is_header);
1473 : : }
1474 : :
1475 : 1325133 : XDELETEVEC (bb_data);
1476 : :
1477 : 1325133 : return rev_post_order_num;
1478 : 7161042 : }
1479 : :
1480 : :
1481 : :
1482 : : /* Compute the depth first search order on the _reverse_ graph and
1483 : : store it in the array DFS_ORDER, marking the nodes visited in VISITED.
1484 : : Returns the number of nodes visited.
1485 : :
1486 : : The computation is split into three pieces:
1487 : :
1488 : : flow_dfs_compute_reverse_init () creates the necessary data
1489 : : structures.
1490 : :
1491 : : flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1492 : : structures. The block will start the search.
1493 : :
1494 : : flow_dfs_compute_reverse_execute () continues (or starts) the
1495 : : search using the block on the top of the stack, stopping when the
1496 : : stack is empty.
1497 : :
1498 : : flow_dfs_compute_reverse_finish () destroys the necessary data
1499 : : structures.
1500 : :
1501 : : Thus, the user will probably call ..._init(), call ..._add_bb() to
1502 : : add a beginning basic block to the stack, call ..._execute(),
1503 : : possibly add another bb to the stack and again call ..._execute(),
1504 : : ..., and finally call _finish(). */
1505 : :
1506 : : /* Initialize the data structures used for depth-first search on the
1507 : : reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
1508 : : added to the basic block stack. DATA is the current depth-first
1509 : : search context. If INITIALIZE_STACK is nonzero, there is an
1510 : : element on the stack. */
1511 : :
1512 : 5160926 : depth_first_search::depth_first_search () :
1513 : 5160926 : m_stack (n_basic_blocks_for_fn (cfun)),
1514 : 5160926 : m_visited_blocks (last_basic_block_for_fn (cfun))
1515 : : {
1516 : 5160926 : bitmap_clear (m_visited_blocks);
1517 : 5160926 : }
1518 : :
1519 : : /* Add the specified basic block to the top of the dfs data
1520 : : structures. When the search continues, it will start at the
1521 : : block. */
1522 : :
1523 : : void
1524 : 59736183 : depth_first_search::add_bb (basic_block bb)
1525 : : {
1526 : 59736183 : m_stack.quick_push (bb);
1527 : 59736183 : bitmap_set_bit (m_visited_blocks, bb->index);
1528 : 59736183 : }
1529 : :
1530 : : /* Continue the depth-first search through the reverse graph starting with the
1531 : : block at the stack's top and ending when the stack is empty. Visited nodes
1532 : : are marked. Returns an unvisited basic block, or NULL if there is none
1533 : : available. */
1534 : :
1535 : : basic_block
1536 : 5185095 : depth_first_search::execute (basic_block last_unvisited)
1537 : : {
1538 : 5185095 : basic_block bb;
1539 : 5185095 : edge e;
1540 : 5185095 : edge_iterator ei;
1541 : :
1542 : 64921278 : while (!m_stack.is_empty ())
1543 : : {
1544 : 59736183 : bb = m_stack.pop ();
1545 : :
1546 : : /* Perform depth-first search on adjacent vertices. */
1547 : 132857974 : FOR_EACH_EDGE (e, ei, bb->preds)
1548 : 73121791 : if (!bitmap_bit_p (m_visited_blocks, e->src->index))
1549 : 54551088 : add_bb (e->src);
1550 : : }
1551 : :
1552 : : /* Determine if there are unvisited basic blocks. */
1553 : 64921278 : FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
1554 : 59760352 : if (!bitmap_bit_p (m_visited_blocks, bb->index))
1555 : 24169 : return bb;
1556 : :
1557 : : return NULL;
1558 : : }
1559 : :
1560 : : /* Performs dfs search from BB over vertices satisfying PREDICATE;
1561 : : if REVERSE, go against direction of edges. Returns number of blocks
1562 : : found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
1563 : : int
1564 : 189756347 : dfs_enumerate_from (basic_block bb, int reverse,
1565 : : bool (*predicate) (const_basic_block, const void *),
1566 : : basic_block *rslt, int rslt_max, const void *data)
1567 : : {
1568 : 189756347 : basic_block *st, lbb;
1569 : 189756347 : int sp = 0, tv = 0;
1570 : :
1571 : 189756347 : auto_bb_flag visited (cfun);
1572 : :
1573 : : #define MARK_VISITED(BB) ((BB)->flags |= visited)
1574 : : #define UNMARK_VISITED(BB) ((BB)->flags &= ~visited)
1575 : : #define VISITED_P(BB) (((BB)->flags & visited) != 0)
1576 : :
1577 : 189756347 : st = XNEWVEC (basic_block, rslt_max);
1578 : 189756347 : rslt[tv++] = st[sp++] = bb;
1579 : 189756347 : MARK_VISITED (bb);
1580 : 1260453376 : while (sp)
1581 : : {
1582 : 1070697029 : edge e;
1583 : 1070697029 : edge_iterator ei;
1584 : 1070697029 : lbb = st[--sp];
1585 : 1070697029 : if (reverse)
1586 : : {
1587 : 2609375788 : FOR_EACH_EDGE (e, ei, lbb->preds)
1588 : 1539957500 : if (!VISITED_P (e->src) && predicate (e->src, data))
1589 : : {
1590 : 880381173 : gcc_assert (tv != rslt_max);
1591 : 880381173 : rslt[tv++] = st[sp++] = e->src;
1592 : 880381173 : MARK_VISITED (e->src);
1593 : : }
1594 : : }
1595 : : else
1596 : : {
1597 : 3104167 : FOR_EACH_EDGE (e, ei, lbb->succs)
1598 : 1825426 : if (!VISITED_P (e->dest) && predicate (e->dest, data))
1599 : : {
1600 : 559509 : gcc_assert (tv != rslt_max);
1601 : 559509 : rslt[tv++] = st[sp++] = e->dest;
1602 : 559509 : MARK_VISITED (e->dest);
1603 : : }
1604 : : }
1605 : : }
1606 : 189756347 : free (st);
1607 : 1260453376 : for (sp = 0; sp < tv; sp++)
1608 : 1070697029 : UNMARK_VISITED (rslt[sp]);
1609 : 189756347 : return tv;
1610 : : #undef MARK_VISITED
1611 : : #undef UNMARK_VISITED
1612 : : #undef VISITED_P
1613 : 189756347 : }
1614 : :
1615 : :
1616 : : /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1617 : :
1618 : : This algorithm can be found in Timothy Harvey's PhD thesis, at
1619 : : http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1620 : : dominance algorithms.
1621 : :
1622 : : First, we identify each join point, j (any node with more than one
1623 : : incoming edge is a join point).
1624 : :
1625 : : We then examine each predecessor, p, of j and walk up the dominator tree
1626 : : starting at p.
1627 : :
1628 : : We stop the walk when we reach j's immediate dominator - j is in the
1629 : : dominance frontier of each of the nodes in the walk, except for j's
1630 : : immediate dominator. Intuitively, all of the rest of j's dominators are
1631 : : shared by j's predecessors as well.
1632 : : Since they dominate j, they will not have j in their dominance frontiers.
1633 : :
1634 : : The number of nodes touched by this algorithm is equal to the size
1635 : : of the dominance frontiers, no more, no less.
1636 : : */
1637 : :
1638 : : void
1639 : 7440338 : compute_dominance_frontiers (bitmap_head *frontiers)
1640 : : {
1641 : 7440338 : timevar_push (TV_DOM_FRONTIERS);
1642 : :
1643 : 7440338 : edge p;
1644 : 7440338 : edge_iterator ei;
1645 : 7440338 : basic_block b;
1646 : 127242286 : FOR_EACH_BB_FN (b, cfun)
1647 : : {
1648 : 147051316 : if (EDGE_COUNT (b->preds) >= 2)
1649 : : {
1650 : 27249368 : basic_block domsb = get_immediate_dominator (CDI_DOMINATORS, b);
1651 : 102899446 : FOR_EACH_EDGE (p, ei, b->preds)
1652 : : {
1653 : 75650078 : basic_block runner = p->src;
1654 : 75650078 : if (runner == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1655 : 6173 : continue;
1656 : :
1657 : 209444232 : while (runner != domsb)
1658 : : {
1659 : 153578289 : if (!bitmap_set_bit (&frontiers[runner->index], b->index))
1660 : : break;
1661 : 133800327 : runner = get_immediate_dominator (CDI_DOMINATORS, runner);
1662 : : }
1663 : : }
1664 : : }
1665 : : }
1666 : :
1667 : 7440338 : timevar_pop (TV_DOM_FRONTIERS);
1668 : 7440338 : }
1669 : :
1670 : : /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1671 : : return a bitmap with all the blocks in the iterated dominance
1672 : : frontier of the blocks in DEF_BLOCKS. DFS contains dominance
1673 : : frontier information as returned by compute_dominance_frontiers.
1674 : :
1675 : : The resulting set of blocks are the potential sites where PHI nodes
1676 : : are needed. The caller is responsible for freeing the memory
1677 : : allocated for the return value. */
1678 : :
1679 : : bitmap
1680 : 21712065 : compute_idf (bitmap def_blocks, bitmap_head *dfs)
1681 : : {
1682 : 21712065 : bitmap_iterator bi;
1683 : 21712065 : unsigned bb_index, i;
1684 : 21712065 : bitmap phi_insertion_points;
1685 : :
1686 : 21712065 : phi_insertion_points = BITMAP_ALLOC (NULL);
1687 : :
1688 : : /* Seed the work set with all the blocks in DEF_BLOCKS. */
1689 : 21712065 : auto_bitmap work_set;
1690 : 21712065 : bitmap_copy (work_set, def_blocks);
1691 : 21712065 : bitmap_tree_view (work_set);
1692 : :
1693 : : /* Pop a block off the workset, add every block that appears in
1694 : : the original block's DF that we have not already processed to
1695 : : the workset. Iterate until the workset is empty. Blocks
1696 : : which are added to the workset are potential sites for
1697 : : PHI nodes. */
1698 : 140760075 : while (!bitmap_empty_p (work_set))
1699 : : {
1700 : : /* The dominance frontier of a block is blocks after it so iterating
1701 : : on earlier blocks first is better.
1702 : : ??? Basic blocks are by no means guaranteed to be ordered in
1703 : : optimal order for this iteration. */
1704 : 97335945 : bb_index = bitmap_clear_first_set_bit (work_set);
1705 : :
1706 : : /* Since the registration of NEW -> OLD name mappings is done
1707 : : separately from the call to update_ssa, when updating the SSA
1708 : : form, the basic blocks where new and/or old names are defined
1709 : : may have disappeared by CFG cleanup calls. In this case,
1710 : : we may pull a non-existing block from the work stack. */
1711 : 97335945 : gcc_checking_assert (bb_index
1712 : : < (unsigned) last_basic_block_for_fn (cfun));
1713 : :
1714 : : /* The population counts of the dominance frontiers is low
1715 : : compared to that of phi_insertion_points which approaches
1716 : : the IDF and of work_set which is at most that of the IDF
1717 : : as well. That makes iterating over the DFS bitmap preferential
1718 : : to whole bitmap operations involving also phi_insertion_points. */
1719 : 201440682 : EXECUTE_IF_SET_IN_BITMAP (&dfs[bb_index], 0, i, bi)
1720 : 104104737 : if (bitmap_set_bit (phi_insertion_points, i))
1721 : 45223646 : bitmap_set_bit (work_set, i);
1722 : : }
1723 : :
1724 : 21712065 : return phi_insertion_points;
1725 : 21712065 : }
1726 : :
1727 : : /* Intersection and union of preds/succs for sbitmap based data flow
1728 : : solvers. All four functions defined below take the same arguments:
1729 : : B is the basic block to perform the operation for. DST is the
1730 : : target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1731 : : last_basic_block so that it can be indexed with basic block indices.
1732 : : DST may be (but does not have to be) SRC[B->index]. */
1733 : :
1734 : : /* Set the bitmap DST to the intersection of SRC of successors of
1735 : : basic block B. */
1736 : :
1737 : : void
1738 : 9386748 : bitmap_intersection_of_succs (sbitmap dst, sbitmap *src, basic_block b)
1739 : : {
1740 : 9386748 : unsigned int set_size = dst->size;
1741 : 9386748 : edge e;
1742 : 9386748 : unsigned ix;
1743 : :
1744 : 18776256 : for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
1745 : : {
1746 : 9318296 : e = EDGE_SUCC (b, ix);
1747 : 9318296 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1748 : 2530 : continue;
1749 : :
1750 : 9315766 : bitmap_copy (dst, src[e->dest->index]);
1751 : 9315766 : break;
1752 : : }
1753 : :
1754 : 9386748 : if (e == 0)
1755 : 68452 : bitmap_ones (dst);
1756 : : else
1757 : 30095290 : for (++ix; ix < EDGE_COUNT (b->succs); ix++)
1758 : : {
1759 : 5729349 : unsigned int i;
1760 : 5729349 : SBITMAP_ELT_TYPE *p, *r;
1761 : :
1762 : 5729349 : e = EDGE_SUCC (b, ix);
1763 : 5729349 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1764 : 0 : continue;
1765 : :
1766 : 5729349 : p = src[e->dest->index]->elms;
1767 : 5729349 : r = dst->elms;
1768 : 21948644 : for (i = 0; i < set_size; i++)
1769 : 16219295 : *r++ &= *p++;
1770 : : }
1771 : 9386748 : }
1772 : :
1773 : : /* Set the bitmap DST to the intersection of SRC of predecessors of
1774 : : basic block B. */
1775 : :
1776 : : void
1777 : 49723067 : bitmap_intersection_of_preds (sbitmap dst, sbitmap *src, basic_block b)
1778 : : {
1779 : 49723067 : unsigned int set_size = dst->size;
1780 : 49723067 : edge e;
1781 : 49723067 : unsigned ix;
1782 : :
1783 : 99446134 : for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
1784 : : {
1785 : 49723067 : e = EDGE_PRED (b, ix);
1786 : 49723067 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1787 : 0 : continue;
1788 : :
1789 : 49723067 : bitmap_copy (dst, src[e->src->index]);
1790 : 49723067 : break;
1791 : : }
1792 : :
1793 : 49723067 : if (e == 0)
1794 : 0 : bitmap_ones (dst);
1795 : : else
1796 : 255744534 : for (++ix; ix < EDGE_COUNT (b->preds); ix++)
1797 : : {
1798 : 78149200 : unsigned int i;
1799 : 78149200 : SBITMAP_ELT_TYPE *p, *r;
1800 : :
1801 : 78149200 : e = EDGE_PRED (b, ix);
1802 : 78149200 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1803 : 0 : continue;
1804 : :
1805 : 78149200 : p = src[e->src->index]->elms;
1806 : 78149200 : r = dst->elms;
1807 : 673457867 : for (i = 0; i < set_size; i++)
1808 : 595308667 : *r++ &= *p++;
1809 : : }
1810 : 49723067 : }
1811 : :
1812 : : /* Set the bitmap DST to the union of SRC of successors of
1813 : : basic block B. */
1814 : :
1815 : : void
1816 : 0 : bitmap_union_of_succs (sbitmap dst, sbitmap *src, basic_block b)
1817 : : {
1818 : 0 : unsigned int set_size = dst->size;
1819 : 0 : edge e;
1820 : 0 : unsigned ix;
1821 : :
1822 : 0 : for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
1823 : : {
1824 : 0 : e = EDGE_SUCC (b, ix);
1825 : 0 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1826 : 0 : continue;
1827 : :
1828 : 0 : bitmap_copy (dst, src[e->dest->index]);
1829 : 0 : break;
1830 : : }
1831 : :
1832 : 0 : if (ix == EDGE_COUNT (b->succs))
1833 : 0 : bitmap_clear (dst);
1834 : : else
1835 : 0 : for (ix++; ix < EDGE_COUNT (b->succs); ix++)
1836 : : {
1837 : 0 : unsigned int i;
1838 : 0 : SBITMAP_ELT_TYPE *p, *r;
1839 : :
1840 : 0 : e = EDGE_SUCC (b, ix);
1841 : 0 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1842 : 0 : continue;
1843 : :
1844 : 0 : p = src[e->dest->index]->elms;
1845 : 0 : r = dst->elms;
1846 : 0 : for (i = 0; i < set_size; i++)
1847 : 0 : *r++ |= *p++;
1848 : : }
1849 : 0 : }
1850 : :
1851 : : /* Set the bitmap DST to the union of SRC of predecessors of
1852 : : basic block B. */
1853 : :
1854 : : void
1855 : 0 : bitmap_union_of_preds (sbitmap dst, sbitmap *src, basic_block b)
1856 : : {
1857 : 0 : unsigned int set_size = dst->size;
1858 : 0 : edge e;
1859 : 0 : unsigned ix;
1860 : :
1861 : 0 : for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
1862 : : {
1863 : 0 : e = EDGE_PRED (b, ix);
1864 : 0 : if (e->src== ENTRY_BLOCK_PTR_FOR_FN (cfun))
1865 : 0 : continue;
1866 : :
1867 : 0 : bitmap_copy (dst, src[e->src->index]);
1868 : 0 : break;
1869 : : }
1870 : :
1871 : 0 : if (ix == EDGE_COUNT (b->preds))
1872 : 0 : bitmap_clear (dst);
1873 : : else
1874 : 0 : for (ix++; ix < EDGE_COUNT (b->preds); ix++)
1875 : : {
1876 : 0 : unsigned int i;
1877 : 0 : SBITMAP_ELT_TYPE *p, *r;
1878 : :
1879 : 0 : e = EDGE_PRED (b, ix);
1880 : 0 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1881 : 0 : continue;
1882 : :
1883 : 0 : p = src[e->src->index]->elms;
1884 : 0 : r = dst->elms;
1885 : 0 : for (i = 0; i < set_size; i++)
1886 : 0 : *r++ |= *p++;
1887 : : }
1888 : 0 : }
1889 : :
1890 : : /* Returns the list of basic blocks in the function in an order that guarantees
1891 : : that if a block X has just a single predecessor Y, then Y is after X in the
1892 : : ordering. */
1893 : :
1894 : : basic_block *
1895 : 7149005 : single_pred_before_succ_order (void)
1896 : : {
1897 : 7149005 : basic_block x, y;
1898 : 7149005 : basic_block *order = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1899 : 7149005 : unsigned n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
1900 : 7149005 : unsigned np, i;
1901 : 7149005 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
1902 : :
1903 : : #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1904 : : #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1905 : :
1906 : 7149005 : bitmap_clear (visited);
1907 : :
1908 : 7149005 : MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1909 : 63805365 : FOR_EACH_BB_FN (x, cfun)
1910 : : {
1911 : 56656360 : if (VISITED_P (x))
1912 : 1712833 : continue;
1913 : :
1914 : : /* Walk the predecessors of x as long as they have precisely one
1915 : : predecessor and add them to the list, so that they get stored
1916 : : after x. */
1917 : 1712833 : for (y = x, np = 1;
1918 : 99537533 : single_pred_p (y) && !VISITED_P (single_pred (y));
1919 : 1712833 : y = single_pred (y))
1920 : 1712833 : np++;
1921 : 54943527 : for (y = x, i = n - np;
1922 : 99537533 : single_pred_p (y) && !VISITED_P (single_pred (y));
1923 : 1712833 : y = single_pred (y), i++)
1924 : : {
1925 : 1712833 : order[i] = y;
1926 : 1712833 : MARK_VISITED (y);
1927 : : }
1928 : 54943527 : order[i] = y;
1929 : 54943527 : MARK_VISITED (y);
1930 : :
1931 : 54943527 : gcc_assert (i == n - 1);
1932 : : n -= np;
1933 : : }
1934 : :
1935 : 7149005 : gcc_assert (n == 0);
1936 : 7149005 : return order;
1937 : :
1938 : : #undef MARK_VISITED
1939 : : #undef VISITED_P
1940 : 7149005 : }
1941 : :
1942 : : /* Ignoring loop backedges, if BB has precisely one incoming edge then
1943 : : return that edge. Otherwise return NULL.
1944 : :
1945 : : When IGNORE_NOT_EXECUTABLE is true, also ignore edges that are not marked
1946 : : as executable. */
1947 : :
1948 : : edge
1949 : 88938986 : single_pred_edge_ignoring_loop_edges (basic_block bb,
1950 : : bool ignore_not_executable)
1951 : : {
1952 : 88938986 : edge retval = NULL;
1953 : 88938986 : edge e;
1954 : 88938986 : edge_iterator ei;
1955 : :
1956 : 174408556 : FOR_EACH_EDGE (e, ei, bb->preds)
1957 : : {
1958 : : /* A loop back edge can be identified by the destination of
1959 : : the edge dominating the source of the edge. */
1960 : 99673864 : if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1961 : 4383327 : continue;
1962 : :
1963 : : /* We can safely ignore edges that are not executable. */
1964 : 95290537 : if (ignore_not_executable
1965 : 23077350 : && (e->flags & EDGE_EXECUTABLE) == 0)
1966 : 45804 : continue;
1967 : :
1968 : : /* If we have already seen a non-loop edge, then we must have
1969 : : multiple incoming non-loop edges and thus we return NULL. */
1970 : 95244733 : if (retval)
1971 : : return NULL;
1972 : :
1973 : : /* This is the first non-loop incoming edge we have found. Record
1974 : : it. */
1975 : : retval = e;
1976 : : }
1977 : :
1978 : : return retval;
1979 : : }
|
