Line data Source code
1 : /* Control flow graph analysis code for GNU compiler.
2 : Copyright (C) 1987-2026 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 35452441 : mark_dfs_back_edges (struct function *fun)
63 : {
64 35452441 : int *pre;
65 35452441 : int *post;
66 35452441 : int prenum = 1;
67 35452441 : int postnum = 1;
68 35452441 : bool found = false;
69 :
70 : /* Allocate the preorder and postorder number arrays. */
71 35452441 : pre = XCNEWVEC (int, last_basic_block_for_fn (fun));
72 35452441 : post = XCNEWVEC (int, last_basic_block_for_fn (fun));
73 :
74 : /* Allocate stack for back-tracking up CFG. */
75 35452441 : 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 35452441 : auto_sbitmap visited (last_basic_block_for_fn (fun));
79 :
80 : /* None of the nodes in the CFG have been visited yet. */
81 35452441 : bitmap_clear (visited);
82 :
83 : /* Push the first edge on to the stack. */
84 35452441 : stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (fun)->succs));
85 :
86 989949012 : while (!stack.is_empty ())
87 : {
88 954496571 : basic_block src;
89 954496571 : basic_block dest;
90 :
91 : /* Look at the edge on the top of the stack. */
92 954496571 : edge_iterator ei = stack.last ();
93 954496571 : src = ei_edge (ei)->src;
94 954496571 : dest = ei_edge (ei)->dest;
95 954496571 : ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
96 :
97 : /* Check if the edge destination has been visited yet. */
98 916739698 : 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 384443390 : bitmap_set_bit (visited, dest->index);
103 :
104 384443390 : pre[dest->index] = prenum++;
105 384443390 : if (EDGE_COUNT (dest->succs) > 0)
106 : {
107 : /* Since the DEST node has been visited for the first
108 : time, check its successors. */
109 362702322 : stack.quick_push (ei_start (dest->succs));
110 : }
111 : else
112 21741068 : post[dest->index] = postnum++;
113 : }
114 : else
115 : {
116 570053181 : if (dest != EXIT_BLOCK_PTR_FOR_FN (fun)
117 532296308 : && src != ENTRY_BLOCK_PTR_FOR_FN (fun)
118 496843867 : && pre[src->index] >= pre[dest->index]
119 121041715 : && post[dest->index] == 0)
120 20476691 : ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
121 :
122 570053181 : if (ei_one_before_end_p (ei)
123 570053181 : && src != ENTRY_BLOCK_PTR_FOR_FN (fun))
124 362702322 : post[src->index] = postnum++;
125 :
126 570053181 : if (!ei_one_before_end_p (ei))
127 171898418 : ei_next (&stack.last ());
128 : else
129 398154763 : stack.pop ();
130 : }
131 : }
132 :
133 35452441 : free (pre);
134 35452441 : free (post);
135 :
136 35452441 : return found;
137 35452441 : }
138 :
139 : bool
140 27568919 : mark_dfs_back_edges (void)
141 : {
142 27568919 : 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 79362543 : find_unreachable_blocks (void)
185 : {
186 79362543 : edge e;
187 79362543 : edge_iterator ei;
188 79362543 : basic_block *tos, *worklist, bb;
189 :
190 79362543 : tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
191 :
192 : /* Clear all the reachability flags. */
193 :
194 1120118612 : FOR_EACH_BB_FN (bb, cfun)
195 1040756069 : 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 158725086 : FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
202 : {
203 79362543 : *tos++ = e->dest;
204 :
205 : /* Mark the block reachable. */
206 79362543 : e->dest->flags |= BB_REACHABLE;
207 : }
208 :
209 : /* Iterate: find everything reachable from what we've already seen. */
210 :
211 1126352274 : while (tos != worklist)
212 : {
213 1046989731 : basic_block b = *--tos;
214 :
215 2557439532 : FOR_EACH_EDGE (e, ei, b->succs)
216 : {
217 1510449801 : basic_block dest = e->dest;
218 :
219 1510449801 : if (!(dest->flags & BB_REACHABLE))
220 : {
221 967627188 : *tos++ = dest;
222 967627188 : dest->flags |= BB_REACHABLE;
223 : }
224 : }
225 : }
226 :
227 79362543 : free (worklist);
228 79362543 : }
229 :
230 : /* Verify that there are no unreachable blocks in the current function. */
231 :
232 : void
233 48796768 : verify_no_unreachable_blocks (void)
234 : {
235 48796768 : find_unreachable_blocks ();
236 :
237 48796768 : basic_block bb;
238 656212556 : FOR_EACH_BB_FN (bb, cfun)
239 607415788 : gcc_assert ((bb->flags & BB_REACHABLE) != 0);
240 48796768 : }
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 507683 : create_edge_list (void)
258 : {
259 507683 : struct edge_list *elist;
260 507683 : edge e;
261 507683 : int num_edges;
262 507683 : basic_block bb;
263 507683 : edge_iterator ei;
264 :
265 : /* Determine the number of edges in the flow graph by counting successor
266 : edges on each basic block. */
267 507683 : num_edges = 0;
268 10960293 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
269 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
270 : {
271 20904602 : num_edges += EDGE_COUNT (bb->succs);
272 : }
273 :
274 507683 : elist = XNEW (struct edge_list);
275 507683 : elist->num_edges = num_edges;
276 507683 : elist->index_to_edge = XNEWVEC (edge, num_edges);
277 :
278 507683 : num_edges = 0;
279 :
280 : /* Follow successors of blocks, and register these edges. */
281 10960293 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
282 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
283 26171282 : FOR_EACH_EDGE (e, ei, bb->succs)
284 15718672 : elist->index_to_edge[num_edges++] = e;
285 :
286 507683 : return elist;
287 : }
288 :
289 : /* This function free's memory associated with an edge list. */
290 :
291 : void
292 507683 : free_edge_list (struct edge_list *elist)
293 : {
294 507683 : if (elist)
295 : {
296 507683 : free (elist->index_to_edge);
297 507683 : free (elist);
298 : }
299 507683 : }
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 48808218 : control_dependences::set_control_dependence_map_bit (basic_block bb,
401 : int edge_index)
402 : {
403 48808218 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
404 : return;
405 48808218 : gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
406 48808218 : 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 50680687 : control_dependences::find_control_dependence (int edge_index)
421 : {
422 50680687 : basic_block current_block;
423 50680687 : basic_block ending_block;
424 :
425 50680687 : gcc_assert (get_edge_src (edge_index) != EXIT_BLOCK_PTR_FOR_FN (cfun));
426 :
427 50680687 : ending_block = get_immediate_dominator (CDI_POST_DOMINATORS,
428 : get_edge_src (edge_index));
429 :
430 50680687 : for (current_block = get_edge_dest (edge_index);
431 : current_block != ending_block
432 99488905 : && current_block != EXIT_BLOCK_PTR_FOR_FN (cfun);
433 48808218 : current_block = get_immediate_dominator (CDI_POST_DOMINATORS,
434 : current_block))
435 48808218 : set_control_dependence_map_bit (current_block, edge_index);
436 50680687 : }
437 :
438 : /* Record all blocks' control dependences on all edges in the edge
439 : list EL, ala Morgan, Section 3.6. */
440 :
441 3742542 : control_dependences::control_dependences ()
442 : {
443 3742542 : timevar_push (TV_CONTROL_DEPENDENCES);
444 :
445 : /* Initialize the edge list. */
446 3742542 : int num_edges = 0;
447 3742542 : basic_block bb;
448 41203981 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
449 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
450 73940734 : num_edges += EDGE_COUNT (bb->succs);
451 3742542 : m_el.create (num_edges);
452 3742542 : edge e;
453 3742542 : edge_iterator ei;
454 41203981 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
455 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
456 88156366 : 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 50694927 : if (e->flags & EDGE_ABNORMAL)
462 : {
463 14240 : num_edges--;
464 14240 : continue;
465 : }
466 50680687 : m_el.quick_push (std::make_pair (e->src->index, e->dest->index));
467 : }
468 :
469 3742542 : bitmap_obstack_initialize (&m_bitmaps);
470 3742542 : control_dependence_map.create (last_basic_block_for_fn (cfun));
471 3742542 : control_dependence_map.quick_grow_cleared (last_basic_block_for_fn (cfun));
472 49533259 : for (int i = 0; i < last_basic_block_for_fn (cfun); ++i)
473 42048175 : bitmap_initialize (&control_dependence_map[i], &m_bitmaps);
474 54423229 : for (int i = 0; i < num_edges; ++i)
475 50680687 : find_control_dependence (i);
476 :
477 3742542 : timevar_pop (TV_CONTROL_DEPENDENCES);
478 3742542 : }
479 :
480 : /* Free control dependences and the associated edge list. */
481 :
482 3742542 : control_dependences::~control_dependences ()
483 : {
484 3742542 : control_dependence_map.release ();
485 3742542 : m_el.release ();
486 3742542 : bitmap_obstack_release (&m_bitmaps);
487 3742542 : }
488 :
489 : /* Returns the bitmap of edges the basic-block I is dependent on. */
490 :
491 : bitmap
492 31816924 : control_dependences::get_edges_dependent_on (int i)
493 : {
494 31816924 : return &control_dependence_map[i];
495 : }
496 :
497 : /* Returns the edge source with index I from the edge list. */
498 :
499 : basic_block
500 148829380 : control_dependences::get_edge_src (int i)
501 : {
502 148829380 : 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 50680687 : control_dependences::get_edge_dest (int i)
509 : {
510 50680687 : 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 866025376 : find_edge (basic_block pred, basic_block succ)
519 : {
520 866025376 : edge e;
521 866025376 : edge_iterator ei;
522 :
523 2404492411 : if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
524 : {
525 952111142 : FOR_EACH_EDGE (e, ei, pred->succs)
526 730552642 : if (e->dest == succ)
527 : return e;
528 : }
529 : else
530 : {
531 235045656 : FOR_EACH_EDGE (e, ei, succ->preds)
532 144949976 : if (e->src == pred)
533 : 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 32 : find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
544 : {
545 32 : int x;
546 :
547 269 : for (x = 0; x < NUM_EDGES (edge_list); x++)
548 269 : if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
549 48 : && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
550 : 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 7251358 : remove_fake_predecessors (basic_block bb)
561 : {
562 7251358 : edge e;
563 7251358 : edge_iterator ei;
564 :
565 18952342 : for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
566 : {
567 11700984 : if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
568 4428941 : remove_edge (e);
569 : else
570 7272043 : ei_next (&ei);
571 : }
572 7251358 : }
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 3023 : remove_fake_edges (void)
580 : {
581 3023 : basic_block bb;
582 :
583 23563 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
584 20540 : remove_fake_predecessors (bb);
585 3023 : }
586 :
587 : /* This routine will remove all fake edges to the EXIT_BLOCK. */
588 :
589 : void
590 7230818 : remove_fake_exit_edges (void)
591 : {
592 7230818 : remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun));
593 7230818 : }
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 7233841 : add_noreturn_fake_exit_edges (void)
602 : {
603 7233841 : basic_block bb;
604 :
605 85216416 : FOR_EACH_BB_FN (bb, cfun)
606 77982575 : if (EDGE_COUNT (bb->succs) == 0)
607 4444261 : make_single_succ_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
608 7233841 : }
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 5753428 : 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 5753428 : 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 5753428 : depth_first_search dfs;
631 5753428 : dfs.add_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
632 :
633 : /* Repeatedly add fake edges, updating the unreachable nodes. */
634 5753428 : basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
635 5802780 : while (1)
636 : {
637 5778104 : unvisited_block = dfs.execute (unvisited_block);
638 5778104 : if (!unvisited_block)
639 : break;
640 :
641 24676 : basic_block deadend_block = dfs_find_deadend (unvisited_block);
642 24676 : edge e = make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun),
643 : EDGE_FAKE);
644 24676 : e->probability = profile_probability::never ();
645 24676 : dfs.add_bb (deadend_block);
646 24676 : }
647 5753428 : }
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 44706158 : post_order_compute (int *post_order, bool include_entry_exit,
656 : bool delete_unreachable)
657 : {
658 44706158 : int post_order_num = 0;
659 44706158 : int count;
660 :
661 44706158 : if (include_entry_exit)
662 43534468 : post_order[post_order_num++] = EXIT_BLOCK;
663 :
664 : /* Allocate stack for back-tracking up CFG. */
665 44706158 : 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 44706158 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
669 :
670 : /* None of the nodes in the CFG have been visited yet. */
671 44706158 : bitmap_clear (visited);
672 :
673 : /* Push the first edge on to the stack. */
674 44706158 : stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
675 :
676 1420656706 : while (!stack.is_empty ())
677 : {
678 1375950548 : basic_block src;
679 1375950548 : basic_block dest;
680 :
681 : /* Look at the edge on the top of the stack. */
682 1375950548 : edge_iterator ei = stack.last ();
683 1375950548 : src = ei_edge (ei)->src;
684 1375950548 : dest = ei_edge (ei)->dest;
685 :
686 : /* Check if the edge destination has been visited yet. */
687 1375950548 : if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
688 1375950548 : && ! bitmap_bit_p (visited, dest->index))
689 : {
690 : /* Mark that we have visited the destination. */
691 540427367 : bitmap_set_bit (visited, dest->index);
692 :
693 540427367 : if (EDGE_COUNT (dest->succs) > 0)
694 : /* Since the DEST node has been visited for the first
695 : time, check its successors. */
696 514446646 : stack.quick_push (ei_start (dest->succs));
697 : else
698 25980721 : post_order[post_order_num++] = dest->index;
699 : }
700 : else
701 : {
702 835523181 : if (ei_one_before_end_p (ei)
703 835523181 : && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
704 514446646 : post_order[post_order_num++] = src->index;
705 :
706 835523181 : if (!ei_one_before_end_p (ei))
707 276370377 : ei_next (&stack.last ());
708 : else
709 559152804 : stack.pop ();
710 : }
711 : }
712 :
713 44706158 : if (include_entry_exit)
714 : {
715 43534468 : post_order[post_order_num++] = ENTRY_BLOCK;
716 43534468 : count = post_order_num;
717 : }
718 : else
719 1171690 : count = post_order_num + 2;
720 :
721 : /* Delete the unreachable blocks if some were found and we are
722 : supposed to do it. */
723 44706158 : if (delete_unreachable && (count != n_basic_blocks_for_fn (cfun)))
724 : {
725 14603 : basic_block b;
726 14603 : basic_block next_bb;
727 14603 : for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
728 2411667 : != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb)
729 : {
730 2397064 : next_bb = b->next_bb;
731 :
732 2397064 : if (!(bitmap_bit_p (visited, b->index)))
733 34722 : delete_basic_block (b);
734 : }
735 :
736 14603 : tidy_fallthru_edges ();
737 : }
738 :
739 44706158 : return post_order_num;
740 44706158 : }
741 :
742 :
743 : /* Helper routine for inverted_rev_post_order_compute
744 : flow_dfs_compute_reverse_execute, and the reverse-CFG
745 : depth 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 451876 : dfs_find_deadend (basic_block bb)
767 : {
768 451876 : auto_bitmap visited;
769 451876 : basic_block next = bb;
770 :
771 1616799 : for (;;)
772 : {
773 2068675 : if (EDGE_COUNT (next->succs) == 0)
774 : return next;
775 :
776 1616799 : if (! bitmap_set_bit (visited, next->index))
777 : return bb;
778 :
779 1164923 : 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 1164923 : if (! bb->loop_father
784 1164923 : || ! loop_outer (bb->loop_father))
785 805388 : next = EDGE_SUCC (bb, 0)->dest;
786 : else
787 : {
788 359535 : edge_iterator ei;
789 359535 : edge e;
790 749650 : FOR_EACH_EDGE (e, ei, bb->succs)
791 436796 : if (loop_exit_edge_p (bb->loop_father, e))
792 : break;
793 359535 : next = e ? e->dest : EDGE_SUCC (bb, 0)->dest;
794 : }
795 : }
796 451876 : }
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 48797529 : inverted_rev_post_order_compute (struct function *fn,
825 : int *rev_post_order,
826 : sbitmap *start_points)
827 : {
828 48797529 : basic_block bb;
829 :
830 48797529 : int rev_post_order_num = n_basic_blocks_for_fn (fn) - 1;
831 :
832 48797529 : if (flag_checking)
833 48796768 : verify_no_unreachable_blocks ();
834 :
835 : /* Allocate stack for back-tracking up CFG. */
836 48797529 : 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 48797529 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
840 :
841 : /* None of the nodes in the CFG have been visited yet. */
842 48797529 : bitmap_clear (visited);
843 :
844 48797529 : if (start_points)
845 : {
846 813084 : FOR_ALL_BB_FN (bb, cfun)
847 793054 : if (bitmap_bit_p (*start_points, bb->index)
848 1349602 : && EDGE_COUNT (bb->preds) > 0)
849 : {
850 556548 : stack.quick_push (ei_start (bb->preds));
851 556548 : bitmap_set_bit (visited, bb->index);
852 : }
853 48816586 : if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds))
854 : {
855 19057 : stack.quick_push (ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds));
856 19057 : 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 752998791 : FOR_ALL_BB_FN (bb, cfun)
862 704221292 : if (EDGE_COUNT (bb->succs) == 0)
863 : {
864 : /* Push the initial edge on to the stack. */
865 777540914 : if (EDGE_COUNT (bb->preds) > 0)
866 : {
867 73319622 : stack.quick_push (ei_start (bb->preds));
868 73319622 : bitmap_set_bit (visited, bb->index);
869 : }
870 : }
871 :
872 49132039 : do
873 : {
874 49132039 : bool has_unvisited_bb = false;
875 :
876 : /* The inverted traversal loop. */
877 1614051574 : while (!stack.is_empty ())
878 : {
879 1564919535 : edge_iterator ei;
880 1564919535 : basic_block pred;
881 :
882 : /* Look at the edge on the top of the stack. */
883 1564919535 : ei = stack.last ();
884 1564919535 : bb = ei_edge (ei)->dest;
885 1564919535 : pred = ei_edge (ei)->src;
886 :
887 : /* Check if the predecessor has been visited yet. */
888 1564919535 : if (! bitmap_bit_p (visited, pred->index))
889 : {
890 : /* Mark that we have visited the destination. */
891 629656011 : bitmap_set_bit (visited, pred->index);
892 :
893 629656011 : if (EDGE_COUNT (pred->preds) > 0)
894 : /* Since the predecessor node has been visited for the first
895 : time, check its predecessors. */
896 580858482 : stack.quick_push (ei_start (pred->preds));
897 : else
898 48797529 : rev_post_order[rev_post_order_num--] = pred->index;
899 : }
900 : else
901 : {
902 935263524 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
903 935263524 : && ei_one_before_end_p (ei))
904 607419288 : rev_post_order[rev_post_order_num--] = bb->index;
905 :
906 935263524 : if (!ei_one_before_end_p (ei))
907 280175305 : ei_next (&stack.last ());
908 : else
909 655088219 : 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 709048666 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
917 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
918 660156822 : if (!bitmap_bit_p (visited, bb->index))
919 : {
920 882300 : has_unvisited_bb = true;
921 :
922 660704612 : if (EDGE_COUNT (bb->preds) > 0)
923 : {
924 787985 : edge_iterator ei;
925 787985 : edge e;
926 787985 : basic_block visited_pred = NULL;
927 :
928 : /* Find an already visited predecessor. */
929 1967208 : FOR_EACH_EDGE (e, ei, bb->preds)
930 : {
931 1179223 : if (bitmap_bit_p (visited, e->src->index))
932 261178 : visited_pred = e->src;
933 : }
934 :
935 787985 : if (visited_pred)
936 : {
937 240195 : basic_block be = dfs_find_deadend (bb);
938 240195 : gcc_assert (be != NULL);
939 240195 : bitmap_set_bit (visited, be->index);
940 240195 : stack.quick_push (ei_start (be->preds));
941 240195 : break;
942 : }
943 : }
944 : }
945 :
946 49132039 : 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 94315 : basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun));
951 94315 : gcc_assert (be != NULL);
952 94315 : bitmap_set_bit (visited, be->index);
953 94315 : 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 98264078 : while (!stack.is_empty ());
960 :
961 : /* EXIT_BLOCK is always included. */
962 48797529 : rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
963 48797529 : return n_basic_blocks_for_fn (fn);
964 48797529 : }
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 103846798 : 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 103846798 : int pre_order_num = 0;
984 103846798 : int rev_post_order_num = n_basic_blocks_for_fn (fn) - 1;
985 :
986 : /* Allocate stack for back-tracking up CFG. */
987 103846798 : auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (fn) + 1);
988 :
989 103846798 : if (include_entry_exit)
990 : {
991 40223584 : if (pre_order)
992 0 : pre_order[pre_order_num] = ENTRY_BLOCK;
993 40223584 : pre_order_num++;
994 40223584 : if (rev_post_order)
995 40223584 : rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
996 : }
997 : else
998 63623214 : rev_post_order_num -= NUM_FIXED_BLOCKS;
999 :
1000 : /* BB flag to track nodes that have been visited. */
1001 103846798 : auto_bb_flag visited (fn);
1002 :
1003 : /* Push the first edge on to the stack. */
1004 103846798 : stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs));
1005 :
1006 3059265134 : while (!stack.is_empty ())
1007 : {
1008 2955418336 : basic_block src;
1009 2955418336 : basic_block dest;
1010 :
1011 : /* Look at the edge on the top of the stack. */
1012 2955418336 : edge_iterator ei = stack.last ();
1013 2955418336 : src = ei_edge (ei)->src;
1014 2955418336 : dest = ei_edge (ei)->dest;
1015 :
1016 : /* Check if the edge destination has been visited yet. */
1017 2955418336 : if (dest != EXIT_BLOCK_PTR_FOR_FN (fn)
1018 2955418336 : && ! (dest->flags & visited))
1019 : {
1020 : /* Mark that we have visited the destination. */
1021 1171029453 : dest->flags |= visited;
1022 :
1023 1171029453 : if (pre_order)
1024 0 : pre_order[pre_order_num] = dest->index;
1025 :
1026 1171029453 : pre_order_num++;
1027 :
1028 1171029453 : if (EDGE_COUNT (dest->succs) > 0)
1029 : /* Since the DEST node has been visited for the first
1030 : time, check its successors. */
1031 1095338100 : stack.quick_push (ei_start (dest->succs));
1032 75691353 : else if (rev_post_order)
1033 : /* There are no successors for the DEST node so assign
1034 : its reverse completion number. */
1035 75691353 : rev_post_order[rev_post_order_num--] = dest->index;
1036 : }
1037 : else
1038 : {
1039 1784388883 : if (ei_one_before_end_p (ei)
1040 1199184898 : && src != ENTRY_BLOCK_PTR_FOR_FN (fn)
1041 2879726983 : && rev_post_order)
1042 : /* There are no more successors for the SRC node
1043 : so assign its reverse completion number. */
1044 1095338100 : rev_post_order[rev_post_order_num--] = src->index;
1045 :
1046 1784388883 : if (!ei_one_before_end_p (ei))
1047 585203985 : ei_next (&stack.last ());
1048 : else
1049 1199184898 : stack.pop ();
1050 : }
1051 : }
1052 :
1053 103846798 : if (include_entry_exit)
1054 : {
1055 40223584 : if (pre_order)
1056 0 : pre_order[pre_order_num] = EXIT_BLOCK;
1057 40223584 : pre_order_num++;
1058 40223584 : if (rev_post_order)
1059 40223584 : rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
1060 : }
1061 :
1062 : /* Clear the temporarily allocated flag. */
1063 103846798 : if (!rev_post_order)
1064 : rev_post_order = pre_order;
1065 1355323419 : for (int i = 0; i < pre_order_num; ++i)
1066 1251476621 : BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags &= ~visited;
1067 :
1068 103846798 : return pre_order_num;
1069 103846798 : }
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 85468283 : pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
1076 : bool include_entry_exit)
1077 : {
1078 85468283 : int pre_order_num
1079 85468283 : = pre_and_rev_post_order_compute_fn (cfun, pre_order, rev_post_order,
1080 : include_entry_exit);
1081 85468283 : if (include_entry_exit)
1082 : /* The number of nodes visited should be the number of blocks. */
1083 40223439 : 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 45244844 : gcc_assert (pre_order_num
1088 : == (n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS));
1089 :
1090 85468283 : 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 127254942 : tag_header (int b, int h, rpoamdbs_bb_data *bb_data)
1116 : {
1117 127254942 : if (h == -1 || b == h)
1118 : return;
1119 : int cur1 = b;
1120 : int cur2 = h;
1121 33841450 : while (bb_data[cur1].scc != -1)
1122 : {
1123 6600641 : int ih = bb_data[cur1].scc;
1124 6600641 : if (ih == cur2)
1125 : return;
1126 896888 : if (bb_data[ih].depth < bb_data[cur2].depth)
1127 : {
1128 313987 : bb_data[cur1].scc = cur2;
1129 313987 : cur1 = cur2;
1130 313987 : cur2 = ih;
1131 : }
1132 : else
1133 : cur1 = ih;
1134 : }
1135 27240809 : 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 48849671 : cmp_edge_dest_pre (const void *e1_, const void *e2_, void *data_)
1143 : {
1144 48849671 : const int *e1 = (const int *)e1_;
1145 48849671 : const int *e2 = (const int *)e2_;
1146 48849671 : rpoamdbs_bb_data *bb_data = (rpoamdbs_bb_data *)data_;
1147 48849671 : 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 13801068 : 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 13801068 : int rev_post_order_num = 0;
1174 :
1175 : /* BB flag to track nodes that have been visited. */
1176 13801068 : auto_bb_flag visited (fn);
1177 :
1178 : /* Lazily initialized per-BB data for the two DFS walks below. */
1179 13801068 : rpoamdbs_bb_data *bb_data
1180 13801068 : = 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 13801068 : auto_vec<edge_iterator, 20> ei_stack (n_basic_blocks_for_fn (fn) + 1);
1187 13801068 : auto_bb_flag is_header (fn);
1188 13801068 : int depth = 1;
1189 13801068 : unsigned n_sccs = 0;
1190 :
1191 13801068 : basic_block dest = entry->dest;
1192 13801068 : edge_iterator ei;
1193 13801068 : int pre_num = 0;
1194 :
1195 : /* DFS process DEST. */
1196 127142240 : find_loops:
1197 127142240 : bb_data[dest->index].bb_to_pre = pre_num++;
1198 127142240 : bb_data[dest->index].depth = depth;
1199 127142240 : bb_data[dest->index].scc = -1;
1200 127142240 : depth++;
1201 127142240 : gcc_assert ((dest->flags & (is_header|visited)) == 0);
1202 127142240 : dest->flags |= visited;
1203 127142240 : ei = ei_start (dest->succs);
1204 304101372 : while (!ei_end_p (ei))
1205 : {
1206 176959132 : ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
1207 176959132 : if (bitmap_bit_p (exit_bbs, ei_edge (ei)->dest->index))
1208 : ;
1209 162590581 : else if (!(ei_edge (ei)->dest->flags & visited))
1210 : {
1211 113341172 : ei_stack.quick_push (ei);
1212 113341172 : dest = ei_edge (ei)->dest;
1213 : /* DFS recurse on DEST. */
1214 113341172 : goto find_loops;
1215 :
1216 113341172 : ret_from_find_loops:
1217 : /* Return point of DFS recursion. */
1218 226682344 : ei = ei_stack.pop ();
1219 113341172 : dest = ei_edge (ei)->src;
1220 113341172 : int header = bb_data[ei_edge (ei)->dest->index].scc;
1221 113341172 : tag_header (dest->index, header, bb_data);
1222 113341172 : depth = bb_data[dest->index].depth + 1;
1223 : }
1224 : else
1225 : {
1226 49249409 : if (bb_data[ei_edge (ei)->dest->index].depth > 0) /* on the stack */
1227 : {
1228 7114886 : ei_edge (ei)->flags |= EDGE_DFS_BACK;
1229 7114886 : n_sccs++;
1230 7114886 : ei_edge (ei)->dest->flags |= is_header;
1231 7114886 : ::new (&bb_data[ei_edge (ei)->dest->index].scc_exits)
1232 7114886 : auto_vec<int, 2> ();
1233 7114886 : tag_header (dest->index, ei_edge (ei)->dest->index, bb_data);
1234 : }
1235 42134523 : else if (bb_data[ei_edge (ei)->dest->index].scc == -1)
1236 : ;
1237 : else
1238 : {
1239 6817368 : int header = bb_data[ei_edge (ei)->dest->index].scc;
1240 6817368 : if (bb_data[header].depth > 0)
1241 6783549 : 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 51158 : while (bb_data[header].scc != -1)
1247 : {
1248 32674 : header = bb_data[header].scc;
1249 32674 : if (bb_data[header].depth > 0)
1250 : {
1251 15335 : tag_header (dest->index, header, bb_data);
1252 15335 : break;
1253 : }
1254 : }
1255 : }
1256 : }
1257 : }
1258 176959132 : ei_next (&ei);
1259 : }
1260 127142240 : rev_post_order[rev_post_order_num++] = dest->index;
1261 : /* not on the stack anymore */
1262 127142240 : bb_data[dest->index].depth = -bb_data[dest->index].depth;
1263 127142240 : if (!ei_stack.is_empty ())
1264 : /* Return from DFS recursion. */
1265 113341172 : goto ret_from_find_loops;
1266 :
1267 : /* Optimize for no SCCs found or !for_iteration. */
1268 13801068 : if (n_sccs == 0 || !for_iteration)
1269 : {
1270 : /* Clear the temporarily allocated flags. */
1271 90341435 : for (int i = 0; i < rev_post_order_num; ++i)
1272 156132224 : BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags
1273 78066112 : &= ~(is_header|visited);
1274 : /* And swap elements. */
1275 46135695 : for (int i = 0; i < rev_post_order_num/2; ++i)
1276 33860372 : std::swap (rev_post_order[i], rev_post_order[rev_post_order_num-i-1]);
1277 12275323 : XDELETEVEC (bb_data);
1278 :
1279 12275323 : 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 50601873 : for (int i = 0; i < rev_post_order_num; ++i)
1286 : {
1287 49076128 : int bb = rev_post_order[i];
1288 49076128 : BASIC_BLOCK_FOR_FN (fn, bb)->flags &= ~visited;
1289 49076128 : edge e;
1290 119578973 : FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (fn, bb)->succs)
1291 : {
1292 70502845 : if (bitmap_bit_p (exit_bbs, e->dest->index))
1293 1631520 : continue;
1294 68871325 : edge_count++;
1295 : /* if e is an exit from e->src, record it for
1296 : bb_data[e->src].scc. */
1297 68871325 : int src_scc = e->src->index;
1298 68871325 : if (!(e->src->flags & is_header))
1299 60722543 : src_scc = bb_data[src_scc].scc;
1300 68871325 : if (src_scc == -1)
1301 36397573 : continue;
1302 32473752 : int dest_scc = e->dest->index;
1303 32473752 : if (!(e->dest->flags & is_header))
1304 27132057 : dest_scc = bb_data[dest_scc].scc;
1305 32473752 : if (src_scc == dest_scc)
1306 23846648 : continue;
1307 : /* When dest_scc is nested inside src_scc it's not an
1308 : exit. */
1309 : int tem_dest_scc = dest_scc;
1310 : unsigned dest_scc_depth = 0;
1311 10503126 : while (tem_dest_scc != -1)
1312 : {
1313 2853162 : dest_scc_depth++;
1314 2853162 : if ((tem_dest_scc = bb_data[tem_dest_scc].scc) == src_scc)
1315 : break;
1316 : }
1317 8627104 : if (tem_dest_scc != -1)
1318 977140 : 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 8380977 : while (tem_src_scc != -1)
1324 : {
1325 8290589 : if (bb_data[tem_src_scc].scc == dest_scc)
1326 : {
1327 7559576 : edge_count++;
1328 7559576 : bb_data[tem_src_scc].scc_exits.safe_push (e->dest->index);
1329 7559576 : break;
1330 : }
1331 731013 : tem_src_scc = bb_data[tem_src_scc].scc;
1332 731013 : 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 7649964 : if (tem_src_scc == -1)
1340 : {
1341 90388 : edge_count++;
1342 91603 : while (src_scc_depth > dest_scc_depth)
1343 : {
1344 1215 : src_scc = bb_data[src_scc].scc;
1345 1215 : src_scc_depth--;
1346 : }
1347 90526 : while (dest_scc_depth > src_scc_depth)
1348 : {
1349 138 : dest_scc = bb_data[dest_scc].scc;
1350 138 : dest_scc_depth--;
1351 : }
1352 90394 : 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 90388 : 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 3051490 : auto_vec<std::pair<basic_block, basic_block>, 20> estack (edge_count + 1);
1372 1525745 : int idx = rev_post_order_num;
1373 1525745 : basic_block edest;
1374 1525745 : dest = entry->dest;
1375 :
1376 : /* DFS process DEST. */
1377 49076128 : dfs_rpo:
1378 49076128 : gcc_checking_assert ((dest->flags & visited) == 0);
1379 : /* Verify we enter SCCs through the same header and SCC nesting appears
1380 : the same. */
1381 49076128 : gcc_assert (bb_data[dest->index].scc == -1
1382 : || (BASIC_BLOCK_FOR_FN (fn, bb_data[dest->index].scc)->flags
1383 : & visited));
1384 49076128 : dest->flags |= visited;
1385 49076128 : bb_data[dest->index].scc_end = -1;
1386 49076128 : if ((dest->flags & is_header)
1387 49076128 : && !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 4064802 : gcc_sort_r (&bb_data[dest->index].scc_exits[0],
1394 4064802 : 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 15779568 : for (int i = bb_data[dest->index].scc_exits.length () - 1; i >= 0; --i)
1398 15299928 : estack.quick_push (std::make_pair
1399 7649964 : (dest, BASIC_BLOCK_FOR_FN (fn, bb_data[dest->index].scc_exits[i])));
1400 : }
1401 : else
1402 : {
1403 45011326 : if (dest->flags & is_header)
1404 151017 : 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 151874456 : for (int i = EDGE_COUNT (dest->succs) - 1; i >= 0; --i)
1408 62514657 : if (!bitmap_bit_p (exit_bbs, EDGE_SUCC (dest, i)->dest->index))
1409 60883493 : estack.quick_push (std::make_pair (dest,
1410 60883493 : EDGE_SUCC (dest, i)->dest));
1411 : }
1412 124071672 : while (!estack.is_empty ()
1413 249669089 : && estack.last ().first == dest)
1414 : {
1415 76521289 : edest = estack.last ().second;
1416 76521289 : if (!(edest->flags & visited))
1417 : {
1418 47550383 : dest = edest;
1419 : /* DFS recurse on DEST. */
1420 47550383 : goto dfs_rpo;
1421 :
1422 47550383 : ret_from_dfs_rpo:
1423 : /* Return point of DFS recursion. */
1424 47550383 : dest = estack.last ().first;
1425 : }
1426 76521289 : 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 76521289 : if (dest->flags & is_header
1432 : /* When the last exit edge was processed mark the SCC end
1433 : and push the regular edges. */
1434 15798746 : && bb_data[dest->index].scc_end == -1
1435 84168466 : && (estack.is_empty ()
1436 7647177 : || estack.last ().first != dest))
1437 : {
1438 4064802 : 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 16117792 : for (int i = EDGE_COUNT (dest->succs) - 1; i >= 0; --i)
1442 7988188 : if (!bitmap_bit_p (exit_bbs, EDGE_SUCC (dest, i)->dest->index))
1443 7987832 : estack.quick_push (std::make_pair (dest,
1444 7987832 : EDGE_SUCC (dest, i)->dest));
1445 : }
1446 : }
1447 49076128 : rev_post_order[--idx] = dest->index;
1448 49076128 : if (!estack.is_empty ())
1449 : /* Return from DFS recursion. */
1450 47550383 : 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 1525745 : if (toplevel_scc_extents)
1455 9357299 : for (int i = 0; i < rev_post_order_num; i++)
1456 : {
1457 8873512 : basic_block bb = BASIC_BLOCK_FOR_FN (fn, rev_post_order[i]);
1458 8873512 : if (bb->flags & is_header)
1459 : {
1460 986121 : toplevel_scc_extents->safe_push
1461 986121 : (std::make_pair (i, bb_data[bb->index].scc_end));
1462 986121 : i = bb_data[bb->index].scc_end;
1463 : }
1464 : }
1465 :
1466 : /* Clear the temporarily allocated flags and free memory. */
1467 50601873 : for (int i = 0; i < rev_post_order_num; ++i)
1468 : {
1469 49076128 : basic_block bb = BASIC_BLOCK_FOR_FN (fn, rev_post_order[i]);
1470 49076128 : if (bb->flags & is_header)
1471 4215819 : bb_data[bb->index].scc_exits.~scc_exit_vec_t ();
1472 49076128 : bb->flags &= ~(visited|is_header);
1473 : }
1474 :
1475 1525745 : XDELETEVEC (bb_data);
1476 :
1477 1525745 : return rev_post_order_num;
1478 13801068 : }
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 5753428 : depth_first_search::depth_first_search () :
1513 5753428 : m_stack (n_basic_blocks_for_fn (cfun)),
1514 5753428 : m_visited_blocks (last_basic_block_for_fn (cfun))
1515 : {
1516 5753428 : bitmap_clear (m_visited_blocks);
1517 5753428 : }
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 68533190 : depth_first_search::add_bb (basic_block bb)
1525 : {
1526 68533190 : m_stack.quick_push (bb);
1527 68533190 : bitmap_set_bit (m_visited_blocks, bb->index);
1528 68533190 : }
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 5778104 : depth_first_search::execute (basic_block last_unvisited)
1537 : {
1538 5778104 : basic_block bb;
1539 5778104 : edge e;
1540 5778104 : edge_iterator ei;
1541 :
1542 74311294 : while (!m_stack.is_empty ())
1543 : {
1544 68533190 : bb = m_stack.pop ();
1545 :
1546 : /* Perform depth-first search on adjacent vertices. */
1547 153034843 : FOR_EACH_EDGE (e, ei, bb->preds)
1548 84501653 : if (!bitmap_bit_p (m_visited_blocks, e->src->index))
1549 62755086 : add_bb (e->src);
1550 : }
1551 :
1552 : /* Determine if there are unvisited basic blocks. */
1553 74311294 : FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
1554 68557866 : if (!bitmap_bit_p (m_visited_blocks, bb->index))
1555 : 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 229186570 : 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 229186570 : basic_block *st, lbb;
1569 229186570 : int sp = 0, tv = 0;
1570 :
1571 229186570 : 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 229186570 : st = XNEWVEC (basic_block, rslt_max);
1578 229186570 : rslt[tv++] = st[sp++] = bb;
1579 229186570 : MARK_VISITED (bb);
1580 1523517347 : while (sp)
1581 : {
1582 1294330777 : edge e;
1583 1294330777 : edge_iterator ei;
1584 1294330777 : lbb = st[--sp];
1585 1294330777 : if (reverse)
1586 : {
1587 3167290237 : FOR_EACH_EDGE (e, ei, lbb->preds)
1588 1874907593 : if (!VISITED_P (e->src) && predicate (e->src, data))
1589 : {
1590 1064252919 : gcc_assert (tv != rslt_max);
1591 1064252919 : rslt[tv++] = st[sp++] = e->src;
1592 1064252919 : MARK_VISITED (e->src);
1593 : }
1594 : }
1595 : else
1596 : {
1597 4769314 : FOR_EACH_EDGE (e, ei, lbb->succs)
1598 2821181 : if (!VISITED_P (e->dest) && predicate (e->dest, data))
1599 : {
1600 891288 : gcc_assert (tv != rslt_max);
1601 891288 : rslt[tv++] = st[sp++] = e->dest;
1602 891288 : MARK_VISITED (e->dest);
1603 : }
1604 : }
1605 : }
1606 229186570 : free (st);
1607 1523517347 : for (sp = 0; sp < tv; sp++)
1608 1294330777 : UNMARK_VISITED (rslt[sp]);
1609 229186570 : return tv;
1610 : #undef MARK_VISITED
1611 : #undef UNMARK_VISITED
1612 : #undef VISITED_P
1613 229186570 : }
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 13463374 : compute_dominance_frontiers (bitmap_head *frontiers)
1640 : {
1641 13463374 : timevar_push (TV_DOM_FRONTIERS);
1642 :
1643 13463374 : edge p;
1644 13463374 : edge_iterator ei;
1645 13463374 : basic_block b;
1646 212323708 : FOR_EACH_BB_FN (b, cfun)
1647 : {
1648 244970957 : if (EDGE_COUNT (b->preds) >= 2)
1649 : {
1650 46110623 : basic_block domsb = get_immediate_dominator (CDI_DOMINATORS, b);
1651 174190181 : FOR_EACH_EDGE (p, ei, b->preds)
1652 : {
1653 128079558 : basic_block runner = p->src;
1654 128079558 : if (runner == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1655 10416 : continue;
1656 :
1657 357445519 : while (runner != domsb)
1658 : {
1659 263054825 : if (!bitmap_set_bit (&frontiers[runner->index], b->index))
1660 : break;
1661 229376377 : runner = get_immediate_dominator (CDI_DOMINATORS, runner);
1662 : }
1663 : }
1664 : }
1665 : }
1666 :
1667 13463374 : timevar_pop (TV_DOM_FRONTIERS);
1668 13463374 : }
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 : If LIVE is not NULL, only the blocks in LIVE are added to the result
1675 : and have their dominance frontier followed. If LIVE is the set of
1676 : blocks where the variable is live on entry, the result is the
1677 : iterated dominance frontier restricted to LIVE.
1678 :
1679 : The resulting set of blocks are the potential sites where PHI nodes
1680 : are needed. The caller is responsible for freeing the memory
1681 : allocated for the return value. */
1682 :
1683 : bitmap
1684 25027824 : compute_idf (bitmap def_blocks, bitmap_head *dfs, bitmap live)
1685 : {
1686 25027824 : bitmap_iterator bi, bi2;
1687 25027824 : unsigned bb_index, i;
1688 25027824 : bitmap phi_insertion_points;
1689 :
1690 25027824 : phi_insertion_points = BITMAP_ALLOC (NULL);
1691 :
1692 : /* The initial workset is the DEF_BLOCKs, process that first,
1693 : seeding phi_insertion_points as the start of the worklist
1694 : for the iteration which then also serves as a visited set. */
1695 92732143 : EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi2)
1696 : {
1697 : /* Since the registration of NEW -> OLD name mappings is done
1698 : separately from the call to update_ssa, when updating the SSA
1699 : form, the basic blocks where new and/or old names are defined
1700 : may have disappeared by CFG cleanup calls. In this case,
1701 : we may pull a non-existing block from the work stack. */
1702 67704319 : gcc_checking_assert (bb_index
1703 : < (unsigned) last_basic_block_for_fn (cfun));
1704 :
1705 : /* The population counts of the dominance frontiers is low
1706 : compared to that of phi_insertion_points which approaches
1707 : the IDF and of work_set which is at most that of the IDF
1708 : as well. That makes iterating over the DFS bitmap preferential
1709 : to whole bitmap operations involving also phi_insertion_points. */
1710 136890928 : EXECUTE_IF_SET_IN_BITMAP (&dfs[bb_index], 0, i, bi)
1711 69186609 : if (!live || bitmap_bit_p (live, i))
1712 63644516 : bitmap_set_bit (phi_insertion_points, i);
1713 : }
1714 :
1715 : /* Seed the work set with the initial phi_insertion_points. */
1716 25027824 : auto_vec<int, 64> work_set (n_basic_blocks_for_fn (cfun));
1717 55990952 : EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, i, bi)
1718 30963128 : work_set.quick_push (i);
1719 :
1720 : /* Pop a block off the workset, add every block that appears in
1721 : the original block's DF that we have not already processed to
1722 : the workset. Iterate until the workset is empty. Blocks
1723 : which are added to the workset are potential sites for
1724 : PHI nodes. */
1725 69070527 : while (!work_set.is_empty ())
1726 : {
1727 44042703 : bb_index = work_set.pop ();
1728 0 : gcc_checking_assert (bb_index
1729 : < (unsigned) last_basic_block_for_fn (cfun));
1730 92308218 : EXECUTE_IF_SET_IN_BITMAP (&dfs[bb_index], 0, i, bi)
1731 1627349 : if ((!live || bitmap_bit_p (live, i))
1732 49056499 : && bitmap_set_bit (phi_insertion_points, i))
1733 13079575 : work_set.quick_push (i);
1734 : }
1735 :
1736 25027824 : return phi_insertion_points;
1737 25027824 : }
1738 :
1739 : /* Intersection and union of preds/succs for sbitmap based data flow
1740 : solvers. All four functions defined below take the same arguments:
1741 : B is the basic block to perform the operation for. DST is the
1742 : target sbitmap, i.e. the result. SRC is an sbitmap vector of size
1743 : last_basic_block so that it can be indexed with basic block indices.
1744 : DST may be (but does not have to be) SRC[B->index]. */
1745 :
1746 : /* Set the bitmap DST to the intersection of SRC of successors of
1747 : basic block B. */
1748 :
1749 : void
1750 10787702 : bitmap_intersection_of_succs (sbitmap dst, sbitmap *src, basic_block b)
1751 : {
1752 10787702 : unsigned int set_size = dst->size;
1753 10787702 : edge e;
1754 10787702 : unsigned ix;
1755 :
1756 10790889 : for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
1757 : {
1758 10709886 : e = EDGE_SUCC (b, ix);
1759 10709886 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1760 3187 : continue;
1761 :
1762 10706699 : bitmap_copy (dst, src[e->dest->index]);
1763 10706699 : break;
1764 : }
1765 :
1766 10787702 : if (e == 0)
1767 77816 : bitmap_ones (dst);
1768 : else
1769 17344880 : for (++ix; ix < EDGE_COUNT (b->succs); ix++)
1770 : {
1771 6634994 : unsigned int i;
1772 6634994 : SBITMAP_ELT_TYPE *p, *r;
1773 :
1774 6634994 : e = EDGE_SUCC (b, ix);
1775 6634994 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1776 0 : continue;
1777 :
1778 6634994 : p = src[e->dest->index]->elms;
1779 6634994 : r = dst->elms;
1780 25532892 : for (i = 0; i < set_size; i++)
1781 18897898 : *r++ &= *p++;
1782 : }
1783 10787702 : }
1784 :
1785 : /* Set the bitmap DST to the intersection of SRC of predecessors of
1786 : basic block B. */
1787 :
1788 : void
1789 57522210 : bitmap_intersection_of_preds (sbitmap dst, sbitmap *src, basic_block b)
1790 : {
1791 57522210 : unsigned int set_size = dst->size;
1792 57522210 : edge e;
1793 57522210 : unsigned ix;
1794 :
1795 57522210 : for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
1796 : {
1797 57522210 : e = EDGE_PRED (b, ix);
1798 57522210 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1799 0 : continue;
1800 :
1801 57522210 : bitmap_copy (dst, src[e->src->index]);
1802 57522210 : break;
1803 : }
1804 :
1805 57522210 : if (e == 0)
1806 0 : bitmap_ones (dst);
1807 : else
1808 143671943 : for (++ix; ix < EDGE_COUNT (b->preds); ix++)
1809 : {
1810 86149733 : unsigned int i;
1811 86149733 : SBITMAP_ELT_TYPE *p, *r;
1812 :
1813 86149733 : e = EDGE_PRED (b, ix);
1814 86149733 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1815 0 : continue;
1816 :
1817 86149733 : p = src[e->src->index]->elms;
1818 86149733 : r = dst->elms;
1819 758911713 : for (i = 0; i < set_size; i++)
1820 672761980 : *r++ &= *p++;
1821 : }
1822 57522210 : }
1823 :
1824 : /* Set the bitmap DST to the union of SRC of successors of
1825 : basic block B. */
1826 :
1827 : void
1828 0 : bitmap_union_of_succs (sbitmap dst, sbitmap *src, basic_block b)
1829 : {
1830 0 : unsigned int set_size = dst->size;
1831 0 : edge e;
1832 0 : unsigned ix;
1833 :
1834 0 : for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
1835 : {
1836 0 : e = EDGE_SUCC (b, ix);
1837 0 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1838 0 : continue;
1839 :
1840 0 : bitmap_copy (dst, src[e->dest->index]);
1841 0 : break;
1842 : }
1843 :
1844 0 : if (ix == EDGE_COUNT (b->succs))
1845 0 : bitmap_clear (dst);
1846 : else
1847 0 : for (ix++; ix < EDGE_COUNT (b->succs); ix++)
1848 : {
1849 0 : unsigned int i;
1850 0 : SBITMAP_ELT_TYPE *p, *r;
1851 :
1852 0 : e = EDGE_SUCC (b, ix);
1853 0 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1854 0 : continue;
1855 :
1856 0 : p = src[e->dest->index]->elms;
1857 0 : r = dst->elms;
1858 0 : for (i = 0; i < set_size; i++)
1859 0 : *r++ |= *p++;
1860 : }
1861 0 : }
1862 :
1863 : /* Set the bitmap DST to the union of SRC of predecessors of
1864 : basic block B. */
1865 :
1866 : void
1867 0 : bitmap_union_of_preds (sbitmap dst, sbitmap *src, basic_block b)
1868 : {
1869 0 : unsigned int set_size = dst->size;
1870 0 : edge e;
1871 0 : unsigned ix;
1872 :
1873 0 : for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
1874 : {
1875 0 : e = EDGE_PRED (b, ix);
1876 0 : if (e->src== ENTRY_BLOCK_PTR_FOR_FN (cfun))
1877 0 : continue;
1878 :
1879 0 : bitmap_copy (dst, src[e->src->index]);
1880 0 : break;
1881 : }
1882 :
1883 0 : if (ix == EDGE_COUNT (b->preds))
1884 0 : bitmap_clear (dst);
1885 : else
1886 0 : for (ix++; ix < EDGE_COUNT (b->preds); ix++)
1887 : {
1888 0 : unsigned int i;
1889 0 : SBITMAP_ELT_TYPE *p, *r;
1890 :
1891 0 : e = EDGE_PRED (b, ix);
1892 0 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1893 0 : continue;
1894 :
1895 0 : p = src[e->src->index]->elms;
1896 0 : r = dst->elms;
1897 0 : for (i = 0; i < set_size; i++)
1898 0 : *r++ |= *p++;
1899 : }
1900 0 : }
1901 :
1902 : /* Returns the list of basic blocks in the function in an order that guarantees
1903 : that if a block X has just a single predecessor Y, then Y is after X in the
1904 : ordering. */
1905 :
1906 : basic_block *
1907 7906785 : single_pred_before_succ_order (void)
1908 : {
1909 7906785 : basic_block x, y;
1910 7906785 : basic_block *order = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1911 7906785 : unsigned n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
1912 7906785 : unsigned np, i;
1913 7906785 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
1914 :
1915 : #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
1916 : #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
1917 :
1918 7906785 : bitmap_clear (visited);
1919 :
1920 7906785 : MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1921 74386242 : FOR_EACH_BB_FN (x, cfun)
1922 : {
1923 66479457 : if (VISITED_P (x))
1924 1982770 : continue;
1925 :
1926 : /* Walk the predecessors of x as long as they have precisely one
1927 : predecessor and add them to the list, so that they get stored
1928 : after x. */
1929 1982770 : for (y = x, np = 1;
1930 117135750 : single_pred_p (y) && !VISITED_P (single_pred (y));
1931 1982770 : y = single_pred (y))
1932 1982770 : np++;
1933 64496687 : for (y = x, i = n - np;
1934 117135750 : single_pred_p (y) && !VISITED_P (single_pred (y));
1935 1982770 : y = single_pred (y), i++)
1936 : {
1937 1982770 : order[i] = y;
1938 1982770 : MARK_VISITED (y);
1939 : }
1940 64496687 : order[i] = y;
1941 64496687 : MARK_VISITED (y);
1942 :
1943 64496687 : gcc_assert (i == n - 1);
1944 : n -= np;
1945 : }
1946 :
1947 7906785 : gcc_assert (n == 0);
1948 7906785 : return order;
1949 :
1950 : #undef MARK_VISITED
1951 : #undef VISITED_P
1952 7906785 : }
1953 :
1954 : /* Ignoring loop backedges, if BB has precisely one incoming edge then
1955 : return that edge. Otherwise return NULL.
1956 :
1957 : When IGNORE_NOT_EXECUTABLE is true, also ignore edges that are not marked
1958 : as executable. */
1959 :
1960 : edge
1961 62700386 : single_pred_edge_ignoring_loop_edges (basic_block bb,
1962 : bool ignore_not_executable)
1963 : {
1964 62700386 : edge retval = NULL;
1965 62700386 : edge e;
1966 62700386 : edge_iterator ei;
1967 :
1968 124613301 : FOR_EACH_EDGE (e, ei, bb->preds)
1969 : {
1970 : /* A loop back edge can be identified by the destination of
1971 : the edge dominating the source of the edge. */
1972 71949087 : if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1973 3361473 : continue;
1974 :
1975 : /* We can safely ignore edges that are not executable. */
1976 68587614 : if (ignore_not_executable
1977 26276883 : && (e->flags & EDGE_EXECUTABLE) == 0)
1978 124432 : continue;
1979 :
1980 : /* If we have already seen a non-loop edge, then we must have
1981 : multiple incoming non-loop edges and thus we return NULL. */
1982 68463182 : if (retval)
1983 : return NULL;
1984 :
1985 : /* This is the first non-loop incoming edge we have found. Record
1986 : it. */
1987 : retval = e;
1988 : }
1989 :
1990 : return retval;
1991 : }
|
