Daily bump.
[official-gcc.git] / gcc / dominance.c
blob5c96dadbbeb15d1db2f43cb20ff706797215a62d
1 /* Calculate (post)dominators in slightly super-linear time.
2 Copyright (C) 2000-2013 Free Software Foundation, Inc.
3 Contributed by Michael Matz (matz@ifh.de).
5 This file is part of GCC.
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.
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.
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/>. */
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.
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. */
35 #include "config.h"
36 #include "system.h"
37 #include "coretypes.h"
38 #include "tm.h"
39 #include "rtl.h"
40 #include "hard-reg-set.h"
41 #include "obstack.h"
42 #include "basic-block.h"
43 #include "diagnostic-core.h"
44 #include "et-forest.h"
45 #include "timevar.h"
46 #include "pointer-set.h"
47 #include "graphds.h"
48 #include "bitmap.h"
50 /* We name our nodes with integers, beginning with 1. Zero is reserved for
51 'undefined' or 'end of list'. The name of each node is given by the dfs
52 number of the corresponding basic block. Please note, that we include the
53 artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
54 support multiple entry points. Its dfs number is of course 1. */
56 /* Type of Basic Block aka. TBB */
57 typedef unsigned int TBB;
59 /* We work in a poor-mans object oriented fashion, and carry an instance of
60 this structure through all our 'methods'. It holds various arrays
61 reflecting the (sub)structure of the flowgraph. Most of them are of type
62 TBB and are also indexed by TBB. */
64 struct dom_info
66 /* The parent of a node in the DFS tree. */
67 TBB *dfs_parent;
68 /* For a node x key[x] is roughly the node nearest to the root from which
69 exists a way to x only over nodes behind x. Such a node is also called
70 semidominator. */
71 TBB *key;
72 /* The value in path_min[x] is the node y on the path from x to the root of
73 the tree x is in with the smallest key[y]. */
74 TBB *path_min;
75 /* bucket[x] points to the first node of the set of nodes having x as key. */
76 TBB *bucket;
77 /* And next_bucket[x] points to the next node. */
78 TBB *next_bucket;
79 /* After the algorithm is done, dom[x] contains the immediate dominator
80 of x. */
81 TBB *dom;
83 /* The following few fields implement the structures needed for disjoint
84 sets. */
85 /* set_chain[x] is the next node on the path from x to the representative
86 of the set containing x. If set_chain[x]==0 then x is a root. */
87 TBB *set_chain;
88 /* set_size[x] is the number of elements in the set named by x. */
89 unsigned int *set_size;
90 /* set_child[x] is used for balancing the tree representing a set. It can
91 be understood as the next sibling of x. */
92 TBB *set_child;
94 /* If b is the number of a basic block (BB->index), dfs_order[b] is the
95 number of that node in DFS order counted from 1. This is an index
96 into most of the other arrays in this structure. */
97 TBB *dfs_order;
98 /* If x is the DFS-index of a node which corresponds with a basic block,
99 dfs_to_bb[x] is that basic block. Note, that in our structure there are
100 more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
101 is true for every basic block bb, but not the opposite. */
102 basic_block *dfs_to_bb;
104 /* This is the next free DFS number when creating the DFS tree. */
105 unsigned int dfsnum;
106 /* The number of nodes in the DFS tree (==dfsnum-1). */
107 unsigned int nodes;
109 /* Blocks with bits set here have a fake edge to EXIT. These are used
110 to turn a DFS forest into a proper tree. */
111 bitmap fake_exit_edge;
114 static void init_dom_info (struct dom_info *, enum cdi_direction);
115 static void free_dom_info (struct dom_info *);
116 static void calc_dfs_tree_nonrec (struct dom_info *, basic_block, bool);
117 static void calc_dfs_tree (struct dom_info *, bool);
118 static void compress (struct dom_info *, TBB);
119 static TBB eval (struct dom_info *, TBB);
120 static void link_roots (struct dom_info *, TBB, TBB);
121 static void calc_idoms (struct dom_info *, bool);
122 void debug_dominance_info (enum cdi_direction);
123 void debug_dominance_tree (enum cdi_direction, basic_block);
125 /* Helper macro for allocating and initializing an array,
126 for aesthetic reasons. */
127 #define init_ar(var, type, num, content) \
128 do \
130 unsigned int i = 1; /* Catch content == i. */ \
131 if (! (content)) \
132 (var) = XCNEWVEC (type, num); \
133 else \
135 (var) = XNEWVEC (type, (num)); \
136 for (i = 0; i < num; i++) \
137 (var)[i] = (content); \
140 while (0)
142 /* Allocate all needed memory in a pessimistic fashion (so we round up).
143 This initializes the contents of DI, which already must be allocated. */
145 static void
146 init_dom_info (struct dom_info *di, enum cdi_direction dir)
148 /* We need memory for n_basic_blocks nodes. */
149 unsigned int num = n_basic_blocks;
150 init_ar (di->dfs_parent, TBB, num, 0);
151 init_ar (di->path_min, TBB, num, i);
152 init_ar (di->key, TBB, num, i);
153 init_ar (di->dom, TBB, num, 0);
155 init_ar (di->bucket, TBB, num, 0);
156 init_ar (di->next_bucket, TBB, num, 0);
158 init_ar (di->set_chain, TBB, num, 0);
159 init_ar (di->set_size, unsigned int, num, 1);
160 init_ar (di->set_child, TBB, num, 0);
162 init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0);
163 init_ar (di->dfs_to_bb, basic_block, num, 0);
165 di->dfsnum = 1;
166 di->nodes = 0;
168 switch (dir)
170 case CDI_DOMINATORS:
171 di->fake_exit_edge = NULL;
172 break;
173 case CDI_POST_DOMINATORS:
174 di->fake_exit_edge = BITMAP_ALLOC (NULL);
175 break;
176 default:
177 gcc_unreachable ();
178 break;
182 #undef init_ar
184 /* Map dominance calculation type to array index used for various
185 dominance information arrays. This version is simple -- it will need
186 to be modified, obviously, if additional values are added to
187 cdi_direction. */
189 static unsigned int
190 dom_convert_dir_to_idx (enum cdi_direction dir)
192 gcc_checking_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
193 return dir - 1;
196 /* Free all allocated memory in DI, but not DI itself. */
198 static void
199 free_dom_info (struct dom_info *di)
201 free (di->dfs_parent);
202 free (di->path_min);
203 free (di->key);
204 free (di->dom);
205 free (di->bucket);
206 free (di->next_bucket);
207 free (di->set_chain);
208 free (di->set_size);
209 free (di->set_child);
210 free (di->dfs_order);
211 free (di->dfs_to_bb);
212 BITMAP_FREE (di->fake_exit_edge);
215 /* The nonrecursive variant of creating a DFS tree. DI is our working
216 structure, BB the starting basic block for this tree and REVERSE
217 is true, if predecessors should be visited instead of successors of a
218 node. After this is done all nodes reachable from BB were visited, have
219 assigned their dfs number and are linked together to form a tree. */
221 static void
222 calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
224 /* We call this _only_ if bb is not already visited. */
225 edge e;
226 TBB child_i, my_i = 0;
227 edge_iterator *stack;
228 edge_iterator ei, einext;
229 int sp;
230 /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
231 problem). */
232 basic_block en_block;
233 /* Ending block. */
234 basic_block ex_block;
236 stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
237 sp = 0;
239 /* Initialize our border blocks, and the first edge. */
240 if (reverse)
242 ei = ei_start (bb->preds);
243 en_block = EXIT_BLOCK_PTR;
244 ex_block = ENTRY_BLOCK_PTR;
246 else
248 ei = ei_start (bb->succs);
249 en_block = ENTRY_BLOCK_PTR;
250 ex_block = EXIT_BLOCK_PTR;
253 /* When the stack is empty we break out of this loop. */
254 while (1)
256 basic_block bn;
258 /* This loop traverses edges e in depth first manner, and fills the
259 stack. */
260 while (!ei_end_p (ei))
262 e = ei_edge (ei);
264 /* Deduce from E the current and the next block (BB and BN), and the
265 next edge. */
266 if (reverse)
268 bn = e->src;
270 /* If the next node BN is either already visited or a border
271 block the current edge is useless, and simply overwritten
272 with the next edge out of the current node. */
273 if (bn == ex_block || di->dfs_order[bn->index])
275 ei_next (&ei);
276 continue;
278 bb = e->dest;
279 einext = ei_start (bn->preds);
281 else
283 bn = e->dest;
284 if (bn == ex_block || di->dfs_order[bn->index])
286 ei_next (&ei);
287 continue;
289 bb = e->src;
290 einext = ei_start (bn->succs);
293 gcc_assert (bn != en_block);
295 /* Fill the DFS tree info calculatable _before_ recursing. */
296 if (bb != en_block)
297 my_i = di->dfs_order[bb->index];
298 else
299 my_i = di->dfs_order[last_basic_block];
300 child_i = di->dfs_order[bn->index] = di->dfsnum++;
301 di->dfs_to_bb[child_i] = bn;
302 di->dfs_parent[child_i] = my_i;
304 /* Save the current point in the CFG on the stack, and recurse. */
305 stack[sp++] = ei;
306 ei = einext;
309 if (!sp)
310 break;
311 ei = stack[--sp];
313 /* OK. The edge-list was exhausted, meaning normally we would
314 end the recursion. After returning from the recursive call,
315 there were (may be) other statements which were run after a
316 child node was completely considered by DFS. Here is the
317 point to do it in the non-recursive variant.
318 E.g. The block just completed is in e->dest for forward DFS,
319 the block not yet completed (the parent of the one above)
320 in e->src. This could be used e.g. for computing the number of
321 descendants or the tree depth. */
322 ei_next (&ei);
324 free (stack);
327 /* The main entry for calculating the DFS tree or forest. DI is our working
328 structure and REVERSE is true, if we are interested in the reverse flow
329 graph. In that case the result is not necessarily a tree but a forest,
330 because there may be nodes from which the EXIT_BLOCK is unreachable. */
332 static void
333 calc_dfs_tree (struct dom_info *di, bool reverse)
335 /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */
336 basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
337 di->dfs_order[last_basic_block] = di->dfsnum;
338 di->dfs_to_bb[di->dfsnum] = begin;
339 di->dfsnum++;
341 calc_dfs_tree_nonrec (di, begin, reverse);
343 if (reverse)
345 /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
346 They are reverse-unreachable. In the dom-case we disallow such
347 nodes, but in post-dom we have to deal with them.
349 There are two situations in which this occurs. First, noreturn
350 functions. Second, infinite loops. In the first case we need to
351 pretend that there is an edge to the exit block. In the second
352 case, we wind up with a forest. We need to process all noreturn
353 blocks before we know if we've got any infinite loops. */
355 basic_block b;
356 bool saw_unconnected = false;
358 FOR_EACH_BB_REVERSE (b)
360 if (EDGE_COUNT (b->succs) > 0)
362 if (di->dfs_order[b->index] == 0)
363 saw_unconnected = true;
364 continue;
366 bitmap_set_bit (di->fake_exit_edge, b->index);
367 di->dfs_order[b->index] = di->dfsnum;
368 di->dfs_to_bb[di->dfsnum] = b;
369 di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
370 di->dfsnum++;
371 calc_dfs_tree_nonrec (di, b, reverse);
374 if (saw_unconnected)
376 FOR_EACH_BB_REVERSE (b)
378 basic_block b2;
379 if (di->dfs_order[b->index])
380 continue;
381 b2 = dfs_find_deadend (b);
382 gcc_checking_assert (di->dfs_order[b2->index] == 0);
383 bitmap_set_bit (di->fake_exit_edge, b2->index);
384 di->dfs_order[b2->index] = di->dfsnum;
385 di->dfs_to_bb[di->dfsnum] = b2;
386 di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
387 di->dfsnum++;
388 calc_dfs_tree_nonrec (di, b2, reverse);
389 gcc_checking_assert (di->dfs_order[b->index]);
394 di->nodes = di->dfsnum - 1;
396 /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
397 gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
400 /* Compress the path from V to the root of its set and update path_min at the
401 same time. After compress(di, V) set_chain[V] is the root of the set V is
402 in and path_min[V] is the node with the smallest key[] value on the path
403 from V to that root. */
405 static void
406 compress (struct dom_info *di, TBB v)
408 /* Btw. It's not worth to unrecurse compress() as the depth is usually not
409 greater than 5 even for huge graphs (I've not seen call depth > 4).
410 Also performance wise compress() ranges _far_ behind eval(). */
411 TBB parent = di->set_chain[v];
412 if (di->set_chain[parent])
414 compress (di, parent);
415 if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
416 di->path_min[v] = di->path_min[parent];
417 di->set_chain[v] = di->set_chain[parent];
421 /* Compress the path from V to the set root of V if needed (when the root has
422 changed since the last call). Returns the node with the smallest key[]
423 value on the path from V to the root. */
425 static inline TBB
426 eval (struct dom_info *di, TBB v)
428 /* The representative of the set V is in, also called root (as the set
429 representation is a tree). */
430 TBB rep = di->set_chain[v];
432 /* V itself is the root. */
433 if (!rep)
434 return di->path_min[v];
436 /* Compress only if necessary. */
437 if (di->set_chain[rep])
439 compress (di, v);
440 rep = di->set_chain[v];
443 if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
444 return di->path_min[v];
445 else
446 return di->path_min[rep];
449 /* This essentially merges the two sets of V and W, giving a single set with
450 the new root V. The internal representation of these disjoint sets is a
451 balanced tree. Currently link(V,W) is only used with V being the parent
452 of W. */
454 static void
455 link_roots (struct dom_info *di, TBB v, TBB w)
457 TBB s = w;
459 /* Rebalance the tree. */
460 while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
462 if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
463 >= 2 * di->set_size[di->set_child[s]])
465 di->set_chain[di->set_child[s]] = s;
466 di->set_child[s] = di->set_child[di->set_child[s]];
468 else
470 di->set_size[di->set_child[s]] = di->set_size[s];
471 s = di->set_chain[s] = di->set_child[s];
475 di->path_min[s] = di->path_min[w];
476 di->set_size[v] += di->set_size[w];
477 if (di->set_size[v] < 2 * di->set_size[w])
479 TBB tmp = s;
480 s = di->set_child[v];
481 di->set_child[v] = tmp;
484 /* Merge all subtrees. */
485 while (s)
487 di->set_chain[s] = v;
488 s = di->set_child[s];
492 /* This calculates the immediate dominators (or post-dominators if REVERSE is
493 true). DI is our working structure and should hold the DFS forest.
494 On return the immediate dominator to node V is in di->dom[V]. */
496 static void
497 calc_idoms (struct dom_info *di, bool reverse)
499 TBB v, w, k, par;
500 basic_block en_block;
501 edge_iterator ei, einext;
503 if (reverse)
504 en_block = EXIT_BLOCK_PTR;
505 else
506 en_block = ENTRY_BLOCK_PTR;
508 /* Go backwards in DFS order, to first look at the leafs. */
509 v = di->nodes;
510 while (v > 1)
512 basic_block bb = di->dfs_to_bb[v];
513 edge e;
515 par = di->dfs_parent[v];
516 k = v;
518 ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
520 if (reverse)
522 /* If this block has a fake edge to exit, process that first. */
523 if (bitmap_bit_p (di->fake_exit_edge, bb->index))
525 einext = ei;
526 einext.index = 0;
527 goto do_fake_exit_edge;
531 /* Search all direct predecessors for the smallest node with a path
532 to them. That way we have the smallest node with also a path to
533 us only over nodes behind us. In effect we search for our
534 semidominator. */
535 while (!ei_end_p (ei))
537 TBB k1;
538 basic_block b;
540 e = ei_edge (ei);
541 b = (reverse) ? e->dest : e->src;
542 einext = ei;
543 ei_next (&einext);
545 if (b == en_block)
547 do_fake_exit_edge:
548 k1 = di->dfs_order[last_basic_block];
550 else
551 k1 = di->dfs_order[b->index];
553 /* Call eval() only if really needed. If k1 is above V in DFS tree,
554 then we know, that eval(k1) == k1 and key[k1] == k1. */
555 if (k1 > v)
556 k1 = di->key[eval (di, k1)];
557 if (k1 < k)
558 k = k1;
560 ei = einext;
563 di->key[v] = k;
564 link_roots (di, par, v);
565 di->next_bucket[v] = di->bucket[k];
566 di->bucket[k] = v;
568 /* Transform semidominators into dominators. */
569 for (w = di->bucket[par]; w; w = di->next_bucket[w])
571 k = eval (di, w);
572 if (di->key[k] < di->key[w])
573 di->dom[w] = k;
574 else
575 di->dom[w] = par;
577 /* We don't need to cleanup next_bucket[]. */
578 di->bucket[par] = 0;
579 v--;
582 /* Explicitly define the dominators. */
583 di->dom[1] = 0;
584 for (v = 2; v <= di->nodes; v++)
585 if (di->dom[v] != di->key[v])
586 di->dom[v] = di->dom[di->dom[v]];
589 /* Assign dfs numbers starting from NUM to NODE and its sons. */
591 static void
592 assign_dfs_numbers (struct et_node *node, int *num)
594 struct et_node *son;
596 node->dfs_num_in = (*num)++;
598 if (node->son)
600 assign_dfs_numbers (node->son, num);
601 for (son = node->son->right; son != node->son; son = son->right)
602 assign_dfs_numbers (son, num);
605 node->dfs_num_out = (*num)++;
608 /* Compute the data necessary for fast resolving of dominator queries in a
609 static dominator tree. */
611 static void
612 compute_dom_fast_query (enum cdi_direction dir)
614 int num = 0;
615 basic_block bb;
616 unsigned int dir_index = dom_convert_dir_to_idx (dir);
618 gcc_checking_assert (dom_info_available_p (dir));
620 if (dom_computed[dir_index] == DOM_OK)
621 return;
623 FOR_ALL_BB (bb)
625 if (!bb->dom[dir_index]->father)
626 assign_dfs_numbers (bb->dom[dir_index], &num);
629 dom_computed[dir_index] = DOM_OK;
632 /* The main entry point into this module. DIR is set depending on whether
633 we want to compute dominators or postdominators. */
635 void
636 calculate_dominance_info (enum cdi_direction dir)
638 struct dom_info di;
639 basic_block b;
640 unsigned int dir_index = dom_convert_dir_to_idx (dir);
641 bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
643 if (dom_computed[dir_index] == DOM_OK)
644 return;
646 timevar_push (TV_DOMINANCE);
647 if (!dom_info_available_p (dir))
649 gcc_assert (!n_bbs_in_dom_tree[dir_index]);
651 FOR_ALL_BB (b)
653 b->dom[dir_index] = et_new_tree (b);
655 n_bbs_in_dom_tree[dir_index] = n_basic_blocks;
657 init_dom_info (&di, dir);
658 calc_dfs_tree (&di, reverse);
659 calc_idoms (&di, reverse);
661 FOR_EACH_BB (b)
663 TBB d = di.dom[di.dfs_order[b->index]];
665 if (di.dfs_to_bb[d])
666 et_set_father (b->dom[dir_index], di.dfs_to_bb[d]->dom[dir_index]);
669 free_dom_info (&di);
670 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
673 compute_dom_fast_query (dir);
675 timevar_pop (TV_DOMINANCE);
678 /* Free dominance information for direction DIR. */
679 void
680 free_dominance_info (enum cdi_direction dir)
682 basic_block bb;
683 unsigned int dir_index = dom_convert_dir_to_idx (dir);
685 if (!dom_info_available_p (dir))
686 return;
688 FOR_ALL_BB (bb)
690 et_free_tree_force (bb->dom[dir_index]);
691 bb->dom[dir_index] = NULL;
693 et_free_pools ();
695 n_bbs_in_dom_tree[dir_index] = 0;
697 dom_computed[dir_index] = DOM_NONE;
700 /* Return the immediate dominator of basic block BB. */
701 basic_block
702 get_immediate_dominator (enum cdi_direction dir, basic_block bb)
704 unsigned int dir_index = dom_convert_dir_to_idx (dir);
705 struct et_node *node = bb->dom[dir_index];
707 gcc_checking_assert (dom_computed[dir_index]);
709 if (!node->father)
710 return NULL;
712 return (basic_block) node->father->data;
715 /* Set the immediate dominator of the block possibly removing
716 existing edge. NULL can be used to remove any edge. */
717 void
718 set_immediate_dominator (enum cdi_direction dir, basic_block bb,
719 basic_block dominated_by)
721 unsigned int dir_index = dom_convert_dir_to_idx (dir);
722 struct et_node *node = bb->dom[dir_index];
724 gcc_checking_assert (dom_computed[dir_index]);
726 if (node->father)
728 if (node->father->data == dominated_by)
729 return;
730 et_split (node);
733 if (dominated_by)
734 et_set_father (node, dominated_by->dom[dir_index]);
736 if (dom_computed[dir_index] == DOM_OK)
737 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
740 /* Returns the list of basic blocks immediately dominated by BB, in the
741 direction DIR. */
742 vec<basic_block>
743 get_dominated_by (enum cdi_direction dir, basic_block bb)
745 unsigned int dir_index = dom_convert_dir_to_idx (dir);
746 struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
747 vec<basic_block> bbs = vNULL;
749 gcc_checking_assert (dom_computed[dir_index]);
751 if (!son)
752 return vNULL;
754 bbs.safe_push ((basic_block) son->data);
755 for (ason = son->right; ason != son; ason = ason->right)
756 bbs.safe_push ((basic_block) ason->data);
758 return bbs;
761 /* Returns the list of basic blocks that are immediately dominated (in
762 direction DIR) by some block between N_REGION ones stored in REGION,
763 except for blocks in the REGION itself. */
765 vec<basic_block>
766 get_dominated_by_region (enum cdi_direction dir, basic_block *region,
767 unsigned n_region)
769 unsigned i;
770 basic_block dom;
771 vec<basic_block> doms = vNULL;
773 for (i = 0; i < n_region; i++)
774 region[i]->flags |= BB_DUPLICATED;
775 for (i = 0; i < n_region; i++)
776 for (dom = first_dom_son (dir, region[i]);
777 dom;
778 dom = next_dom_son (dir, dom))
779 if (!(dom->flags & BB_DUPLICATED))
780 doms.safe_push (dom);
781 for (i = 0; i < n_region; i++)
782 region[i]->flags &= ~BB_DUPLICATED;
784 return doms;
787 /* Returns the list of basic blocks including BB dominated by BB, in the
788 direction DIR up to DEPTH in the dominator tree. The DEPTH of zero will
789 produce a vector containing all dominated blocks. The vector will be sorted
790 in preorder. */
792 vec<basic_block>
793 get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
795 vec<basic_block> bbs = vNULL;
796 unsigned i;
797 unsigned next_level_start;
799 i = 0;
800 bbs.safe_push (bb);
801 next_level_start = 1; /* = bbs.length (); */
805 basic_block son;
807 bb = bbs[i++];
808 for (son = first_dom_son (dir, bb);
809 son;
810 son = next_dom_son (dir, son))
811 bbs.safe_push (son);
813 if (i == next_level_start && --depth)
814 next_level_start = bbs.length ();
816 while (i < next_level_start);
818 return bbs;
821 /* Returns the list of basic blocks including BB dominated by BB, in the
822 direction DIR. The vector will be sorted in preorder. */
824 vec<basic_block>
825 get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
827 return get_dominated_to_depth (dir, bb, 0);
830 /* Redirect all edges pointing to BB to TO. */
831 void
832 redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
833 basic_block to)
835 unsigned int dir_index = dom_convert_dir_to_idx (dir);
836 struct et_node *bb_node, *to_node, *son;
838 bb_node = bb->dom[dir_index];
839 to_node = to->dom[dir_index];
841 gcc_checking_assert (dom_computed[dir_index]);
843 if (!bb_node->son)
844 return;
846 while (bb_node->son)
848 son = bb_node->son;
850 et_split (son);
851 et_set_father (son, to_node);
854 if (dom_computed[dir_index] == DOM_OK)
855 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
858 /* Find first basic block in the tree dominating both BB1 and BB2. */
859 basic_block
860 nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
862 unsigned int dir_index = dom_convert_dir_to_idx (dir);
864 gcc_checking_assert (dom_computed[dir_index]);
866 if (!bb1)
867 return bb2;
868 if (!bb2)
869 return bb1;
871 return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
875 /* Find the nearest common dominator for the basic blocks in BLOCKS,
876 using dominance direction DIR. */
878 basic_block
879 nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
881 unsigned i, first;
882 bitmap_iterator bi;
883 basic_block dom;
885 first = bitmap_first_set_bit (blocks);
886 dom = BASIC_BLOCK (first);
887 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
888 if (dom != BASIC_BLOCK (i))
889 dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
891 return dom;
894 /* Given a dominator tree, we can determine whether one thing
895 dominates another in constant time by using two DFS numbers:
897 1. The number for when we visit a node on the way down the tree
898 2. The number for when we visit a node on the way back up the tree
900 You can view these as bounds for the range of dfs numbers the
901 nodes in the subtree of the dominator tree rooted at that node
902 will contain.
904 The dominator tree is always a simple acyclic tree, so there are
905 only three possible relations two nodes in the dominator tree have
906 to each other:
908 1. Node A is above Node B (and thus, Node A dominates node B)
917 In the above case, DFS_Number_In of A will be <= DFS_Number_In of
918 B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is
919 because we must hit A in the dominator tree *before* B on the walk
920 down, and we will hit A *after* B on the walk back up
922 2. Node A is below node B (and thus, node B dominates node A)
931 In the above case, DFS_Number_In of A will be >= DFS_Number_In of
932 B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
934 This is because we must hit A in the dominator tree *after* B on
935 the walk down, and we will hit A *before* B on the walk back up
937 3. Node A and B are siblings (and thus, neither dominates the other)
945 In the above case, DFS_Number_In of A will *always* be <=
946 DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
947 DFS_Number_Out of B. This is because we will always finish the dfs
948 walk of one of the subtrees before the other, and thus, the dfs
949 numbers for one subtree can't intersect with the range of dfs
950 numbers for the other subtree. If you swap A and B's position in
951 the dominator tree, the comparison changes direction, but the point
952 is that both comparisons will always go the same way if there is no
953 dominance relationship.
955 Thus, it is sufficient to write
957 A_Dominates_B (node A, node B)
959 return DFS_Number_In(A) <= DFS_Number_In(B)
960 && DFS_Number_Out (A) >= DFS_Number_Out(B);
963 A_Dominated_by_B (node A, node B)
965 return DFS_Number_In(A) >= DFS_Number_In(A)
966 && DFS_Number_Out (A) <= DFS_Number_Out(B);
967 } */
969 /* Return TRUE in case BB1 is dominated by BB2. */
970 bool
971 dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
973 unsigned int dir_index = dom_convert_dir_to_idx (dir);
974 struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
976 gcc_checking_assert (dom_computed[dir_index]);
978 if (dom_computed[dir_index] == DOM_OK)
979 return (n1->dfs_num_in >= n2->dfs_num_in
980 && n1->dfs_num_out <= n2->dfs_num_out);
982 return et_below (n1, n2);
985 /* Returns the entry dfs number for basic block BB, in the direction DIR. */
987 unsigned
988 bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
990 unsigned int dir_index = dom_convert_dir_to_idx (dir);
991 struct et_node *n = bb->dom[dir_index];
993 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
994 return n->dfs_num_in;
997 /* Returns the exit dfs number for basic block BB, in the direction DIR. */
999 unsigned
1000 bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
1002 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1003 struct et_node *n = bb->dom[dir_index];
1005 gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
1006 return n->dfs_num_out;
1009 /* Verify invariants of dominator structure. */
1010 DEBUG_FUNCTION void
1011 verify_dominators (enum cdi_direction dir)
1013 int err = 0;
1014 basic_block bb, imm_bb, imm_bb_correct;
1015 struct dom_info di;
1016 bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
1018 gcc_assert (dom_info_available_p (dir));
1020 init_dom_info (&di, dir);
1021 calc_dfs_tree (&di, reverse);
1022 calc_idoms (&di, reverse);
1024 FOR_EACH_BB (bb)
1026 imm_bb = get_immediate_dominator (dir, bb);
1027 if (!imm_bb)
1029 error ("dominator of %d status unknown", bb->index);
1030 err = 1;
1033 imm_bb_correct = di.dfs_to_bb[di.dom[di.dfs_order[bb->index]]];
1034 if (imm_bb != imm_bb_correct)
1036 error ("dominator of %d should be %d, not %d",
1037 bb->index, imm_bb_correct->index, imm_bb->index);
1038 err = 1;
1042 free_dom_info (&di);
1043 gcc_assert (!err);
1046 /* Determine immediate dominator (or postdominator, according to DIR) of BB,
1047 assuming that dominators of other blocks are correct. We also use it to
1048 recompute the dominators in a restricted area, by iterating it until it
1049 reaches a fixed point. */
1051 basic_block
1052 recompute_dominator (enum cdi_direction dir, basic_block bb)
1054 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1055 basic_block dom_bb = NULL;
1056 edge e;
1057 edge_iterator ei;
1059 gcc_checking_assert (dom_computed[dir_index]);
1061 if (dir == CDI_DOMINATORS)
1063 FOR_EACH_EDGE (e, ei, bb->preds)
1065 if (!dominated_by_p (dir, e->src, bb))
1066 dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
1069 else
1071 FOR_EACH_EDGE (e, ei, bb->succs)
1073 if (!dominated_by_p (dir, e->dest, bb))
1074 dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
1078 return dom_bb;
1081 /* Use simple heuristics (see iterate_fix_dominators) to determine dominators
1082 of BBS. We assume that all the immediate dominators except for those of the
1083 blocks in BBS are correct. If CONSERVATIVE is true, we also assume that the
1084 currently recorded immediate dominators of blocks in BBS really dominate the
1085 blocks. The basic blocks for that we determine the dominator are removed
1086 from BBS. */
1088 static void
1089 prune_bbs_to_update_dominators (vec<basic_block> bbs,
1090 bool conservative)
1092 unsigned i;
1093 bool single;
1094 basic_block bb, dom = NULL;
1095 edge_iterator ei;
1096 edge e;
1098 for (i = 0; bbs.iterate (i, &bb);)
1100 if (bb == ENTRY_BLOCK_PTR)
1101 goto succeed;
1103 if (single_pred_p (bb))
1105 set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
1106 goto succeed;
1109 if (!conservative)
1110 goto fail;
1112 single = true;
1113 dom = NULL;
1114 FOR_EACH_EDGE (e, ei, bb->preds)
1116 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
1117 continue;
1119 if (!dom)
1120 dom = e->src;
1121 else
1123 single = false;
1124 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1128 gcc_assert (dom != NULL);
1129 if (single
1130 || find_edge (dom, bb))
1132 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1133 goto succeed;
1136 fail:
1137 i++;
1138 continue;
1140 succeed:
1141 bbs.unordered_remove (i);
1145 /* Returns root of the dominance tree in the direction DIR that contains
1146 BB. */
1148 static basic_block
1149 root_of_dom_tree (enum cdi_direction dir, basic_block bb)
1151 return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
1154 /* See the comment in iterate_fix_dominators. Finds the immediate dominators
1155 for the sons of Y, found using the SON and BROTHER arrays representing
1156 the dominance tree of graph G. BBS maps the vertices of G to the basic
1157 blocks. */
1159 static void
1160 determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
1161 int y, int *son, int *brother)
1163 bitmap gprime;
1164 int i, a, nc;
1165 vec<int> *sccs;
1166 basic_block bb, dom, ybb;
1167 unsigned si;
1168 edge e;
1169 edge_iterator ei;
1171 if (son[y] == -1)
1172 return;
1173 if (y == (int) bbs.length ())
1174 ybb = ENTRY_BLOCK_PTR;
1175 else
1176 ybb = bbs[y];
1178 if (brother[son[y]] == -1)
1180 /* Handle the common case Y has just one son specially. */
1181 bb = bbs[son[y]];
1182 set_immediate_dominator (CDI_DOMINATORS, bb,
1183 recompute_dominator (CDI_DOMINATORS, bb));
1184 identify_vertices (g, y, son[y]);
1185 return;
1188 gprime = BITMAP_ALLOC (NULL);
1189 for (a = son[y]; a != -1; a = brother[a])
1190 bitmap_set_bit (gprime, a);
1192 nc = graphds_scc (g, gprime);
1193 BITMAP_FREE (gprime);
1195 /* ??? Needed to work around the pre-processor confusion with
1196 using a multi-argument template type as macro argument. */
1197 typedef vec<int> vec_int_heap;
1198 sccs = XCNEWVEC (vec_int_heap, nc);
1199 for (a = son[y]; a != -1; a = brother[a])
1200 sccs[g->vertices[a].component].safe_push (a);
1202 for (i = nc - 1; i >= 0; i--)
1204 dom = NULL;
1205 FOR_EACH_VEC_ELT (sccs[i], si, a)
1207 bb = bbs[a];
1208 FOR_EACH_EDGE (e, ei, bb->preds)
1210 if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
1211 continue;
1213 dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
1217 gcc_assert (dom != NULL);
1218 FOR_EACH_VEC_ELT (sccs[i], si, a)
1220 bb = bbs[a];
1221 set_immediate_dominator (CDI_DOMINATORS, bb, dom);
1225 for (i = 0; i < nc; i++)
1226 sccs[i].release ();
1227 free (sccs);
1229 for (a = son[y]; a != -1; a = brother[a])
1230 identify_vertices (g, y, a);
1233 /* Recompute dominance information for basic blocks in the set BBS. The
1234 function assumes that the immediate dominators of all the other blocks
1235 in CFG are correct, and that there are no unreachable blocks.
1237 If CONSERVATIVE is true, we additionally assume that all the ancestors of
1238 a block of BBS in the current dominance tree dominate it. */
1240 void
1241 iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
1242 bool conservative)
1244 unsigned i;
1245 basic_block bb, dom;
1246 struct graph *g;
1247 int n, y;
1248 size_t dom_i;
1249 edge e;
1250 edge_iterator ei;
1251 struct pointer_map_t *map;
1252 int *parent, *son, *brother;
1253 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1255 /* We only support updating dominators. There are some problems with
1256 updating postdominators (need to add fake edges from infinite loops
1257 and noreturn functions), and since we do not currently use
1258 iterate_fix_dominators for postdominators, any attempt to handle these
1259 problems would be unused, untested, and almost surely buggy. We keep
1260 the DIR argument for consistency with the rest of the dominator analysis
1261 interface. */
1262 gcc_checking_assert (dir == CDI_DOMINATORS && dom_computed[dir_index]);
1264 /* The algorithm we use takes inspiration from the following papers, although
1265 the details are quite different from any of them:
1267 [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
1268 Dominator Tree of a Reducible Flowgraph
1269 [2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
1270 dominator trees
1271 [3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
1272 Algorithm
1274 First, we use the following heuristics to decrease the size of the BBS
1275 set:
1276 a) if BB has a single predecessor, then its immediate dominator is this
1277 predecessor
1278 additionally, if CONSERVATIVE is true:
1279 b) if all the predecessors of BB except for one (X) are dominated by BB,
1280 then X is the immediate dominator of BB
1281 c) if the nearest common ancestor of the predecessors of BB is X and
1282 X -> BB is an edge in CFG, then X is the immediate dominator of BB
1284 Then, we need to establish the dominance relation among the basic blocks
1285 in BBS. We split the dominance tree by removing the immediate dominator
1286 edges from BBS, creating a forest F. We form a graph G whose vertices
1287 are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
1288 X' -> Y in CFG such that X' belongs to the tree of the dominance forest
1289 whose root is X. We then determine dominance tree of G. Note that
1290 for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
1291 In this step, we can use arbitrary algorithm to determine dominators.
1292 We decided to prefer the algorithm [3] to the algorithm of
1293 Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
1294 10 during gcc bootstrap), and [3] should perform better in this case.
1296 Finally, we need to determine the immediate dominators for the basic
1297 blocks of BBS. If the immediate dominator of X in G is Y, then
1298 the immediate dominator of X in CFG belongs to the tree of F rooted in
1299 Y. We process the dominator tree T of G recursively, starting from leaves.
1300 Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
1301 subtrees of the dominance tree of CFG rooted in X_i are already correct.
1302 Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make
1303 the following observations:
1304 (i) the immediate dominator of all blocks in a strongly connected
1305 component of G' is the same
1306 (ii) if X has no predecessors in G', then the immediate dominator of X
1307 is the nearest common ancestor of the predecessors of X in the
1308 subtree of F rooted in Y
1309 Therefore, it suffices to find the topological ordering of G', and
1310 process the nodes X_i in this order using the rules (i) and (ii).
1311 Then, we contract all the nodes X_i with Y in G, so that the further
1312 steps work correctly. */
1314 if (!conservative)
1316 /* Split the tree now. If the idoms of blocks in BBS are not
1317 conservatively correct, setting the dominators using the
1318 heuristics in prune_bbs_to_update_dominators could
1319 create cycles in the dominance "tree", and cause ICE. */
1320 FOR_EACH_VEC_ELT (bbs, i, bb)
1321 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1324 prune_bbs_to_update_dominators (bbs, conservative);
1325 n = bbs.length ();
1327 if (n == 0)
1328 return;
1330 if (n == 1)
1332 bb = bbs[0];
1333 set_immediate_dominator (CDI_DOMINATORS, bb,
1334 recompute_dominator (CDI_DOMINATORS, bb));
1335 return;
1338 /* Construct the graph G. */
1339 map = pointer_map_create ();
1340 FOR_EACH_VEC_ELT (bbs, i, bb)
1342 /* If the dominance tree is conservatively correct, split it now. */
1343 if (conservative)
1344 set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
1345 *pointer_map_insert (map, bb) = (void *) (size_t) i;
1347 *pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
1349 g = new_graph (n + 1);
1350 for (y = 0; y < g->n_vertices; y++)
1351 g->vertices[y].data = BITMAP_ALLOC (NULL);
1352 FOR_EACH_VEC_ELT (bbs, i, bb)
1354 FOR_EACH_EDGE (e, ei, bb->preds)
1356 dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
1357 if (dom == bb)
1358 continue;
1360 dom_i = (size_t) *pointer_map_contains (map, dom);
1362 /* Do not include parallel edges to G. */
1363 if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
1364 continue;
1366 add_edge (g, dom_i, i);
1369 for (y = 0; y < g->n_vertices; y++)
1370 BITMAP_FREE (g->vertices[y].data);
1371 pointer_map_destroy (map);
1373 /* Find the dominator tree of G. */
1374 son = XNEWVEC (int, n + 1);
1375 brother = XNEWVEC (int, n + 1);
1376 parent = XNEWVEC (int, n + 1);
1377 graphds_domtree (g, n, parent, son, brother);
1379 /* Finally, traverse the tree and find the immediate dominators. */
1380 for (y = n; son[y] != -1; y = son[y])
1381 continue;
1382 while (y != -1)
1384 determine_dominators_for_sons (g, bbs, y, son, brother);
1386 if (brother[y] != -1)
1388 y = brother[y];
1389 while (son[y] != -1)
1390 y = son[y];
1392 else
1393 y = parent[y];
1396 free (son);
1397 free (brother);
1398 free (parent);
1400 free_graph (g);
1403 void
1404 add_to_dominance_info (enum cdi_direction dir, basic_block bb)
1406 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1408 gcc_checking_assert (dom_computed[dir_index] && !bb->dom[dir_index]);
1410 n_bbs_in_dom_tree[dir_index]++;
1412 bb->dom[dir_index] = et_new_tree (bb);
1414 if (dom_computed[dir_index] == DOM_OK)
1415 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1418 void
1419 delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
1421 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1423 gcc_checking_assert (dom_computed[dir_index]);
1425 et_free_tree (bb->dom[dir_index]);
1426 bb->dom[dir_index] = NULL;
1427 n_bbs_in_dom_tree[dir_index]--;
1429 if (dom_computed[dir_index] == DOM_OK)
1430 dom_computed[dir_index] = DOM_NO_FAST_QUERY;
1433 /* Returns the first son of BB in the dominator or postdominator tree
1434 as determined by DIR. */
1436 basic_block
1437 first_dom_son (enum cdi_direction dir, basic_block bb)
1439 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1440 struct et_node *son = bb->dom[dir_index]->son;
1442 return (basic_block) (son ? son->data : NULL);
1445 /* Returns the next dominance son after BB in the dominator or postdominator
1446 tree as determined by DIR, or NULL if it was the last one. */
1448 basic_block
1449 next_dom_son (enum cdi_direction dir, basic_block bb)
1451 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1452 struct et_node *next = bb->dom[dir_index]->right;
1454 return (basic_block) (next->father->son == next ? NULL : next->data);
1457 /* Return dominance availability for dominance info DIR. */
1459 enum dom_state
1460 dom_info_state (enum cdi_direction dir)
1462 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1464 return dom_computed[dir_index];
1467 /* Set the dominance availability for dominance info DIR to NEW_STATE. */
1469 void
1470 set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
1472 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1474 dom_computed[dir_index] = new_state;
1477 /* Returns true if dominance information for direction DIR is available. */
1479 bool
1480 dom_info_available_p (enum cdi_direction dir)
1482 unsigned int dir_index = dom_convert_dir_to_idx (dir);
1484 return dom_computed[dir_index] != DOM_NONE;
1487 DEBUG_FUNCTION void
1488 debug_dominance_info (enum cdi_direction dir)
1490 basic_block bb, bb2;
1491 FOR_EACH_BB (bb)
1492 if ((bb2 = get_immediate_dominator (dir, bb)))
1493 fprintf (stderr, "%i %i\n", bb->index, bb2->index);
1496 /* Prints to stderr representation of the dominance tree (for direction DIR)
1497 rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false,
1498 the first line of the output is not indented. */
1500 static void
1501 debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
1502 unsigned indent, bool indent_first)
1504 basic_block son;
1505 unsigned i;
1506 bool first = true;
1508 if (indent_first)
1509 for (i = 0; i < indent; i++)
1510 fprintf (stderr, "\t");
1511 fprintf (stderr, "%d\t", root->index);
1513 for (son = first_dom_son (dir, root);
1514 son;
1515 son = next_dom_son (dir, son))
1517 debug_dominance_tree_1 (dir, son, indent + 1, !first);
1518 first = false;
1521 if (first)
1522 fprintf (stderr, "\n");
1525 /* Prints to stderr representation of the dominance tree (for direction DIR)
1526 rooted in ROOT. */
1528 DEBUG_FUNCTION void
1529 debug_dominance_tree (enum cdi_direction dir, basic_block root)
1531 debug_dominance_tree_1 (dir, root, 0, false);