1 /* Calculate (post)dominators in slightly super-linear time.
2 Copyright (C) 2000-2022 Free Software Foundation, Inc.
3 Contributed by Michael Matz (matz@ifh.de).
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 /* This file implements the well known algorithm from Lengauer and Tarjan
22 to compute the dominators in a control flow graph. A basic block D is said
23 to dominate another block X, when all paths from the entry node of the CFG
24 to X go also over D. The dominance relation is a transitive reflexive
25 relation and its minimal transitive reduction is a tree, called the
26 dominator tree. So for each block X besides the entry block exists a
27 block I(X), called the immediate dominator of X, which is the parent of X
28 in the dominator tree.
29
30 The algorithm computes this dominator tree implicitly by computing for
31 each block its immediate dominator. We use tree balancing and path
32 compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
33 slowly growing functional inverse of the Ackerman function. */
34
35 #include "config.h"
36 #include "system.h"
37 #include "coretypes.h"
38 #include "backend.h"
39 #include "timevar.h"
40 #include "diagnostic-core.h"
41 #include "cfganal.h"
42 #include "et-forest.h"
43 #include "graphds.h"
44
45 /* We name our nodes with integers, beginning with 1. Zero is reserved for
46 'undefined' or 'end of list'. The name of each node is given by the dfs
47 number of the corresponding basic block. Please note, that we include the
48 artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
49 support multiple entry points. Its dfs number is of course 1. */
50
51 /* Type of Basic Block aka. TBB */
52 typedef unsigned int TBB;
53
54 namespace {
55
56 /* This class holds various arrays reflecting the (sub)structure of the
57 flowgraph. Most of them are of type TBB and are also indexed by TBB. */
58
59 class dom_info
60 {
61 public:
62 dom_info (function *, cdi_direction);
63 dom_info (vec <basic_block>, cdi_direction);
64 ~dom_info ();
65 void calc_dfs_tree ();
66 void calc_idoms ();
67
68 inline basic_block get_idom (basic_block);
69 private:
70 void calc_dfs_tree_nonrec (basic_block);
71 void compress (TBB);
72 void dom_init (void);
73 TBB eval (TBB);
74 void link_roots (TBB, TBB);
75
76 /* The parent of a node in the DFS tree. */
77 TBB *m_dfs_parent;
78 /* For a node x m_key[x] is roughly the node nearest to the root from which
79 exists a way to x only over nodes behind x. Such a node is also called
80 semidominator. */
81 TBB *m_key;
82 /* The value in m_path_min[x] is the node y on the path from x to the root of
83 the tree x is in with the smallest m_key[y]. */
84 TBB *m_path_min;
85 /* m_bucket[x] points to the first node of the set of nodes having x as
86 key. */
87 TBB *m_bucket;
88 /* And m_next_bucket[x] points to the next node. */
89 TBB *m_next_bucket;
90 /* After the algorithm is done, m_dom[x] contains the immediate dominator
91 of x. */
92 TBB *m_dom;
93
94 /* The following few fields implement the structures needed for disjoint
95 sets. */
96 /* m_set_chain[x] is the next node on the path from x to the representative
97 of the set containing x. If m_set_chain[x]==0 then x is a root. */
98 TBB *m_set_chain;
99 /* m_set_size[x] is the number of elements in the set named by x. */
100 unsigned int *m_set_size;
101 /* m_set_child[x] is used for balancing the tree representing a set. It can
102 be understood as the next sibling of x. */
103 TBB *m_set_child;
104
105 /* If b is the number of a basic block (BB->index), m_dfs_order[b] is the
106 number of that node in DFS order counted from 1. This is an index
107 into most of the other arrays in this structure. */
108 TBB *m_dfs_order;
109 /* Points to last element in m_dfs_order array. */
110 TBB *m_dfs_last;
111 /* If x is the DFS-index of a node which corresponds with a basic block,
112 m_dfs_to_bb[x] is that basic block. Note, that in our structure there are
113 more nodes that basic blocks, so only
114 m_dfs_to_bb[m_dfs_order[bb->index]]==bb is true for every basic block bb,
115 but not the opposite. */
116 basic_block *m_dfs_to_bb;
117
118 /* This is the next free DFS number when creating the DFS tree. */
119 unsigned int m_dfsnum;
120 /* The number of nodes in the DFS tree (==m_dfsnum-1). */
121 unsigned int m_nodes;
122
123 /* Blocks with bits set here have a fake edge to EXIT. These are used
124 to turn a DFS forest into a proper tree. */
125 bitmap m_fake_exit_edge;
126
127 /* Number of basic blocks in the function being compiled. */
128 unsigned m_n_basic_blocks;
129
130 /* True, if we are computing postdominators (rather than dominators). */
131 bool m_reverse;
132
133 /* Start block (the entry block for forward problem, exit block for backward
134 problem). */
135 basic_block m_start_block;
136 /* Ending block. */
137 basic_block m_end_block;
138 };
139
140 } // anonymous namespace
141
142 void debug_dominance_info (cdi_direction);
143 void debug_dominance_tree (cdi_direction, basic_block);
144
145 /* Allocate and zero-initialize NUM elements of type T (T must be a
146 POD-type). Note: after transition to C++11 or later,
147 `x = new_zero_array <T> (num);' can be replaced with
148 `x = new T[num] {};'. */
149
150 template<typename T>
new_zero_array(unsigned num)151 inline T *new_zero_array (unsigned num)
152 {
153 T *result = new T[num];
154 memset (result, 0, sizeof (T) * num);
155 return result;
156 }
157
158 /* Helper function for constructors to initialize a part of class members. */
159
160 void
dom_init(void)161 dom_info::dom_init (void)
162 {
163 unsigned num = m_n_basic_blocks;
164
165 m_dfs_parent = new_zero_array <TBB> (num);
166 m_dom = new_zero_array <TBB> (num);
167
168 m_path_min = new TBB[num];
169 m_key = new TBB[num];
170 m_set_size = new unsigned int[num];
171 for (unsigned i = 0; i < num; i++)
172 {
173 m_path_min[i] = m_key[i] = i;
174 m_set_size[i] = 1;
175 }
176
177 m_bucket = new_zero_array <TBB> (num);
178 m_next_bucket = new_zero_array <TBB> (num);
179
180 m_set_chain = new_zero_array <TBB> (num);
181 m_set_child = new_zero_array <TBB> (num);
182
183 m_dfs_to_bb = new_zero_array <basic_block> (num);
184
185 m_dfsnum = 1;
186 m_nodes = 0;
187 }
188
189 /* Allocate all needed memory in a pessimistic fashion (so we round up). */
190
dom_info(function * fn,cdi_direction dir)191 dom_info::dom_info (function *fn, cdi_direction dir)
192 {
193 m_n_basic_blocks = n_basic_blocks_for_fn (fn);
194
195 dom_init ();
196
197 unsigned last_bb_index = last_basic_block_for_fn (fn);
198 m_dfs_order = new_zero_array <TBB> (last_bb_index + 1);
199 m_dfs_last = &m_dfs_order[last_bb_index];
200
201 switch (dir)
202 {
203 case CDI_DOMINATORS:
204 m_reverse = false;
205 m_fake_exit_edge = NULL;
206 m_start_block = ENTRY_BLOCK_PTR_FOR_FN (fn);
207 m_end_block = EXIT_BLOCK_PTR_FOR_FN (fn);
208 break;
209 case CDI_POST_DOMINATORS:
210 m_reverse = true;
211 m_fake_exit_edge = BITMAP_ALLOC (NULL);
212 m_start_block = EXIT_BLOCK_PTR_FOR_FN (fn);
213 m_end_block = ENTRY_BLOCK_PTR_FOR_FN (fn);
214 break;
215 default:
216 gcc_unreachable ();
217 }
218 }
219
220 /* Constructor for reducible region REGION. */
221
dom_info(vec<basic_block> region,cdi_direction dir)222 dom_info::dom_info (vec<basic_block> region, cdi_direction dir)
223 {
224 m_n_basic_blocks = region.length ();
225 unsigned nm1 = m_n_basic_blocks - 1;
226
227 dom_init ();
228
229 /* Determine max basic block index in region. */
230 int max_index = region[0]->index;
231 for (unsigned i = 1; i <= nm1; i++)
232 if (region[i]->index > max_index)
233 max_index = region[i]->index;
234 max_index += 1; /* set index on the first bb out of region. */
235
236 m_dfs_order = new_zero_array <TBB> (max_index + 1);
237 m_dfs_last = &m_dfs_order[max_index];
238
239 m_fake_exit_edge = NULL; /* Assume that region is reducible. */
240
241 switch (dir)
242 {
243 case CDI_DOMINATORS:
244 m_reverse = false;
245 m_start_block = region[0];
246 m_end_block = region[nm1];
247 break;
248 case CDI_POST_DOMINATORS:
249 m_reverse = true;
250 m_start_block = region[nm1];
251 m_end_block = region[0];
252 break;
253 default:
254 gcc_unreachable ();
255 }
256 }
257
258 inline basic_block
get_idom(basic_block bb)259 dom_info::get_idom (basic_block bb)
260 {
261 TBB d = m_dom[m_dfs_order[bb->index]];
262 return m_dfs_to_bb[d];
263 }
264
265 /* Map dominance calculation type to array index used for various
266 dominance information arrays. This version is simple -- it will need
267 to be modified, obviously, if additional values are added to
268 cdi_direction. */
269
270 static inline unsigned int
dom_convert_dir_to_idx(cdi_direction dir)271 dom_convert_dir_to_idx (cdi_direction dir)
272 {
273 gcc_checking_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
274 return dir - 1;
275 }
276
277 /* Free all allocated memory in dom_info. */
278
~dom_info()279 dom_info::~dom_info ()
280 {
281 delete[] m_dfs_parent;
282 delete[] m_path_min;
283 delete[] m_key;
284 delete[] m_dom;
285 delete[] m_bucket;
286 delete[] m_next_bucket;
287 delete[] m_set_chain;
288 delete[] m_set_size;
289 delete[] m_set_child;
290 delete[] m_dfs_order;
291 delete[] m_dfs_to_bb;
292 BITMAP_FREE (m_fake_exit_edge);
293 }
294
295 /* The nonrecursive variant of creating a DFS tree. BB is the starting basic
296 block for this tree and m_reverse is true, if predecessors should be visited
297 instead of successors of a node. After this is done all nodes reachable
298 from BB were visited, have assigned their dfs number and are linked together
299 to form a tree. */
300
301 void
calc_dfs_tree_nonrec(basic_block bb)302 dom_info::calc_dfs_tree_nonrec (basic_block bb)
303 {
304 edge_iterator *stack = new edge_iterator[m_n_basic_blocks + 1];
305 int sp = 0;
306 unsigned d_i = dom_convert_dir_to_idx (m_reverse ? CDI_POST_DOMINATORS
307 : CDI_DOMINATORS);
308
309 /* Initialize the first edge. */
310 edge_iterator ei = m_reverse ? ei_start (bb->preds)
311 : ei_start (bb->succs);
312
313 /* When the stack is empty we break out of this loop. */
314 while (1)
315 {
316 basic_block bn;
317 edge_iterator einext;
318
319 /* This loop traverses edges e in depth first manner, and fills the
320 stack. */
321 while (!ei_end_p (ei))
322 {
323 edge e = ei_edge (ei);
324
325 /* Deduce from E the current and the next block (BB and BN), and the
326 next edge. */
327 if (m_reverse)
328 {
329 bn = e->src;
330
331 /* If the next node BN is either already visited or a border
332 block or out of region the current edge is useless, and simply
333 overwritten with the next edge out of the current node. */
334 if (bn == m_end_block || bn->dom[d_i] == NULL
335 || m_dfs_order[bn->index])
336 {
337 ei_next (&ei);
338 continue;
339 }
340 bb = e->dest;
341 einext = ei_start (bn->preds);
342 }
343 else
344 {
345 bn = e->dest;
346 if (bn == m_end_block || bn->dom[d_i] == NULL
347 || m_dfs_order[bn->index])
348 {
349 ei_next (&ei);
350 continue;
351 }
352 bb = e->src;
353 einext = ei_start (bn->succs);
354 }
355
356 gcc_assert (bn != m_start_block);
357
358 /* Fill the DFS tree info calculatable _before_ recursing. */
359 TBB my_i;
360 if (bb != m_start_block)
361 my_i = m_dfs_order[bb->index];
362 else
363 my_i = *m_dfs_last;
364 TBB child_i = m_dfs_order[bn->index] = m_dfsnum++;
365 m_dfs_to_bb[child_i] = bn;
366 m_dfs_parent[child_i] = my_i;
367
368 /* Save the current point in the CFG on the stack, and recurse. */
369 stack[sp++] = ei;
370 ei = einext;
371 }
372
373 if (!sp)
374 break;
375 ei = stack[--sp];
376
377 /* OK. The edge-list was exhausted, meaning normally we would
378 end the recursion. After returning from the recursive call,
379 there were (may be) other statements which were run after a
380 child node was completely considered by DFS. Here is the
381 point to do it in the non-recursive variant.
382 E.g. The block just completed is in e->dest for forward DFS,
383 the block not yet completed (the parent of the one above)
384 in e->src. This could be used e.g. for computing the number of
385 descendants or the tree depth. */
386 ei_next (&ei);
387 }
388 delete[] stack;
389 }
390
391 /* The main entry for calculating the DFS tree or forest. m_reverse is true,
392 if we are interested in the reverse flow graph. In that case the result is
393 not necessarily a tree but a forest, because there may be nodes from which
394 the EXIT_BLOCK is unreachable. */
395
396 void
calc_dfs_tree()397 dom_info::calc_dfs_tree ()
398 {
399 *m_dfs_last = m_dfsnum;
400 m_dfs_to_bb[m_dfsnum] = m_start_block;
401 m_dfsnum++;
402
403 calc_dfs_tree_nonrec (m_start_block);
404
405 if (m_fake_exit_edge)
406 {
407 /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
408 They are reverse-unreachable. In the dom-case we disallow such
409 nodes, but in post-dom we have to deal with them.
410
411 There are two situations in which this occurs. First, noreturn
412 functions. Second, infinite loops. In the first case we need to
413 pretend that there is an edge to the exit block. In the second
414 case, we wind up with a forest. We need to process all noreturn
415 blocks before we know if we've got any infinite loops. */
416
417 basic_block b;
418 bool saw_unconnected = false;
419
420 FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
421 {
422 if (EDGE_COUNT (b->succs) > 0)
423 {
424 if (m_dfs_order[b->index] == 0)
425 saw_unconnected = true;
426 continue;
427 }
428 bitmap_set_bit (m_fake_exit_edge, b->index);
429 m_dfs_order[b->index] = m_dfsnum;
430 m_dfs_to_bb[m_dfsnum] = b;
431 m_dfs_parent[m_dfsnum] = *m_dfs_last;
432 m_dfsnum++;
433 calc_dfs_tree_nonrec (b);
434 }
435
436 if (saw_unconnected)
437 {
438 FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
439 {
440 if (m_dfs_order[b->index])
441 continue;
442 basic_block b2 = dfs_find_deadend (b);
443 gcc_checking_assert (m_dfs_order[b2->index] == 0);
444 bitmap_set_bit (m_fake_exit_edge, b2->index);
445 m_dfs_order[b2->index] = m_dfsnum;
446 m_dfs_to_bb[m_dfsnum] = b2;
447 m_dfs_parent[m_dfsnum] = *m_dfs_last;
448 m_dfsnum++;
449 calc_dfs_tree_nonrec (b2);
450 gcc_checking_assert (m_dfs_order[b->index]);
451 }
452 }
453 }
454
455 m_nodes = m_dfsnum - 1;
456
457 /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
458 gcc_assert (m_nodes == (unsigned int) m_n_basic_blocks - 1);
459 }
460
461 /* Compress the path from V to the root of its set and update path_min at the
462 same time. After compress(di, V) set_chain[V] is the root of the set V is
463 in and path_min[V] is the node with the smallest key[] value on the path
464 from V to that root. */
465
466 void
compress(TBB v)467 dom_info::compress (TBB v)
468 {
469 /* Btw. It's not worth to unrecurse compress() as the depth is usually not
470 greater than 5 even for huge graphs (I've not seen call depth > 4).
471 Also performance wise compress() ranges _far_ behind eval(). */
472 TBB parent = m_set_chain[v];
473 if (m_set_chain[parent])
474 {
475 compress (parent);
476 if (m_key[m_path_min[parent]] < m_key[m_path_min[v]])
477 m_path_min[v] = m_path_min[parent];
478 m_set_chain[v] = m_set_chain[parent];
479 }
480 }
481
482 /* Compress the path from V to the set root of V if needed (when the root has
483 changed since the last call). Returns the node with the smallest key[]
484 value on the path from V to the root. */
485
486 inline TBB
eval(TBB v)487 dom_info::eval (TBB v)
488 {
489 /* The representative of the set V is in, also called root (as the set
490 representation is a tree). */
491 TBB rep = m_set_chain[v];
492
493 /* V itself is the root. */
494 if (!rep)
495 return m_path_min[v];
496
497 /* Compress only if necessary. */
498 if (m_set_chain[rep])
499 {
500 compress (v);
501 rep = m_set_chain[v];
502 }
503
504 if (m_key[m_path_min[rep]] >= m_key[m_path_min[v]])
505 return m_path_min[v];
506 else
507 return m_path_min[rep];
508 }
509
510 /* This essentially merges the two sets of V and W, giving a single set with
511 the new root V. The internal representation of these disjoint sets is a
512 balanced tree. Currently link(V,W) is only used with V being the parent
513 of W. */
514
515 void
link_roots(TBB v,TBB w)516 dom_info::link_roots (TBB v, TBB w)
517 {
518 TBB s = w;
519
520 /* Rebalance the tree. */
521 while (m_key[m_path_min[w]] < m_key[m_path_min[m_set_child[s]]])
522 {
523 if (m_set_size[s] + m_set_size[m_set_child[m_set_child[s]]]
524 >= 2 * m_set_size[m_set_child[s]])
525 {
526 m_set_chain[m_set_child[s]] = s;
527 m_set_child[s] = m_set_child[m_set_child[s]];
528 }
529 else
530 {
531 m_set_size[m_set_child[s]] = m_set_size[s];
532 s = m_set_chain[s] = m_set_child[s];
533 }
534 }
535
536 m_path_min[s] = m_path_min[w];
537 m_set_size[v] += m_set_size[w];
538 if (m_set_size[v] < 2 * m_set_size[w])
539 std::swap (m_set_child[v], s);
540
541 /* Merge all subtrees. */
542 while (s)
543 {
544 m_set_chain[s] = v;
545 s = m_set_child[s];
546 }
547 }
548
549 /* This calculates the immediate dominators (or post-dominators). THIS is our
550 working structure and should hold the DFS forest.
551 On return the immediate dominator to node V is in m_dom[V]. */
552
553 void
calc_idoms()554 dom_info::calc_idoms ()
555 {
556 /* Go backwards in DFS order, to first look at the leafs. */
557 for (TBB v = m_nodes; v > 1; v--)
558 {
559 basic_block bb = m_dfs_to_bb[v];
560 edge e;
561
562 TBB par = m_dfs_parent[v];
563 TBB k = v;
564
565 edge_iterator ei = m_reverse ? ei_start (bb->succs)
566 : ei_start (bb->preds);
567 edge_iterator einext;
568
569 if (m_fake_exit_edge)
570 {
571 /* If this block has a fake edge to exit, process that first. */
572 if (bitmap_bit_p (m_fake_exit_edge, bb->index))
573 {
574 einext = ei;
575 einext.index = 0;
576 goto do_fake_exit_edge;
577 }
578 }
579
580 /* Search all direct predecessors for the smallest node with a path
581 to them. That way we have the smallest node with also a path to
582 us only over nodes behind us. In effect we search for our
583 semidominator. */
584 while (!ei_end_p (ei))
585 {
586 basic_block b;
587 TBB k1;
588
589 e = ei_edge (ei);
590 b = m_reverse ? e->dest : e->src;
591 einext = ei;
592 ei_next (&einext);
593
594 if (b == m_start_block)
595 {
596 do_fake_exit_edge:
597 k1 = *m_dfs_last;
598 }
599 else
600 k1 = m_dfs_order[b->index];
601
602 /* Call eval() only if really needed. If k1 is above V in DFS tree,
603 then we know, that eval(k1) == k1 and key[k1] == k1. */
604 if (k1 > v)
605 k1 = m_key[eval (k1)];
606 if (k1 < k)
607 k = k1;
608
609 ei = einext;
610 }
611
612 m_key[v] = k;
613 link_roots (par, v);
614 m_next_bucket[v] = m_bucket[k];
615 m_bucket[k] = v;
616
617 /* Transform semidominators into dominators. */
618 for (TBB w = m_bucket[par]; w; w = m_next_bucket[w])
619 {
620 k = eval (w);
621 if (m_key[k] < m_key[w])
622 m_dom[w] = k;
623 else
624 m_dom[w] = par;
625 }
626 /* We don't need to cleanup next_bucket[]. */
627 m_bucket[par] = 0;
628 }
629
630 /* Explicitly define the dominators. */
631 m_dom[1] = 0;
632 for (TBB v = 2; v <= m_nodes; v++)
633 if (m_dom[v] != m_key[v])
634 m_dom[v] = m_dom[m_dom[v]];
635 }
636
637 /* Assign dfs numbers starting from NUM to NODE and its sons. */
638
639 static void
assign_dfs_numbers(struct et_node * node,int * num)640 assign_dfs_numbers (struct et_node *node, int *num)
641 {
642 et_node *n = node;
643 while (1)
644 {
645 n->dfs_num_in = (*num)++;
646 if (n->son)
647 n = n->son;
648 else
649 {
650 while (!n->right || n->right == n->father->son)
651 {
652 n->dfs_num_out = (*num)++;
653 if (n == node)
654 return;
655 n = n->father;
656 }
657 n->dfs_num_out = (*num)++;
658 n = n->right;
659 }
660 }
661 }
662
663 /* Compute the data necessary for fast resolving of dominator queries in a
664 static dominator tree. */
665
666 static void
compute_dom_fast_query(enum cdi_direction dir)667 compute_dom_fast_query (enum cdi_direction dir)
668 {
669 int num = 0;
670 basic_block bb;
671 unsigned int dir_index = dom_convert_dir_to_idx (dir);
672
673 gcc_checking_assert (dom_info_available_p (dir));
674
675 if (dom_computed[dir_index] == DOM_OK)
676 return;
677
678 FOR_ALL_BB_FN (bb, cfun)
679 {
680 if (!bb->dom[dir_index]->father)
681 assign_dfs_numbers (bb->dom[dir_index], &num);
682 }
683
684 dom_computed[dir_index] = DOM_OK;
685 }
686
687 /* Analogous to the previous function but compute the data for reducible
688 region REGION. */
689
690 static void
compute_dom_fast_query_in_region(enum cdi_direction dir,vec<basic_block> region)691 compute_dom_fast_query_in_region (enum cdi_direction dir,
692 vec<basic_block> region)
693 {
694 int num = 0;
695 basic_block bb;
696 unsigned int dir_index = dom_convert_dir_to_idx (dir);
697
698 gcc_checking_assert (dom_info_available_p (dir));
699
700 if (dom_computed[dir_index] == DOM_OK)
701 return;
702
703 /* Assign dfs numbers for region nodes except for entry and exit nodes. */
704 for (unsigned int i = 1; i < region.length () - 1; i++)
705 {
706 bb = region[i];
707 if (!bb->dom[dir_index]->father)
708 assign_dfs_numbers (bb->dom[dir_index], &num);
709 }
710
711 dom_computed[dir_index] = DOM_OK;
712 }
713
714 /* The main entry point into this module. DIR is set depending on whether
715 we want to compute dominators or postdominators. */
716
717 void
calculate_dominance_info(cdi_direction dir)718 calculate_dominance_info (cdi_direction dir)
719 {
720 unsigned int dir_index = dom_convert_dir_to_idx (dir);
721
722 if (dom_computed[dir_index] == DOM_OK)
723 {
724 checking_verify_dominators (dir);
725 return;
726 }
727
728 timevar_push (TV_DOMINANCE);
729 if (!dom_info_available_p (dir))
730 {
731 gcc_assert (!n_bbs_in_dom_tree[dir_index]);
732
733 basic_block b;
734 FOR_ALL_BB_FN (b, cfun)
735 {
736 b->dom[dir_index] = et_new_tree (b);
737 }
738 n_bbs_in_dom_tree[dir_index] = n_basic_blocks_for_fn (cfun);
739
740 dom_info di (cfun, dir);
741 di.calc_dfs_tree ();
742 di.calc_idoms ();
743
744 FOR_EACH_BB_FN (b, cfun)
745 {
746 if (basic_block d = di.get_idom (b))
747 et_set_father (b->dom[dir_index], d->dom[dir_index]);
748 }
749
750 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
751 }
752 else
753 checking_verify_dominators (dir);
754
755 compute_dom_fast_query (dir);
756
757 timevar_pop (TV_DOMINANCE);
758 }
759
760 /* Analogous to the previous function but compute dominance info for regions
761 which are single entry, multiple exit regions for CDI_DOMINATORs and
762 multiple entry, single exit regions for CDI_POST_DOMINATORs. */
763
764 void
calculate_dominance_info_for_region(cdi_direction dir,vec<basic_block> region)765 calculate_dominance_info_for_region (cdi_direction dir,
766 vec<basic_block> region)
767 {
768 unsigned int dir_index = dom_convert_dir_to_idx (dir);
769 basic_block bb;
770 unsigned int i;
771
772 if (dom_computed[dir_index] == DOM_OK)
773 return;
774
775 timevar_push (TV_DOMINANCE);
776 /* Assume that dom info is not partially computed. */
777 gcc_assert (!dom_info_available_p (dir));
778
779 FOR_EACH_VEC_ELT (region, i, bb)
780 {
781 bb->dom[dir_index] = et_new_tree (bb);
782 }
783 dom_info di (region, dir);
784 di.calc_dfs_tree ();
785 di.calc_idoms ();
786
787 FOR_EACH_VEC_ELT (region, i, bb)
788 if (basic_block d = di.get_idom (bb))
789 et_set_father (bb->dom[dir_index], d->dom[dir_index]);
790
791 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
792 compute_dom_fast_query_in_region (dir, region);
793
794 timevar_pop (TV_DOMINANCE);
795 }
796
797 /* Free dominance information for direction DIR. */
798 void
free_dominance_info(function * fn,enum cdi_direction dir)799 free_dominance_info (function *fn, enum cdi_direction dir)
800 {
801 basic_block bb;
802 unsigned int dir_index = dom_convert_dir_to_idx (dir);
803
804 if (!dom_info_available_p (fn, dir))
805 return;
806
807 FOR_ALL_BB_FN (bb, fn)
808 {
809 et_free_tree_force (bb->dom[dir_index]);
810 bb->dom[dir_index] = NULL;
811 }
812 et_free_pools ();
813
814 fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
815
816 fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
817 }
818
819 void
free_dominance_info(enum cdi_direction dir)820 free_dominance_info (enum cdi_direction dir)
821 {
822 free_dominance_info (cfun, dir);
823 }
824
825 /* Free dominance information for direction DIR in region REGION. */
826
827 void
free_dominance_info_for_region(function * fn,enum cdi_direction dir,vec<basic_block> region)828 free_dominance_info_for_region (function *fn,
829 enum cdi_direction dir,
830 vec<basic_block> region)
831 {
832 basic_block bb;
833 unsigned int i;
834 unsigned int dir_index = dom_convert_dir_to_idx (dir);
835
836 if (!dom_info_available_p (dir))
837 return;
838
839 FOR_EACH_VEC_ELT (region, i, bb)
840 {
841 et_free_tree_force (bb->dom[dir_index]);
842 bb->dom[dir_index] = NULL;
843 }
844 et_free_pools ();
845
846 fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
847
848 fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
849 }
850
851 /* Return the immediate dominator of basic block BB. */
852 basic_block
get_immediate_dominator(enum cdi_direction dir,basic_block bb)853 get_immediate_dominator (enum cdi_direction dir, basic_block bb)
854 {
855 unsigned int dir_index = dom_convert_dir_to_idx (dir);
856 struct et_node *node = bb->dom[dir_index];
857
858 gcc_checking_assert (dom_computed[dir_index]);
859
860 if (!node->father)
861 return NULL;
862
863 return (basic_block) node->father->data;
864 }
865
866 /* Set the immediate dominator of the block possibly removing
867 existing edge. NULL can be used to remove any edge. */
868 void
set_immediate_dominator(enum cdi_direction dir,basic_block bb,basic_block dominated_by)869 set_immediate_dominator (enum cdi_direction dir, basic_block bb,
870 basic_block dominated_by)
871 {
872 unsigned int dir_index = dom_convert_dir_to_idx (dir);
873 struct et_node *node = bb->dom[dir_index];
874
875 gcc_checking_assert (dom_computed[dir_index]);
876
877 if (node->father)
878 {
879 if (node->father->data == dominated_by)
880 return;
881 et_split (node);
882 }
883
884 if (dominated_by)
885 et_set_father (node, dominated_by->dom[dir_index]);
886
887 if (dom_computed[dir_index] == DOM_OK)
888 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
889 }
890
891 /* Returns the list of basic blocks immediately dominated by BB, in the
892 direction DIR. */
893 auto_vec<basic_block>
get_dominated_by(enum cdi_direction dir,basic_block bb)894 get_dominated_by (enum cdi_direction dir, basic_block bb)
895 {
896 unsigned int dir_index = dom_convert_dir_to_idx (dir);
897 struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
898 auto_vec<basic_block> bbs;
899
900 gcc_checking_assert (dom_computed[dir_index]);
901
902 if (!son)
903 return bbs;
904
905 bbs.safe_push ((basic_block) son->data);
906 for (ason = son->right; ason != son; ason = ason->right)
907 bbs.safe_push ((basic_block) ason->data);
908
909 return bbs;
910 }
911
912 /* Returns the list of basic blocks that are immediately dominated (in
913 direction DIR) by some block between N_REGION ones stored in REGION,
914 except for blocks in the REGION itself. */
915
916 auto_vec<basic_block>
get_dominated_by_region(enum cdi_direction dir,basic_block * region,unsigned n_region)917 get_dominated_by_region (enum cdi_direction dir, basic_block *region,
918 unsigned n_region)
919 {
920 unsigned i;
921 basic_block dom;
922 auto_vec<basic_block> doms;
923
924 for (i = 0; i < n_region; i++)
925 region[i]->flags |= BB_DUPLICATED;
926 for (i = 0; i < n_region; i++)
927 for (dom = first_dom_son (dir, region[i]);
928 dom;
929 dom = next_dom_son (dir, dom))
930 if (!(dom->flags & BB_DUPLICATED))
931 doms.safe_push (dom);
932 for (i = 0; i < n_region; i++)
933 region[i]->flags &= ~BB_DUPLICATED;
934
935 return doms;
936 }
937
938 /* Returns the list of basic blocks including BB dominated by BB, in the
939 direction DIR up to DEPTH in the dominator tree. The DEPTH of zero will
940 produce a vector containing all dominated blocks. The vector will be sorted
941 in preorder. */
942
943 auto_vec<basic_block>
get_dominated_to_depth(enum cdi_direction dir,basic_block bb,int depth)944 get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
945 {
946 auto_vec<basic_block> bbs;
947 unsigned i;
948 unsigned next_level_start;
949
950 i = 0;
951 bbs.safe_push (bb);
952 next_level_start = 1; /* = bbs.length (); */
953
954 do
955 {
956 basic_block son;
957
958 bb = bbs[i++];
959 for (son = first_dom_son (dir, bb);
960 son;
961 son = next_dom_son (dir, son))
962 bbs.safe_push (son);
963
964 if (i == next_level_start && --depth)
965 next_level_start = bbs.length ();
966 }
967 while (i < next_level_start);
968
969 return bbs;
970 }
971
972 /* Returns the list of basic blocks including BB dominated by BB, in the
973 direction DIR. The vector will be sorted in preorder. */
974
975 auto_vec<basic_block>
get_all_dominated_blocks(enum cdi_direction dir,basic_block bb)976 get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
977 {
978 return get_dominated_to_depth (dir, bb, 0);
979 }
980
981 /* Redirect all edges pointing to BB to TO. */
982 void
redirect_immediate_dominators(enum cdi_direction dir,basic_block bb,basic_block to)983 redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
984 basic_block to)
985 {
986 unsigned int dir_index = dom_convert_dir_to_idx (dir);
987 struct et_node *bb_node, *to_node, *son;
988
989 bb_node = bb->dom[dir_index];
990 to_node = to->dom[dir_index];
991
992 gcc_checking_assert (dom_computed[dir_index]);
993
994 if (!bb_node->son)
995 return;
996
997 while (bb_node->son)
998 {
999 son = bb_node->son;
1000
1001 et_split (son);
1002 et_set_father (son, to_node);
1003 }
1004
1005 if (dom_computed[dir_index] == DOM_OK)
1006 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1007 }
1008
1009 /* Find first basic block in the tree dominating both BB1 and BB2. */
1010 basic_block
nearest_common_dominator(enum cdi_direction dir,basic_block bb1,basic_block bb2)1011 nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
1012 {
1013 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1014
1015 gcc_checking_assert (dom_computed[dir_index]);
1016
1017 if (!bb1)
1018 return bb2;
1019 if (!bb2)
1020 return bb1;
1021
1022 return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
1023 }
1024
1025
1026 /* Find the nearest common dominator for the basic blocks in BLOCKS,
1027 using dominance direction DIR. */
1028
1029 basic_block
nearest_common_dominator_for_set(enum cdi_direction dir,bitmap blocks)1030 nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
1031 {
1032 unsigned i, first;
1033 bitmap_iterator bi;
1034 basic_block dom;
1035
1036 first = bitmap_first_set_bit (blocks);
1037 dom = BASIC_BLOCK_FOR_FN (cfun, first);
1038 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
1039 if (dom != BASIC_BLOCK_FOR_FN (cfun, i))
1040 dom = nearest_common_dominator (dir, dom, BASIC_BLOCK_FOR_FN (cfun, i));
1041
1042 return dom;
1043 }
1044
1045 /* Given a dominator tree, we can determine whether one thing
1046 dominates another in constant time by using two DFS numbers:
1047
1048 1. The number for when we visit a node on the way down the tree
1049 2. The number for when we visit a node on the way back up the tree
1050
1051 You can view these as bounds for the range of dfs numbers the
1052 nodes in the subtree of the dominator tree rooted at that node
1053 will contain.
1054
1055 The dominator tree is always a simple acyclic tree, so there are
1056 only three possible relations two nodes in the dominator tree have
1057 to each other:
1058
1059 1. Node A is above Node B (and thus, Node A dominates node B)
1060
1061 A
1062 |
1063 C
1064 / \
1065 B D
1066
1067
1068 In the above case, DFS_Number_In of A will be <= DFS_Number_In of
1069 B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is
1070 because we must hit A in the dominator tree *before* B on the walk
1071 down, and we will hit A *after* B on the walk back up
1072
1073 2. Node A is below node B (and thus, node B dominates node A)
1074
1075
1076 B
1077 |
1078 A
1079 / \
1080 C D
1081
1082 In the above case, DFS_Number_In of A will be >= DFS_Number_In of
1083 B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
1084
1085 This is because we must hit A in the dominator tree *after* B on
1086 the walk down, and we will hit A *before* B on the walk back up
1087
1088 3. Node A and B are siblings (and thus, neither dominates the other)
1089
1090 C
1091 |
1092 D
1093 / \
1094 A B
1095
1096 In the above case, DFS_Number_In of A will *always* be <=
1097 DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
1098 DFS_Number_Out of B. This is because we will always finish the dfs
1099 walk of one of the subtrees before the other, and thus, the dfs
1100 numbers for one subtree can't intersect with the range of dfs
1101 numbers for the other subtree. If you swap A and B's position in
1102 the dominator tree, the comparison changes direction, but the point
1103 is that both comparisons will always go the same way if there is no
1104 dominance relationship.
1105
1106 Thus, it is sufficient to write
1107
1108 A_Dominates_B (node A, node B)
1109 {
1110 return DFS_Number_In(A) <= DFS_Number_In(B)
1111 && DFS_Number_Out (A) >= DFS_Number_Out(B);
1112 }
1113
1114 A_Dominated_by_B (node A, node B)
1115 {
1116 return DFS_Number_In(A) >= DFS_Number_In(B)
1117 && DFS_Number_Out (A) <= DFS_Number_Out(B);
1118 } */
1119
1120 /* Return TRUE in case BB1 is dominated by BB2. */
1121 bool
dominated_by_p(enum cdi_direction dir,const_basic_block bb1,const_basic_block bb2)1122 dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
1123 {
1124 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1125 struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
1126
1127 gcc_checking_assert (dom_computed[dir_index]);
1128
1129 if (dom_computed[dir_index] == DOM_OK)
1130 return (n1->dfs_num_in >= n2->dfs_num_in
1131 && n1->dfs_num_out <= n2->dfs_num_out);
1132
1133 return et_below (n1, n2);
1134 }
1135
1136 /* Returns the entry dfs number for basic block BB, in the direction DIR. */
1137
1138 unsigned
bb_dom_dfs_in(enum cdi_direction dir,basic_block bb)1139 bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
1140 {
1141 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1142 struct et_node *n = bb->dom[dir_index];
1143
1144 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1145 return n->dfs_num_in;
1146 }
1147
1148 /* Returns the exit dfs number for basic block BB, in the direction DIR. */
1149
1150 unsigned
bb_dom_dfs_out(enum cdi_direction dir,basic_block bb)1151 bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
1152 {
1153 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1154 struct et_node *n = bb->dom[dir_index];
1155
1156 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1157 return n->dfs_num_out;
1158 }
1159
1160 /* Verify invariants of dominator structure. */
1161 DEBUG_FUNCTION void
verify_dominators(cdi_direction dir)1162 verify_dominators (cdi_direction dir)
1163 {
1164 gcc_assert (dom_info_available_p (dir));
1165
1166 dom_info di (cfun, dir);
1167 di.calc_dfs_tree ();
1168 di.calc_idoms ();
1169
1170 bool err = false;
1171 basic_block bb;
1172 FOR_EACH_BB_FN (bb, cfun)
1173 {
1174 basic_block imm_bb = get_immediate_dominator (dir, bb);
1175 if (!imm_bb)
1176 {
1177 error ("dominator of %d status unknown", bb->index);
1178 err = true;
1179 continue;
1180 }
1181
1182 basic_block imm_bb_correct = di.get_idom (bb);
1183 if (imm_bb != imm_bb_correct)
1184 {
1185 error ("dominator of %d should be %d, not %d",
1186 bb->index, imm_bb_correct->index, imm_bb->index);
1187 err = true;
1188 }
1189 }
1190
1191 gcc_assert (!err);
1192 }
1193
1194 /* Determine immediate dominator (or postdominator, according to DIR) of BB,
1195 assuming that dominators of other blocks are correct. We also use it to
1196 recompute the dominators in a restricted area, by iterating it until it
1197 reaches a fixed point. */
1198
1199 basic_block
recompute_dominator(enum cdi_direction dir,basic_block bb)1200 recompute_dominator (enum cdi_direction dir, basic_block bb)
1201 {
1202 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1203 basic_block dom_bb = NULL;
1204 edge e;
1205 edge_iterator ei;
1206
1207 gcc_checking_assert (dom_computed[dir_index]);
1208
1209 if (dir == CDI_DOMINATORS)
1210 {
1211 FOR_EACH_EDGE (e, ei, bb->preds)
1212 {
1213 if (!dominated_by_p (dir, e->src, bb))
1214 dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
1215 }
1216 }
1217 else
1218 {
1219 FOR_EACH_EDGE (e, ei, bb->succs)
1220 {
1221 if (!dominated_by_p (dir, e->dest, bb))
1222 dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
1223 }
1224 }
1225
1226 return dom_bb;
1227 }
1228
1229 /* Use simple heuristics (see iterate_fix_dominators) to determine dominators
1230 of BBS. We assume that all the immediate dominators except for those of the
1231 blocks in BBS are correct. If CONSERVATIVE is true, we also assume that the
1232 currently recorded immediate dominators of blocks in BBS really dominate the
1233 blocks. The basic blocks for that we determine the dominator are removed
1234 from BBS. */
1235
1236 static void
prune_bbs_to_update_dominators(vec<basic_block> & bbs,bool conservative)1237 prune_bbs_to_update_dominators (vec<basic_block> &bbs,
1238 bool conservative)
1239 {
1240 unsigned i;
1241 bool single;
1242 basic_block bb, dom = NULL;
1243 edge_iterator ei;
1244 edge e;
1245
1246 for (i = 0; bbs.iterate (i, &bb);)
1247 {
1248 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1249 goto succeed;
1250
1251 if (single_pred_p (bb))
1252 {
1253 set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
1254 goto succeed;
1255 }
1256
1257 if (!conservative)
1258 goto fail;
1259
1260 single = true;
1261 dom = NULL;
1262 FOR_EACH_EDGE (e, ei, bb->preds)
1263 {
1264 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1265 continue;
1266
1267 if (!dom)
1268 dom = e->src;
1269 else
1270 {
1271 single = false;
1272 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1273 }
1274 }
1275
1276 gcc_assert (dom != NULL);
1277 if (single
1278 || find_edge (dom, bb))
1279 {
1280 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1281 goto succeed;
1282 }
1283
1284 fail:
1285 i++;
1286 continue;
1287
1288 succeed:
1289 bbs.unordered_remove (i);
1290 }
1291 }
1292
1293 /* Returns root of the dominance tree in the direction DIR that contains
1294 BB. */
1295
1296 static basic_block
root_of_dom_tree(enum cdi_direction dir,basic_block bb)1297 root_of_dom_tree (enum cdi_direction dir, basic_block bb)
1298 {
1299 return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
1300 }
1301
1302 /* See the comment in iterate_fix_dominators. Finds the immediate dominators
1303 for the sons of Y, found using the SON and BROTHER arrays representing
1304 the dominance tree of graph G. BBS maps the vertices of G to the basic
1305 blocks. */
1306
1307 static void
determine_dominators_for_sons(struct graph * g,vec<basic_block> bbs,int y,int * son,int * brother)1308 determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
1309 int y, int *son, int *brother)
1310 {
1311 bitmap gprime;
1312 int i, a, nc;
1313 vec<int> *sccs;
1314 basic_block bb, dom, ybb;
1315 unsigned si;
1316 edge e;
1317 edge_iterator ei;
1318
1319 if (son[y] == -1)
1320 return;
1321 if (y == (int) bbs.length ())
1322 ybb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1323 else
1324 ybb = bbs[y];
1325
1326 if (brother[son[y]] == -1)
1327 {
1328 /* Handle the common case Y has just one son specially. */
1329 bb = bbs[son[y]];
1330 set_immediate_dominator (CDI_DOMINATORS, bb,
1331 recompute_dominator (CDI_DOMINATORS, bb));
1332 identify_vertices (g, y, son[y]);
1333 return;
1334 }
1335
1336 gprime = BITMAP_ALLOC (NULL);
1337 for (a = son[y]; a != -1; a = brother[a])
1338 bitmap_set_bit (gprime, a);
1339
1340 nc = graphds_scc (g, gprime);
1341 BITMAP_FREE (gprime);
1342
1343 /* ??? Needed to work around the pre-processor confusion with
1344 using a multi-argument template type as macro argument. */
1345 typedef vec<int> vec_int_heap;
1346 sccs = XCNEWVEC (vec_int_heap, nc);
1347 for (a = son[y]; a != -1; a = brother[a])
1348 sccs[g->vertices[a].component].safe_push (a);
1349
1350 for (i = nc - 1; i >= 0; i--)
1351 {
1352 dom = NULL;
1353 FOR_EACH_VEC_ELT (sccs[i], si, a)
1354 {
1355 bb = bbs[a];
1356 FOR_EACH_EDGE (e, ei, bb->preds)
1357 {
1358 if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
1359 continue;
1360
1361 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1362 }
1363 }
1364
1365 gcc_assert (dom != NULL);
1366 FOR_EACH_VEC_ELT (sccs[i], si, a)
1367 {
1368 bb = bbs[a];
1369 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1370 }
1371 }
1372
1373 for (i = 0; i < nc; i++)
1374 sccs[i].release ();
1375 free (sccs);
1376
1377 for (a = son[y]; a != -1; a = brother[a])
1378 identify_vertices (g, y, a);
1379 }
1380
1381 /* Recompute dominance information for basic blocks in the set BBS. The
1382 function assumes that the immediate dominators of all the other blocks
1383 in CFG are correct, and that there are no unreachable blocks.
1384
1385 If CONSERVATIVE is true, we additionally assume that all the ancestors of
1386 a block of BBS in the current dominance tree dominate it. */
1387
1388 void
iterate_fix_dominators(enum cdi_direction dir,vec<basic_block> & bbs,bool conservative)1389 iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> &bbs,
1390 bool conservative)
1391 {
1392 unsigned i;
1393 basic_block bb, dom;
1394 struct graph *g;
1395 int n, y;
1396 size_t dom_i;
1397 edge e;
1398 edge_iterator ei;
1399 int *parent, *son, *brother;
1400 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1401
1402 /* We only support updating dominators. There are some problems with
1403 updating postdominators (need to add fake edges from infinite loops
1404 and noreturn functions), and since we do not currently use
1405 iterate_fix_dominators for postdominators, any attempt to handle these
1406 problems would be unused, untested, and almost surely buggy. We keep
1407 the DIR argument for consistency with the rest of the dominator analysis
1408 interface. */
1409 gcc_checking_assert (dir == CDI_DOMINATORS && dom_computed[dir_index]);
1410
1411 /* The algorithm we use takes inspiration from the following papers, although
1412 the details are quite different from any of them:
1413
1414 [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
1415 Dominator Tree of a Reducible Flowgraph
1416 [2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
1417 dominator trees
1418 [3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
1419 Algorithm
1420
1421 First, we use the following heuristics to decrease the size of the BBS
1422 set:
1423 a) if BB has a single predecessor, then its immediate dominator is this
1424 predecessor
1425 additionally, if CONSERVATIVE is true:
1426 b) if all the predecessors of BB except for one (X) are dominated by BB,
1427 then X is the immediate dominator of BB
1428 c) if the nearest common ancestor of the predecessors of BB is X and
1429 X -> BB is an edge in CFG, then X is the immediate dominator of BB
1430
1431 Then, we need to establish the dominance relation among the basic blocks
1432 in BBS. We split the dominance tree by removing the immediate dominator
1433 edges from BBS, creating a forest F. We form a graph G whose vertices
1434 are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
1435 X' -> Y in CFG such that X' belongs to the tree of the dominance forest
1436 whose root is X. We then determine dominance tree of G. Note that
1437 for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
1438 In this step, we can use arbitrary algorithm to determine dominators.
1439 We decided to prefer the algorithm [3] to the algorithm of
1440 Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
1441 10 during gcc bootstrap), and [3] should perform better in this case.
1442
1443 Finally, we need to determine the immediate dominators for the basic
1444 blocks of BBS. If the immediate dominator of X in G is Y, then
1445 the immediate dominator of X in CFG belongs to the tree of F rooted in
1446 Y. We process the dominator tree T of G recursively, starting from leaves.
1447 Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
1448 subtrees of the dominance tree of CFG rooted in X_i are already correct.
1449 Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make
1450 the following observations:
1451 (i) the immediate dominator of all blocks in a strongly connected
1452 component of G' is the same
1453 (ii) if X has no predecessors in G', then the immediate dominator of X
1454 is the nearest common ancestor of the predecessors of X in the
1455 subtree of F rooted in Y
1456 Therefore, it suffices to find the topological ordering of G', and
1457 process the nodes X_i in this order using the rules (i) and (ii).
1458 Then, we contract all the nodes X_i with Y in G, so that the further
1459 steps work correctly. */
1460
1461 if (!conservative)
1462 {
1463 /* Split the tree now. If the idoms of blocks in BBS are not
1464 conservatively correct, setting the dominators using the
1465 heuristics in prune_bbs_to_update_dominators could
1466 create cycles in the dominance "tree", and cause ICE. */
1467 FOR_EACH_VEC_ELT (bbs, i, bb)
1468 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1469 }
1470
1471 prune_bbs_to_update_dominators (bbs, conservative);
1472 n = bbs.length ();
1473
1474 if (n == 0)
1475 return;
1476
1477 if (n == 1)
1478 {
1479 bb = bbs[0];
1480 set_immediate_dominator (CDI_DOMINATORS, bb,
1481 recompute_dominator (CDI_DOMINATORS, bb));
1482 return;
1483 }
1484
1485 timevar_push (TV_DOMINANCE);
1486
1487 /* Construct the graph G. */
1488 hash_map<basic_block, int> map (251);
1489 FOR_EACH_VEC_ELT (bbs, i, bb)
1490 {
1491 /* If the dominance tree is conservatively correct, split it now. */
1492 if (conservative)
1493 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1494 map.put (bb, i);
1495 }
1496 map.put (ENTRY_BLOCK_PTR_FOR_FN (cfun), n);
1497
1498 g = new_graph (n + 1);
1499 for (y = 0; y < g->n_vertices; y++)
1500 g->vertices[y].data = BITMAP_ALLOC (NULL);
1501 FOR_EACH_VEC_ELT (bbs, i, bb)
1502 {
1503 FOR_EACH_EDGE (e, ei, bb->preds)
1504 {
1505 dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
1506 if (dom == bb)
1507 continue;
1508
1509 dom_i = *map.get (dom);
1510
1511 /* Do not include parallel edges to G. */
1512 if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
1513 continue;
1514
1515 add_edge (g, dom_i, i);
1516 }
1517 }
1518 for (y = 0; y < g->n_vertices; y++)
1519 BITMAP_FREE (g->vertices[y].data);
1520
1521 /* Find the dominator tree of G. */
1522 son = XNEWVEC (int, n + 1);
1523 brother = XNEWVEC (int, n + 1);
1524 parent = XNEWVEC (int, n + 1);
1525 graphds_domtree (g, n, parent, son, brother);
1526
1527 /* Finally, traverse the tree and find the immediate dominators. */
1528 for (y = n; son[y] != -1; y = son[y])
1529 continue;
1530 while (y != -1)
1531 {
1532 determine_dominators_for_sons (g, bbs, y, son, brother);
1533
1534 if (brother[y] != -1)
1535 {
1536 y = brother[y];
1537 while (son[y] != -1)
1538 y = son[y];
1539 }
1540 else
1541 y = parent[y];
1542 }
1543
1544 free (son);
1545 free (brother);
1546 free (parent);
1547
1548 free_graph (g);
1549
1550 timevar_pop (TV_DOMINANCE);
1551 }
1552
1553 void
add_to_dominance_info(enum cdi_direction dir,basic_block bb)1554 add_to_dominance_info (enum cdi_direction dir, basic_block bb)
1555 {
1556 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1557
1558 gcc_checking_assert (dom_computed[dir_index] && !bb->dom[dir_index]);
1559
1560 n_bbs_in_dom_tree[dir_index]++;
1561
1562 bb->dom[dir_index] = et_new_tree (bb);
1563
1564 if (dom_computed[dir_index] == DOM_OK)
1565 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1566 }
1567
1568 void
delete_from_dominance_info(enum cdi_direction dir,basic_block bb)1569 delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
1570 {
1571 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1572
1573 gcc_checking_assert (dom_computed[dir_index]);
1574
1575 et_free_tree (bb->dom[dir_index]);
1576 bb->dom[dir_index] = NULL;
1577 n_bbs_in_dom_tree[dir_index]--;
1578
1579 if (dom_computed[dir_index] == DOM_OK)
1580 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1581 }
1582
1583 /* Returns the first son of BB in the dominator or postdominator tree
1584 as determined by DIR. */
1585
1586 basic_block
first_dom_son(enum cdi_direction dir,basic_block bb)1587 first_dom_son (enum cdi_direction dir, basic_block bb)
1588 {
1589 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1590 struct et_node *son = bb->dom[dir_index]->son;
1591
1592 return (basic_block) (son ? son->data : NULL);
1593 }
1594
1595 /* Returns the next dominance son after BB in the dominator or postdominator
1596 tree as determined by DIR, or NULL if it was the last one. */
1597
1598 basic_block
next_dom_son(enum cdi_direction dir,basic_block bb)1599 next_dom_son (enum cdi_direction dir, basic_block bb)
1600 {
1601 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1602 struct et_node *next = bb->dom[dir_index]->right;
1603
1604 return (basic_block) (next->father->son == next ? NULL : next->data);
1605 }
1606
1607 /* Return dominance availability for dominance info DIR. */
1608
1609 enum dom_state
dom_info_state(function * fn,enum cdi_direction dir)1610 dom_info_state (function *fn, enum cdi_direction dir)
1611 {
1612 if (!fn->cfg)
1613 return DOM_NONE;
1614
1615 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1616 return fn->cfg->x_dom_computed[dir_index];
1617 }
1618
1619 enum dom_state
dom_info_state(enum cdi_direction dir)1620 dom_info_state (enum cdi_direction dir)
1621 {
1622 return dom_info_state (cfun, dir);
1623 }
1624
1625 /* Set the dominance availability for dominance info DIR to NEW_STATE. */
1626
1627 void
set_dom_info_availability(enum cdi_direction dir,enum dom_state new_state)1628 set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
1629 {
1630 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1631
1632 dom_computed[dir_index] = new_state;
1633 }
1634
1635 /* Returns true if dominance information for direction DIR is available. */
1636
1637 bool
dom_info_available_p(function * fn,enum cdi_direction dir)1638 dom_info_available_p (function *fn, enum cdi_direction dir)
1639 {
1640 return dom_info_state (fn, dir) != DOM_NONE;
1641 }
1642
1643 bool
dom_info_available_p(enum cdi_direction dir)1644 dom_info_available_p (enum cdi_direction dir)
1645 {
1646 return dom_info_available_p (cfun, dir);
1647 }
1648
1649 DEBUG_FUNCTION void
debug_dominance_info(enum cdi_direction dir)1650 debug_dominance_info (enum cdi_direction dir)
1651 {
1652 basic_block bb, bb2;
1653 FOR_EACH_BB_FN (bb, cfun)
1654 if ((bb2 = get_immediate_dominator (dir, bb)))
1655 fprintf (stderr, "%i %i\n", bb->index, bb2->index);
1656 }
1657
1658 /* Prints to stderr representation of the dominance tree (for direction DIR)
1659 rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false,
1660 the first line of the output is not indented. */
1661
1662 static void
debug_dominance_tree_1(enum cdi_direction dir,basic_block root,unsigned indent,bool indent_first)1663 debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
1664 unsigned indent, bool indent_first)
1665 {
1666 basic_block son;
1667 unsigned i;
1668 bool first = true;
1669
1670 if (indent_first)
1671 for (i = 0; i < indent; i++)
1672 fprintf (stderr, "\t");
1673 fprintf (stderr, "%d\t", root->index);
1674
1675 for (son = first_dom_son (dir, root);
1676 son;
1677 son = next_dom_son (dir, son))
1678 {
1679 debug_dominance_tree_1 (dir, son, indent + 1, !first);
1680 first = false;
1681 }
1682
1683 if (first)
1684 fprintf (stderr, "\n");
1685 }
1686
1687 /* Prints to stderr representation of the dominance tree (for direction DIR)
1688 rooted in ROOT. */
1689
1690 DEBUG_FUNCTION void
debug_dominance_tree(enum cdi_direction dir,basic_block root)1691 debug_dominance_tree (enum cdi_direction dir, basic_block root)
1692 {
1693 debug_dominance_tree_1 (dir, root, 0, false);
1694 }
1695