From f80326884cf82c1804385664197afa44ad468d97 Mon Sep 17 00:00:00 2001 From: Michael Matz Date: Tue, 14 Nov 2000 09:58:40 +0000 Subject: Michael Matz * dominance.c: New file. * Makefile.in (OBJS): Add dominance.o. * flow.c (compute_flow_dominators): Remove. (compute_immediate_dominators): Remove. (compute_immediate_postdominators): Remove. * basic-block.h: Remove their prototypes. (calculate_dominance_info): Add prototype. * dce.c (eliminate_dead_code): Change calls to above functions. Don't compute dominators but only immediate dominators. * flow.c (flow_loops_find): Change callers. * gcse.c (compute_code_hoist_data): Likewise. * haifa-sched.c (schedule_insns): Likewise. * ifcvt.c (if_convert): Likewise. * ssa.c (convert_to_ssa): Likewise, and only compute immediate dominators. From-SVN: r37449 --- gcc/ChangeLog | 20 ++ gcc/Makefile.in | 4 +- gcc/basic-block.h | 15 +- gcc/dce.c | 6 +- gcc/dominance.c | 622 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/flow.c | 246 +-------------------- gcc/gcse.c | 2 +- gcc/haifa-sched.c | 6 +- gcc/ifcvt.c | 2 +- gcc/ssa.c | 9 +- 10 files changed, 663 insertions(+), 269 deletions(-) create mode 100644 gcc/dominance.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d9794e1..ace6a89 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,23 @@ +2000-11-14 Michael Matz + + * dominance.c: New file. + * Makefile.in (OBJS): Add dominance.o. + + * flow.c (compute_flow_dominators): Remove. + (compute_immediate_dominators): Remove. + (compute_immediate_postdominators): Remove. + * basic-block.h: Remove their prototypes. + (calculate_dominance_info): Add prototype. + + * dce.c (eliminate_dead_code): Change calls to above functions. + Don't compute dominators but only immediate dominators. + * flow.c (flow_loops_find): Change callers. + * gcse.c (compute_code_hoist_data): Likewise. + * haifa-sched.c (schedule_insns): Likewise. + * ifcvt.c (if_convert): Likewise. + * ssa.c (convert_to_ssa): Likewise, and only compute immediate + dominators. + 2000-11-14 Richard Henderson * stmt.c (warn_if_unused_value): Don't warn if the expression diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 1550ec7..ff820d8 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -735,7 +735,7 @@ OBJS = diagnostic.o version.o tree.o print-tree.o stor-layout.o fold-const.o \ profile.o insn-attrtab.o $(out_object_file) $(EXTRA_OBJS) convert.o \ mbchar.o splay-tree.o graph.o sbitmap.o resource.o hash.o predict.o \ lists.o ggc-common.o $(GGC) simplify-rtx.o ssa.o bb-reorder.o \ - sibcall.o conflict.o timevar.o ifcvt.o dependence.o dce.o + sibcall.o conflict.o timevar.o ifcvt.o dominance.o dependence.o dce.o BACKEND = toplev.o libbackend.a @@ -1403,6 +1403,8 @@ unroll.o : unroll.c $(CONFIG_H) system.h $(RTL_H) insn-config.h function.h \ flow.o : flow.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h insn-config.h \ $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \ insn-flags.h function.h except.h $(EXPR_H) ssa.h $(GGC_H) +dominance.o : dominance.c $(CONFIG_H) system.h $(RTL_H) hard-reg-set.h \ + $(BASIC_BLOCK_H) combine.o : combine.c $(CONFIG_H) system.h $(RTL_H) flags.h function.h \ insn-config.h insn-flags.h insn-codes.h $(INSN_ATTR_H) $(REGS_H) $(EXPR_H) \ $(BASIC_BLOCK_H) $(RECOG_H) real.h hard-reg-set.h toplev.h diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 04177eb..f3ed1a9 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -458,10 +458,6 @@ void verify_edge_list PARAMS ((FILE *, struct edge_list *)); int find_edge_index PARAMS ((struct edge_list *, basic_block, basic_block)); -extern void compute_flow_dominators PARAMS ((sbitmap *, sbitmap *)); -extern void compute_immediate_dominators PARAMS ((int *, sbitmap *)); -extern void compute_immediate_postdominators PARAMS ((int *, sbitmap *)); - enum update_life_extent { @@ -565,4 +561,15 @@ extern conflict_graph conflict_graph_compute PARAMS ((regset, partition)); +/* In dominance.c */ + +enum cdi_direction +{ + CDI_DOMINATORS, + CDI_POST_DOMINATORS +}; + +extern void calculate_dominance_info PARAMS ((int *, sbitmap *, + enum cdi_direction)); + #endif /* _BASIC_BLOCK_H */ diff --git a/gcc/dce.c b/gcc/dce.c index ddd2cd0..3a83d7a 100644 --- a/gcc/dce.c +++ b/gcc/dce.c @@ -485,7 +485,6 @@ eliminate_dead_code () /* Map element (b,e) is nonzero if the block is control dependent on edge. "cdbte" abbreviates control dependent block to edge. */ control_dependent_block_to_edge_map cdbte; - sbitmap *postdominators; /* Element I is the immediate postdominator of block I. */ int *pdom; struct edge_list *el; @@ -504,17 +503,14 @@ eliminate_dead_code () compute_bb_for_insn (max_insn_uid); /* Compute control dependence. */ - postdominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - compute_flow_dominators (NULL, postdominators); pdom = (int *) xmalloc (n_basic_blocks * sizeof (int)); for (i = 0; i < n_basic_blocks; ++i) pdom[i] = INVALID_BLOCK; - compute_immediate_postdominators (pdom, postdominators); + calculate_dominance_info (pdom, NULL, CDI_POST_DOMINATORS); /* Assume there is a path from each node to the exit block. */ for (i = 0; i < n_basic_blocks; ++i) if (pdom[i] == INVALID_BLOCK) pdom[i] = EXIT_BLOCK; - sbitmap_vector_free (postdominators); el = create_edge_list(); find_all_control_dependences (el, pdom, cdbte); diff --git a/gcc/dominance.c b/gcc/dominance.c new file mode 100644 index 0000000..66ff11e --- /dev/null +++ b/gcc/dominance.c @@ -0,0 +1,622 @@ +/* Calculate (post)dominators in slightly super-linear time. + Copyright (C) 2000 Free Software Foundation, Inc. + Contributed by Michael Matz (matz@ifh.de). + + This file is part of GNU CC. + + GNU CC is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2, or (at your option) + any later version. + + GNU CC is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with GNU CC; see the file COPYING. If not, write to + the Free Software Foundation, 59 Temple Place - Suite 330, + Boston, MA 02111-1307, USA. */ + +/* This file implements the well known algorithm from Lengauer and Tarjan + to compute the dominators in a control flow graph. A basic block D is said + to dominate another block X, when all paths from the entry node of the CFG + to X go also over D. The dominance relation is a transitive reflexive + relation and its minimal transitive reduction is a tree, called the + dominator tree. So for each block X besides the entry block exists a + block I(X), called the immediate dominator of X, which is the parent of X + in the dominator tree. + + The algorithm computes this dominator tree implicitely by computing for + each block its immediate dominator. We use tree balancing and path + compression, so its the O(e*a(e,v)) variant, where a(e,v) is the very + slowly growing functional inverse of the Ackerman function. */ + +#include "config.h" +#include "system.h" +#include "rtl.h" +#include "hard-reg-set.h" +#include "basic-block.h" + + +/* We name our nodes with integers, beginning with 1. Zero is reserved for + 'undefined' or 'end of list'. The name of each node is given by the dfs + number of the corresponding basic block. Please note, that we include the + artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to + support multiple entry points. As it has no real basic block index we use + 'n_basic_blocks' for that. Its dfs number is of course 1. */ + +/* Type of Basic Block aka. TBB */ +typedef unsigned int TBB; + +/* We work in a poor-mans object oriented fashion, and carry an instance of + this structure through all our 'methods'. It holds various arrays + reflecting the (sub)structure of the flowgraph. Most of them are of type + TBB and are also indexed by TBB. */ + +struct dom_info +{ + /* The parent of a node in the DFS tree. */ + TBB *dfs_parent; + /* For a node x key[x] is roughly the node nearest to the root from which + exists a way to x only over nodes behind x. Such a node is also called + semidominator. */ + TBB *key; + /* The value in path_min[x] is the node y on the path from x to the root of + the tree x is in with the smallest key[y]. */ + TBB *path_min; + /* bucket[x] points to the first node of the set of nodes having x as key. */ + TBB *bucket; + /* And next_bucket[x] points to the next node. */ + TBB *next_bucket; + /* After the algorithm is done, dom[x] contains the immediate dominator + of x. */ + TBB *dom; + + /* The following few fields implement the structures needed for disjoint + sets. */ + /* set_chain[x] is the next node on the path from x to the representant + of the set containing x. If set_chain[x]==0 then x is a root. */ + TBB *set_chain; + /* set_size[x] is the number of elements in the set named by x. */ + unsigned int *set_size; + /* set_child[x] is used for balancing the tree representing a set. It can + be understood as the next sibling of x. */ + TBB *set_child; + + /* If b is the number of a basic block (BB->index), dfs_order[b] is the + number of that node in DFS order counted from 1. This is an index + into most of the other arrays in this structure. */ + TBB *dfs_order; + /* If x is the DFS-index of a node which correspondends with an basic block, + dfs_to_bb[x] is that basic block. Note, that in our structure there are + more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb + is true for every basic block bb, but not the opposite. */ + basic_block *dfs_to_bb; + + /* This is the next free DFS number when creating the DFS tree or forest. */ + unsigned int dfsnum; + /* The number of nodes in the DFS tree (==dfsnum-1). */ + unsigned int nodes; +}; + +static void init_dom_info PARAMS ((struct dom_info *)); +static void free_dom_info PARAMS ((struct dom_info *)); +static void calc_dfs_tree_nonrec PARAMS ((struct dom_info *, + basic_block, + enum cdi_direction)); +static void calc_dfs_tree PARAMS ((struct dom_info *, + enum cdi_direction)); +static void compress PARAMS ((struct dom_info *, TBB)); +static TBB eval PARAMS ((struct dom_info *, TBB)); +static void link_roots PARAMS ((struct dom_info *, TBB, TBB)); +static void calc_idoms PARAMS ((struct dom_info *, + enum cdi_direction)); +static void idoms_to_doms PARAMS ((struct dom_info *, + sbitmap *)); + +/* Helper macro for allocating and initializing an array, + for aesthetic reasons. */ +#define init_ar(var, type, num, content) \ + do { \ + unsigned int i = 1; /* Catch content == i. */ \ + if (! (content)) \ + (var) = (type *) xcalloc ((num), sizeof (type)); \ + else \ + { \ + (var) = (type *) xmalloc ((num) * sizeof (type)); \ + for (i = 0; i < num; i++) \ + (var)[i] = (content); \ + } \ + } while (0) + +/* Allocate all needed memory in a pessimistic fashion (so we round up). + This initialises the contents of DI, which already must be allocated. */ + +static void +init_dom_info (di) + struct dom_info *di; +{ + /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or + EXIT_BLOCK. */ + unsigned int num = n_basic_blocks + 1 + 1; + init_ar (di->dfs_parent, TBB, num, 0); + init_ar (di->path_min, TBB, num, i); + init_ar (di->key, TBB, num, i); + init_ar (di->dom, TBB, num, 0); + + init_ar (di->bucket, TBB, num, 0); + init_ar (di->next_bucket, TBB, num, 0); + + init_ar (di->set_chain, TBB, num, 0); + init_ar (di->set_size, unsigned int, num, 1); + init_ar (di->set_child, TBB, num, 0); + + init_ar (di->dfs_order, TBB, (unsigned int) n_basic_blocks + 1, 0); + init_ar (di->dfs_to_bb, basic_block, num, 0); + + di->dfsnum = 1; + di->nodes = 0; +} + +#undef init_ar + +/* Free all allocated memory in DI, but not DI itself. */ + +static void +free_dom_info (di) + struct dom_info *di; +{ + free (di->dfs_parent); + free (di->path_min); + free (di->key); + free (di->dom); + free (di->bucket); + free (di->next_bucket); + free (di->set_chain); + free (di->set_size); + free (di->set_child); + free (di->dfs_order); + free (di->dfs_to_bb); +} + +/* The nonrecursive variant of creating a DFS tree. DI is our working + structure, BB the starting basic block for this tree and REVERSE + is true, if predecessors should be visited instead of successors of a + node. After this is done all nodes reachable from BB were visited, have + assigned their dfs number and are linked together to form a tree. */ + +static void +calc_dfs_tree_nonrec (di, bb, reverse) + struct dom_info *di; + basic_block bb; + enum cdi_direction reverse; +{ + /* We never call this with bb==EXIT_BLOCK_PTR (ENTRY_BLOCK_PTR if REVERSE). */ + /* We call this _only_ if bb is not already visited. */ + edge e; + TBB child_i, my_i = 0; + edge *stack; + int sp; + /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward + problem). */ + basic_block en_block; + /* Ending block. */ + basic_block ex_block; + + stack = (edge *) xmalloc ((n_basic_blocks + 3) * sizeof (edge)); + sp = 0; + + /* Initialize our border blocks, and the first edge. */ + if (reverse) + { + e = bb->pred; + en_block = EXIT_BLOCK_PTR; + ex_block = ENTRY_BLOCK_PTR; + } + else + { + e = bb->succ; + en_block = ENTRY_BLOCK_PTR; + ex_block = EXIT_BLOCK_PTR; + } + + /* When the stack is empty we break out of this loop. */ + while (1) + { + basic_block bn; + + /* This loop traverses edges e in depth first manner, and fills the + stack. */ + while (e) + { + edge e_next; + + /* Deduce from E the current and the next block (BB and BN), and the + next edge. */ + if (reverse) + { + bn = e->src; + + /* If the next node BN is either already visited or a border + block the current edge is useless, and simply overwritten + with the next edge out of the current node. */ + if (di->dfs_order[bn->index] || bn == ex_block) + { + e = e->pred_next; + continue; + } + bb = e->dest; + e_next = bn->pred; + } + else + { + bn = e->dest; + if (di->dfs_order[bn->index] || bn == ex_block) + { + e = e->succ_next; + continue; + } + bb = e->src; + e_next = bn->succ; + } + + if (bn == en_block) + abort (); + + /* Fill the DFS tree info calculatable _before_ recursing. */ + if (bb != en_block) + my_i = di->dfs_order[bb->index]; + else + my_i = di->dfs_order[n_basic_blocks]; + child_i = di->dfs_order[bn->index] = di->dfsnum++; + di->dfs_to_bb[child_i] = bn; + di->dfs_parent[child_i] = my_i; + + /* Save the current point in the CFG on the stack, and recurse. */ + stack[sp++] = e; + e = e_next; + } + + if (!sp) + break; + e = stack[--sp]; + + /* OK. The edge-list was exhausted, meaning normally we would + end the recursion. After returning from the recursive call, + there were (may be) other statements which were run after a + child node was completely considered by DFS. Here is the + point to do it in the non-recursive variant. + E.g. The block just completed is in e->dest for forward DFS, + the block not yet completed (the parent of the one above) + in e->src. This could be used e.g. for computing the number of + descendants or the tree depth. */ + if (reverse) + e = e->pred_next; + else + e = e->succ_next; + } + free (stack); +} + +/* The main entry for calculating the DFS tree or forest. DI is our working + structure and REVERSE is true, if we are interested in the reverse flow + graph. In that case the result is not necessarily a tree but a forest, + because there may be nodes from which the EXIT_BLOCK is unreachable. */ + +static void +calc_dfs_tree (di, reverse) + struct dom_info *di; + enum cdi_direction reverse; +{ + /* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */ + basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR; + di->dfs_order[n_basic_blocks] = di->dfsnum; + di->dfs_to_bb[di->dfsnum] = begin; + di->dfsnum++; + + calc_dfs_tree_nonrec (di, begin, reverse); + + if (reverse) + { + /* In the post-dom case we may have nodes without a path to EXIT_BLOCK. + They are reverse-unreachable. In the dom-case we disallow such + nodes, but in post-dom we have to deal with them, so we simply + include them in the DFS tree which actually becomes a forest. */ + int i; + for (i = n_basic_blocks - 1; i >= 0; i--) + { + basic_block b = BASIC_BLOCK (i); + if (di->dfs_order[b->index]) + continue; + di->dfs_order[b->index] = di->dfsnum; + di->dfs_to_bb[di->dfsnum] = b; + di->dfsnum++; + calc_dfs_tree_nonrec (di, b, reverse); + } + } + + di->nodes = di->dfsnum - 1; + + /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */ + if (di->nodes != (unsigned int) n_basic_blocks + 1) + abort (); +} + +/* Compress the path from V to the root of its set and update path_min at the + same time. After compress(di, V) set_chain[V] is the root of the set V is + in and path_min[V] is the node with the smallest key[] value on the path + from V to that root. */ + +static void +compress (di, v) + struct dom_info *di; + TBB v; +{ + /* Btw. It's not worth to unrecurse compress() as the depth is usually not + greater than 5 even for huge graphs (I've not seen call depth > 4). + Also performance wise compress() ranges _far_ behind eval(). */ + TBB parent = di->set_chain[v]; + if (di->set_chain[parent]) + { + compress (di, parent); + if (di->key[di->path_min[parent]] < di->key[di->path_min[v]]) + di->path_min[v] = di->path_min[parent]; + di->set_chain[v] = di->set_chain[parent]; + } +} + +/* Compress the path from V to the set root of V if needed (when the root has + changed since the last call). Returns the node with the smallest key[] + value on the path from V to the root. */ + +static inline TBB +eval (di, v) + struct dom_info *di; + TBB v; +{ + /* The representant of the set V is in, also called root (as the set + representation is a tree). */ + TBB rep = di->set_chain[v]; + + /* V itself is the root. */ + if (!rep) + return di->path_min[v]; + + /* Compress only if necessary. */ + if (di->set_chain[rep]) + { + compress (di, v); + rep = di->set_chain[v]; + } + + if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]]) + return di->path_min[v]; + else + return di->path_min[rep]; +} + +/* This essentially merges the two sets of V and W, giving a single set with + the new root V. The internal representation of these disjoint sets is a + balanced tree. Currently link(V,W) is only used with V being the parent + of W. */ + +static void +link_roots (di, v, w) + struct dom_info *di; + TBB v, w; +{ + TBB s = w; + + /* Rebalance the tree. */ + while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]]) + { + if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]] + >= 2 * di->set_size[di->set_child[s]]) + { + di->set_chain[di->set_child[s]] = s; + di->set_child[s] = di->set_child[di->set_child[s]]; + } + else + { + di->set_size[di->set_child[s]] = di->set_size[s]; + s = di->set_chain[s] = di->set_child[s]; + } + } + + di->path_min[s] = di->path_min[w]; + di->set_size[v] += di->set_size[w]; + if (di->set_size[v] < 2 * di->set_size[w]) + { + TBB tmp = s; + s = di->set_child[v]; + di->set_child[v] = tmp; + } + + /* Merge all subtrees. */ + while (s) + { + di->set_chain[s] = v; + s = di->set_child[s]; + } +} + +/* This calculates the immediate dominators (or post-dominators if REVERSE is + true). DI is our working structure and should hold the DFS forest. + On return the immediate dominator to node V is in di->dom[V]. */ + +static void +calc_idoms (di, reverse) + struct dom_info *di; + enum cdi_direction reverse; +{ + TBB v, w, k, par; + basic_block en_block; + if (reverse) + en_block = EXIT_BLOCK_PTR; + else + en_block = ENTRY_BLOCK_PTR; + + /* Go backwards in DFS order, to first look at the leafs. */ + v = di->nodes; + while (v > 1) + { + basic_block bb = di->dfs_to_bb[v]; + edge e, e_next; + + par = di->dfs_parent[v]; + k = v; + if (reverse) + e = bb->succ; + else + e = bb->pred; + + /* Search all direct predecessors for the smallest node with a path + to them. That way we have the smallest node with also a path to + us only over nodes behind us. In effect we search for our + semidominator. */ + for (; e; e = e_next) + { + TBB k1; + basic_block b; + + if (reverse) + { + b = e->dest; + e_next = e->succ_next; + } + else + { + b = e->src; + e_next = e->pred_next; + } + if (b == en_block) + k1 = di->dfs_order[n_basic_blocks]; + else + k1 = di->dfs_order[b->index]; + + /* Call eval() only if really needed. If k1 is above V in DFS tree, + then we know, that eval(k1) == k1 and key[k1] == k1. */ + if (k1 > v) + k1 = di->key[eval (di, k1)]; + if (k1 < k) + k = k1; + } + + di->key[v] = k; + link_roots (di, par, v); + di->next_bucket[v] = di->bucket[k]; + di->bucket[k] = v; + + /* Transform semidominators into dominators. */ + for (w = di->bucket[par]; w; w = di->next_bucket[w]) + { + k = eval (di, w); + if (di->key[k] < di->key[w]) + di->dom[w] = k; + else + di->dom[w] = par; + } + /* We don't need to cleanup next_bucket[]. */ + di->bucket[par] = 0; + v--; + } + + /* Explicitely define the dominators. */ + di->dom[1] = 0; + for (v = 2; v <= di->nodes; v++) + if (di->dom[v] != di->key[v]) + di->dom[v] = di->dom[di->dom[v]]; +} + +/* Convert the information about immediate dominators (in DI) to sets of all + dominators (in DOMINATORS). */ + +static void +idoms_to_doms (di, dominators) + struct dom_info *di; + sbitmap *dominators; +{ + TBB i, e_index; + int bb, bb_idom; + sbitmap_vector_zero (dominators, n_basic_blocks); + /* We have to be careful, to not include the ENTRY_BLOCK or EXIT_BLOCK + in the list of (post)-doms, so remember that in e_index. */ + e_index = di->dfs_order[n_basic_blocks]; + + for (i = 1; i <= di->nodes; i++) + { + if (i == e_index) + continue; + bb = di->dfs_to_bb[i]->index; + + if (di->dom[i] && (di->dom[i] != e_index)) + { + bb_idom = di->dfs_to_bb[di->dom[i]]->index; + sbitmap_copy (dominators[bb], dominators[bb_idom]); + } + else + { + /* It has no immediate dom or only ENTRY_BLOCK or EXIT_BLOCK. + If it is a child of ENTRY_BLOCK that's OK, and it's only + dominated by itself; if it's _not_ a child of ENTRY_BLOCK, it + means, it is unreachable. That case has been disallowed in the + building of the DFS tree, so we are save here. For the reverse + flow graph it means, it has no children, so, to be compatible + with the old code, we set the post_dominators to all one. */ + if (!di->dom[i]) + { + sbitmap_ones (dominators[bb]); + } + } + SET_BIT (dominators[bb], bb); + } +} + +/* The main entry point into this module. IDOM is an integer array with room + for n_basic_blocks integers, DOMS is a preallocated sbitmap array having + room for n_basic_blocks^2 bits, and POST is true if the caller wants to + know post-dominators. + + On return IDOM[i] will be the BB->index of the immediate (post) dominator + of basic block i, and DOMS[i] will have set bit j if basic block j is a + (post)dominator for block i. + + Either IDOM or DOMS may be NULL (meaning the caller is not interested in + immediate resp. all dominators). */ + +void +calculate_dominance_info (idom, doms, reverse) + int *idom; + sbitmap *doms; + enum cdi_direction reverse; +{ + struct dom_info di; + + if (!doms && !idom) + return; + init_dom_info (&di); + calc_dfs_tree (&di, reverse); + calc_idoms (&di, reverse); + + if (idom) + { + int i; + for (i = 0; i < n_basic_blocks; i++) + { + basic_block b = BASIC_BLOCK (i); + TBB d = di.dom[di.dfs_order[b->index]]; + + /* The old code didn't modify array elements of nodes having only + itself as dominator (d==0) or only ENTRY_BLOCK (resp. EXIT_BLOCK) + (d==1). */ + if (d > 1) + idom[i] = di.dfs_to_bb[d]->index; + } + } + if (doms) + idoms_to_doms (&di, doms); + + free_dom_info (&di); +} diff --git a/gcc/flow.c b/gcc/flow.c index 4fc8ac3..23f3236 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -6247,250 +6247,6 @@ print_rtl_with_bb (outf, rtx_first) } } -/* Compute dominator relationships using new flow graph structures. */ - -void -compute_flow_dominators (dominators, post_dominators) - sbitmap *dominators; - sbitmap *post_dominators; -{ - int bb; - sbitmap *temp_bitmap; - edge e; - basic_block *worklist, *workend, *qin, *qout; - int qlen; - - /* Allocate a worklist array/queue. Entries are only added to the - list if they were not already on the list. So the size is - bounded by the number of basic blocks. */ - worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks); - workend = &worklist[n_basic_blocks]; - - temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - sbitmap_vector_zero (temp_bitmap, n_basic_blocks); - - if (dominators) - { - /* The optimistic setting of dominators requires us to put every - block on the work list initially. */ - qin = qout = worklist; - for (bb = 0; bb < n_basic_blocks; bb++) - { - *qin++ = BASIC_BLOCK (bb); - BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb); - } - qlen = n_basic_blocks; - qin = worklist; - - /* We want a maximal solution, so initially assume everything dominates - everything else. */ - sbitmap_vector_ones (dominators, n_basic_blocks); - - /* Mark successors of the entry block so we can identify them below. */ - for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next) - e->dest->aux = ENTRY_BLOCK_PTR; - - /* Iterate until the worklist is empty. */ - while (qlen) - { - /* Take the first entry off the worklist. */ - basic_block b = *qout++; - if (qout >= workend) - qout = worklist; - qlen--; - - bb = b->index; - - /* Compute the intersection of the dominators of all the - predecessor blocks. - - If one of the predecessor blocks is the ENTRY block, then the - intersection of the dominators of the predecessor blocks is - defined as the null set. We can identify such blocks by the - special value in the AUX field in the block structure. */ - if (b->aux == ENTRY_BLOCK_PTR) - { - /* Do not clear the aux field for blocks which are - successors of the ENTRY block. That way we never add - them to the worklist again. - - The intersect of dominators of the preds of this block is - defined as the null set. */ - sbitmap_zero (temp_bitmap[bb]); - } - else - { - /* Clear the aux field of this block so it can be added to - the worklist again if necessary. */ - b->aux = NULL; - sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb); - } - - /* Make sure each block always dominates itself. */ - SET_BIT (temp_bitmap[bb], bb); - - /* If the out state of this block changed, then we need to - add the successors of this block to the worklist if they - are not already on the worklist. */ - if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb])) - { - for (e = b->succ; e; e = e->succ_next) - { - if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR) - { - *qin++ = e->dest; - if (qin >= workend) - qin = worklist; - qlen++; - - e->dest->aux = e; - } - } - } - } - } - - if (post_dominators) - { - /* The optimistic setting of dominators requires us to put every - block on the work list initially. */ - qin = qout = worklist; - for (bb = 0; bb < n_basic_blocks; bb++) - { - *qin++ = BASIC_BLOCK (bb); - BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb); - } - qlen = n_basic_blocks; - qin = worklist; - - /* We want a maximal solution, so initially assume everything post - dominates everything else. */ - sbitmap_vector_ones (post_dominators, n_basic_blocks); - - /* Mark predecessors of the exit block so we can identify them below. */ - for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next) - e->src->aux = EXIT_BLOCK_PTR; - - /* Iterate until the worklist is empty. */ - while (qlen) - { - /* Take the first entry off the worklist. */ - basic_block b = *qout++; - if (qout >= workend) - qout = worklist; - qlen--; - - bb = b->index; - - /* Compute the intersection of the post dominators of all the - successor blocks. - - If one of the successor blocks is the EXIT block, then the - intersection of the dominators of the successor blocks is - defined as the null set. We can identify such blocks by the - special value in the AUX field in the block structure. */ - if (b->aux == EXIT_BLOCK_PTR) - { - /* Do not clear the aux field for blocks which are - predecessors of the EXIT block. That way we we never - add them to the worklist again. - - The intersect of dominators of the succs of this block is - defined as the null set. */ - sbitmap_zero (temp_bitmap[bb]); - } - else - { - /* Clear the aux field of this block so it can be added to - the worklist again if necessary. */ - b->aux = NULL; - sbitmap_intersection_of_succs (temp_bitmap[bb], - post_dominators, bb); - } - - /* Make sure each block always post dominates itself. */ - SET_BIT (temp_bitmap[bb], bb); - - /* If the out state of this block changed, then we need to - add the successors of this block to the worklist if they - are not already on the worklist. */ - if (sbitmap_a_and_b (post_dominators[bb], - post_dominators[bb], - temp_bitmap[bb])) - { - for (e = b->pred; e; e = e->pred_next) - { - if (!e->src->aux && e->src != ENTRY_BLOCK_PTR) - { - *qin++ = e->src; - if (qin >= workend) - qin = worklist; - qlen++; - - e->src->aux = e; - } - } - } - } - } - - free (worklist); - free (temp_bitmap); -} - -/* Given DOMINATORS, compute the immediate dominators into IDOM. If a - block dominates only itself, its entry remains as INVALID_BLOCK. */ - -void -compute_immediate_dominators (idom, dominators) - int *idom; - sbitmap *dominators; -{ - sbitmap *tmp; - int b; - - tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - - /* Begin with tmp(n) = dom(n) - { n }. */ - for (b = n_basic_blocks; --b >= 0;) - { - sbitmap_copy (tmp[b], dominators[b]); - RESET_BIT (tmp[b], b); - } - - /* Subtract out all of our dominator's dominators. */ - for (b = n_basic_blocks; --b >= 0;) - { - sbitmap tmp_b = tmp[b]; - int s; - - for (s = n_basic_blocks; --s >= 0;) - if (TEST_BIT (tmp_b, s)) - sbitmap_difference (tmp_b, tmp_b, tmp[s]); - } - - /* Find the one bit set in the bitmap and put it in the output array. */ - for (b = n_basic_blocks; --b >= 0;) - { - int t; - EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; }); - } - - sbitmap_vector_free (tmp); -} - -/* Given POSTDOMINATORS, compute the immediate postdominators into - IDOM. If a block is only dominated by itself, its entry remains as - INVALID_BLOCK. */ - -void -compute_immediate_postdominators (idom, postdominators) - int *idom; - sbitmap *postdominators; -{ - compute_immediate_dominators (idom, postdominators); -} - /* Recompute register set/reference counts immediately prior to register allocation. @@ -8151,7 +7907,7 @@ flow_loops_find (loops, flags) /* Compute the dominators. */ dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - compute_flow_dominators (dom, NULL); + calculate_dominance_info (NULL, dom, CDI_DOMINATORS); /* Count the number of loop edges (back edges). This should be the same as the number of natural loops. */ diff --git a/gcc/gcse.c b/gcc/gcse.c index 2938597..ac87c93 100644 --- a/gcc/gcse.c +++ b/gcc/gcse.c @@ -5292,7 +5292,7 @@ compute_code_hoist_data () compute_local_properties (transp, comp, antloc, 0); compute_transpout (); compute_code_hoist_vbeinout (); - compute_flow_dominators (dominators, NULL); + calculate_dominance_info (NULL, dominators, CDI_DOMINATORS); if (gcse_file) fprintf (gcse_file, "\n"); } diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c index 2ab6377..01f08b5 100644 --- a/gcc/haifa-sched.c +++ b/gcc/haifa-sched.c @@ -7001,10 +7001,8 @@ schedule_insns (dump_file) so may even be beneficial. */ edge_list = create_edge_list (); - /* Compute the dominators and post dominators. We don't - currently use post dominators, but we should for - speculative motion analysis. */ - compute_flow_dominators (dom, NULL); + /* Compute the dominators and post dominators. */ + calculate_dominance_info (NULL, dom, CDI_DOMINATORS); /* build_control_flow will return nonzero if it detects unreachable blocks or any other irregularity with the cfg which prevents diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c index 3ca0e6c..6ad1d35 100644 --- a/gcc/ifcvt.c +++ b/gcc/ifcvt.c @@ -2104,7 +2104,7 @@ if_convert (life_data_ok) if (HAVE_conditional_execution || life_data_ok) { post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - compute_flow_dominators (NULL, post_dominators); + calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS); } /* Record initial block numbers. */ diff --git a/gcc/ssa.c b/gcc/ssa.c index 0bc6dc8..3dabc62 100644 --- a/gcc/ssa.c +++ b/gcc/ssa.c @@ -1148,7 +1148,6 @@ convert_to_ssa () sbitmap *evals; /* Dominator bitmaps. */ - sbitmap *dominators; sbitmap *dfs; sbitmap *idfs; @@ -1164,15 +1163,9 @@ convert_to_ssa () /* Need global_live_at_{start,end} up to date. */ life_analysis (get_insns (), NULL, PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE); - /* Compute dominators. */ - dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); - compute_flow_dominators (dominators, NULL); - idom = (int *) alloca (n_basic_blocks * sizeof (int)); memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int)); - compute_immediate_dominators (idom, dominators); - - sbitmap_vector_free (dominators); + calculate_dominance_info (idom, NULL, CDI_DOMINATORS); if (rtl_dump_file) { -- cgit v1.1