/* Calculate (post)dominators in slightly super-linear time.
|
/* Calculate (post)dominators in slightly super-linear time.
|
Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
|
Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
Contributed by Michael Matz (matz@ifh.de).
|
Contributed by Michael Matz (matz@ifh.de).
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it
|
GCC is free software; you can redistribute it and/or modify it
|
under the terms of the GNU General Public License as published by
|
under the terms of the GNU General Public License as published by
|
the Free Software Foundation; either version 3, or (at your option)
|
the Free Software Foundation; either version 3, or (at your option)
|
any later version.
|
any later version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT
|
GCC is distributed in the hope that it will be useful, but WITHOUT
|
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
|
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
|
License for more details.
|
License for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
/* This file implements the well known algorithm from Lengauer and Tarjan
|
/* 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 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 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
|
to X go also over D. The dominance relation is a transitive reflexive
|
relation and its minimal transitive reduction is a tree, called the
|
relation and its minimal transitive reduction is a tree, called the
|
dominator tree. So for each block X besides the entry block exists a
|
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
|
block I(X), called the immediate dominator of X, which is the parent of X
|
in the dominator tree.
|
in the dominator tree.
|
|
|
The algorithm computes this dominator tree implicitly by computing for
|
The algorithm computes this dominator tree implicitly by computing for
|
each block its immediate dominator. We use tree balancing and path
|
each block its immediate dominator. We use tree balancing and path
|
compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
|
compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
|
slowly growing functional inverse of the Ackerman function. */
|
slowly growing functional inverse of the Ackerman function. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "hard-reg-set.h"
|
#include "hard-reg-set.h"
|
#include "obstack.h"
|
#include "obstack.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "toplev.h"
|
#include "toplev.h"
|
#include "et-forest.h"
|
#include "et-forest.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "vecprim.h"
|
#include "vecprim.h"
|
#include "pointer-set.h"
|
#include "pointer-set.h"
|
#include "graphds.h"
|
#include "graphds.h"
|
|
|
/* We name our nodes with integers, beginning with 1. Zero is reserved for
|
/* 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
|
'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
|
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
|
artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
|
support multiple entry points. Its dfs number is of course 1. */
|
support multiple entry points. Its dfs number is of course 1. */
|
|
|
/* Type of Basic Block aka. TBB */
|
/* Type of Basic Block aka. TBB */
|
typedef unsigned int TBB;
|
typedef unsigned int TBB;
|
|
|
/* We work in a poor-mans object oriented fashion, and carry an instance of
|
/* We work in a poor-mans object oriented fashion, and carry an instance of
|
this structure through all our 'methods'. It holds various arrays
|
this structure through all our 'methods'. It holds various arrays
|
reflecting the (sub)structure of the flowgraph. Most of them are of type
|
reflecting the (sub)structure of the flowgraph. Most of them are of type
|
TBB and are also indexed by TBB. */
|
TBB and are also indexed by TBB. */
|
|
|
struct dom_info
|
struct dom_info
|
{
|
{
|
/* The parent of a node in the DFS tree. */
|
/* The parent of a node in the DFS tree. */
|
TBB *dfs_parent;
|
TBB *dfs_parent;
|
/* For a node x key[x] is roughly the node nearest to the root from which
|
/* 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
|
exists a way to x only over nodes behind x. Such a node is also called
|
semidominator. */
|
semidominator. */
|
TBB *key;
|
TBB *key;
|
/* The value in path_min[x] is the node y on the path from x to the root of
|
/* 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]. */
|
the tree x is in with the smallest key[y]. */
|
TBB *path_min;
|
TBB *path_min;
|
/* bucket[x] points to the first node of the set of nodes having x as key. */
|
/* bucket[x] points to the first node of the set of nodes having x as key. */
|
TBB *bucket;
|
TBB *bucket;
|
/* And next_bucket[x] points to the next node. */
|
/* And next_bucket[x] points to the next node. */
|
TBB *next_bucket;
|
TBB *next_bucket;
|
/* After the algorithm is done, dom[x] contains the immediate dominator
|
/* After the algorithm is done, dom[x] contains the immediate dominator
|
of x. */
|
of x. */
|
TBB *dom;
|
TBB *dom;
|
|
|
/* The following few fields implement the structures needed for disjoint
|
/* The following few fields implement the structures needed for disjoint
|
sets. */
|
sets. */
|
/* set_chain[x] is the next node on the path from x to the representative
|
/* set_chain[x] is the next node on the path from x to the representative
|
of the set containing x. If set_chain[x]==0 then x is a root. */
|
of the set containing x. If set_chain[x]==0 then x is a root. */
|
TBB *set_chain;
|
TBB *set_chain;
|
/* set_size[x] is the number of elements in the set named by x. */
|
/* set_size[x] is the number of elements in the set named by x. */
|
unsigned int *set_size;
|
unsigned int *set_size;
|
/* set_child[x] is used for balancing the tree representing a set. It can
|
/* set_child[x] is used for balancing the tree representing a set. It can
|
be understood as the next sibling of x. */
|
be understood as the next sibling of x. */
|
TBB *set_child;
|
TBB *set_child;
|
|
|
/* If b is the number of a basic block (BB->index), dfs_order[b] is the
|
/* 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
|
number of that node in DFS order counted from 1. This is an index
|
into most of the other arrays in this structure. */
|
into most of the other arrays in this structure. */
|
TBB *dfs_order;
|
TBB *dfs_order;
|
/* If x is the DFS-index of a node which corresponds with a basic block,
|
/* If x is the DFS-index of a node which corresponds with a basic block,
|
dfs_to_bb[x] is that basic block. Note, that in our structure there are
|
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
|
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. */
|
is true for every basic block bb, but not the opposite. */
|
basic_block *dfs_to_bb;
|
basic_block *dfs_to_bb;
|
|
|
/* This is the next free DFS number when creating the DFS tree. */
|
/* This is the next free DFS number when creating the DFS tree. */
|
unsigned int dfsnum;
|
unsigned int dfsnum;
|
/* The number of nodes in the DFS tree (==dfsnum-1). */
|
/* The number of nodes in the DFS tree (==dfsnum-1). */
|
unsigned int nodes;
|
unsigned int nodes;
|
|
|
/* Blocks with bits set here have a fake edge to EXIT. These are used
|
/* Blocks with bits set here have a fake edge to EXIT. These are used
|
to turn a DFS forest into a proper tree. */
|
to turn a DFS forest into a proper tree. */
|
bitmap fake_exit_edge;
|
bitmap fake_exit_edge;
|
};
|
};
|
|
|
static void init_dom_info (struct dom_info *, enum cdi_direction);
|
static void init_dom_info (struct dom_info *, enum cdi_direction);
|
static void free_dom_info (struct dom_info *);
|
static void free_dom_info (struct dom_info *);
|
static void calc_dfs_tree_nonrec (struct dom_info *, basic_block, bool);
|
static void calc_dfs_tree_nonrec (struct dom_info *, basic_block, bool);
|
static void calc_dfs_tree (struct dom_info *, bool);
|
static void calc_dfs_tree (struct dom_info *, bool);
|
static void compress (struct dom_info *, TBB);
|
static void compress (struct dom_info *, TBB);
|
static TBB eval (struct dom_info *, TBB);
|
static TBB eval (struct dom_info *, TBB);
|
static void link_roots (struct dom_info *, TBB, TBB);
|
static void link_roots (struct dom_info *, TBB, TBB);
|
static void calc_idoms (struct dom_info *, bool);
|
static void calc_idoms (struct dom_info *, bool);
|
void debug_dominance_info (enum cdi_direction);
|
void debug_dominance_info (enum cdi_direction);
|
void debug_dominance_tree (enum cdi_direction, basic_block);
|
void debug_dominance_tree (enum cdi_direction, basic_block);
|
|
|
/* Helper macro for allocating and initializing an array,
|
/* Helper macro for allocating and initializing an array,
|
for aesthetic reasons. */
|
for aesthetic reasons. */
|
#define init_ar(var, type, num, content) \
|
#define init_ar(var, type, num, content) \
|
do \
|
do \
|
{ \
|
{ \
|
unsigned int i = 1; /* Catch content == i. */ \
|
unsigned int i = 1; /* Catch content == i. */ \
|
if (! (content)) \
|
if (! (content)) \
|
(var) = XCNEWVEC (type, num); \
|
(var) = XCNEWVEC (type, num); \
|
else \
|
else \
|
{ \
|
{ \
|
(var) = XNEWVEC (type, (num)); \
|
(var) = XNEWVEC (type, (num)); \
|
for (i = 0; i < num; i++) \
|
for (i = 0; i < num; i++) \
|
(var)[i] = (content); \
|
(var)[i] = (content); \
|
} \
|
} \
|
} \
|
} \
|
while (0)
|
while (0)
|
|
|
/* Allocate all needed memory in a pessimistic fashion (so we round up).
|
/* Allocate all needed memory in a pessimistic fashion (so we round up).
|
This initializes the contents of DI, which already must be allocated. */
|
This initializes the contents of DI, which already must be allocated. */
|
|
|
static void
|
static void
|
init_dom_info (struct dom_info *di, enum cdi_direction dir)
|
init_dom_info (struct dom_info *di, enum cdi_direction dir)
|
{
|
{
|
/* We need memory for n_basic_blocks nodes. */
|
/* We need memory for n_basic_blocks nodes. */
|
unsigned int num = n_basic_blocks;
|
unsigned int num = n_basic_blocks;
|
init_ar (di->dfs_parent, TBB, num, 0);
|
init_ar (di->dfs_parent, TBB, num, 0);
|
init_ar (di->path_min, TBB, num, i);
|
init_ar (di->path_min, TBB, num, i);
|
init_ar (di->key, TBB, num, i);
|
init_ar (di->key, TBB, num, i);
|
init_ar (di->dom, TBB, num, 0);
|
init_ar (di->dom, TBB, num, 0);
|
|
|
init_ar (di->bucket, TBB, num, 0);
|
init_ar (di->bucket, TBB, num, 0);
|
init_ar (di->next_bucket, TBB, num, 0);
|
init_ar (di->next_bucket, TBB, num, 0);
|
|
|
init_ar (di->set_chain, TBB, num, 0);
|
init_ar (di->set_chain, TBB, num, 0);
|
init_ar (di->set_size, unsigned int, num, 1);
|
init_ar (di->set_size, unsigned int, num, 1);
|
init_ar (di->set_child, TBB, num, 0);
|
init_ar (di->set_child, TBB, num, 0);
|
|
|
init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0);
|
init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0);
|
init_ar (di->dfs_to_bb, basic_block, num, 0);
|
init_ar (di->dfs_to_bb, basic_block, num, 0);
|
|
|
di->dfsnum = 1;
|
di->dfsnum = 1;
|
di->nodes = 0;
|
di->nodes = 0;
|
|
|
switch (dir)
|
switch (dir)
|
{
|
{
|
case CDI_DOMINATORS:
|
case CDI_DOMINATORS:
|
di->fake_exit_edge = NULL;
|
di->fake_exit_edge = NULL;
|
break;
|
break;
|
case CDI_POST_DOMINATORS:
|
case CDI_POST_DOMINATORS:
|
di->fake_exit_edge = BITMAP_ALLOC (NULL);
|
di->fake_exit_edge = BITMAP_ALLOC (NULL);
|
break;
|
break;
|
default:
|
default:
|
gcc_unreachable ();
|
gcc_unreachable ();
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
#undef init_ar
|
#undef init_ar
|
|
|
/* Map dominance calculation type to array index used for various
|
/* Map dominance calculation type to array index used for various
|
dominance information arrays. This version is simple -- it will need
|
dominance information arrays. This version is simple -- it will need
|
to be modified, obviously, if additional values are added to
|
to be modified, obviously, if additional values are added to
|
cdi_direction. */
|
cdi_direction. */
|
|
|
static unsigned int
|
static unsigned int
|
dom_convert_dir_to_idx (enum cdi_direction dir)
|
dom_convert_dir_to_idx (enum cdi_direction dir)
|
{
|
{
|
gcc_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
|
gcc_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
|
return dir - 1;
|
return dir - 1;
|
}
|
}
|
|
|
/* Free all allocated memory in DI, but not DI itself. */
|
/* Free all allocated memory in DI, but not DI itself. */
|
|
|
static void
|
static void
|
free_dom_info (struct dom_info *di)
|
free_dom_info (struct dom_info *di)
|
{
|
{
|
free (di->dfs_parent);
|
free (di->dfs_parent);
|
free (di->path_min);
|
free (di->path_min);
|
free (di->key);
|
free (di->key);
|
free (di->dom);
|
free (di->dom);
|
free (di->bucket);
|
free (di->bucket);
|
free (di->next_bucket);
|
free (di->next_bucket);
|
free (di->set_chain);
|
free (di->set_chain);
|
free (di->set_size);
|
free (di->set_size);
|
free (di->set_child);
|
free (di->set_child);
|
free (di->dfs_order);
|
free (di->dfs_order);
|
free (di->dfs_to_bb);
|
free (di->dfs_to_bb);
|
BITMAP_FREE (di->fake_exit_edge);
|
BITMAP_FREE (di->fake_exit_edge);
|
}
|
}
|
|
|
/* The nonrecursive variant of creating a DFS tree. DI is our working
|
/* The nonrecursive variant of creating a DFS tree. DI is our working
|
structure, BB the starting basic block for this tree and REVERSE
|
structure, BB the starting basic block for this tree and REVERSE
|
is true, if predecessors should be visited instead of successors of a
|
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
|
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. */
|
assigned their dfs number and are linked together to form a tree. */
|
|
|
static void
|
static void
|
calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
|
calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
|
{
|
{
|
/* We call this _only_ if bb is not already visited. */
|
/* We call this _only_ if bb is not already visited. */
|
edge e;
|
edge e;
|
TBB child_i, my_i = 0;
|
TBB child_i, my_i = 0;
|
edge_iterator *stack;
|
edge_iterator *stack;
|
edge_iterator ei, einext;
|
edge_iterator ei, einext;
|
int sp;
|
int sp;
|
/* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
|
/* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
|
problem). */
|
problem). */
|
basic_block en_block;
|
basic_block en_block;
|
/* Ending block. */
|
/* Ending block. */
|
basic_block ex_block;
|
basic_block ex_block;
|
|
|
stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
|
stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
|
sp = 0;
|
sp = 0;
|
|
|
/* Initialize our border blocks, and the first edge. */
|
/* Initialize our border blocks, and the first edge. */
|
if (reverse)
|
if (reverse)
|
{
|
{
|
ei = ei_start (bb->preds);
|
ei = ei_start (bb->preds);
|
en_block = EXIT_BLOCK_PTR;
|
en_block = EXIT_BLOCK_PTR;
|
ex_block = ENTRY_BLOCK_PTR;
|
ex_block = ENTRY_BLOCK_PTR;
|
}
|
}
|
else
|
else
|
{
|
{
|
ei = ei_start (bb->succs);
|
ei = ei_start (bb->succs);
|
en_block = ENTRY_BLOCK_PTR;
|
en_block = ENTRY_BLOCK_PTR;
|
ex_block = EXIT_BLOCK_PTR;
|
ex_block = EXIT_BLOCK_PTR;
|
}
|
}
|
|
|
/* When the stack is empty we break out of this loop. */
|
/* When the stack is empty we break out of this loop. */
|
while (1)
|
while (1)
|
{
|
{
|
basic_block bn;
|
basic_block bn;
|
|
|
/* This loop traverses edges e in depth first manner, and fills the
|
/* This loop traverses edges e in depth first manner, and fills the
|
stack. */
|
stack. */
|
while (!ei_end_p (ei))
|
while (!ei_end_p (ei))
|
{
|
{
|
e = ei_edge (ei);
|
e = ei_edge (ei);
|
|
|
/* Deduce from E the current and the next block (BB and BN), and the
|
/* Deduce from E the current and the next block (BB and BN), and the
|
next edge. */
|
next edge. */
|
if (reverse)
|
if (reverse)
|
{
|
{
|
bn = e->src;
|
bn = e->src;
|
|
|
/* If the next node BN is either already visited or a border
|
/* If the next node BN is either already visited or a border
|
block the current edge is useless, and simply overwritten
|
block the current edge is useless, and simply overwritten
|
with the next edge out of the current node. */
|
with the next edge out of the current node. */
|
if (bn == ex_block || di->dfs_order[bn->index])
|
if (bn == ex_block || di->dfs_order[bn->index])
|
{
|
{
|
ei_next (&ei);
|
ei_next (&ei);
|
continue;
|
continue;
|
}
|
}
|
bb = e->dest;
|
bb = e->dest;
|
einext = ei_start (bn->preds);
|
einext = ei_start (bn->preds);
|
}
|
}
|
else
|
else
|
{
|
{
|
bn = e->dest;
|
bn = e->dest;
|
if (bn == ex_block || di->dfs_order[bn->index])
|
if (bn == ex_block || di->dfs_order[bn->index])
|
{
|
{
|
ei_next (&ei);
|
ei_next (&ei);
|
continue;
|
continue;
|
}
|
}
|
bb = e->src;
|
bb = e->src;
|
einext = ei_start (bn->succs);
|
einext = ei_start (bn->succs);
|
}
|
}
|
|
|
gcc_assert (bn != en_block);
|
gcc_assert (bn != en_block);
|
|
|
/* Fill the DFS tree info calculatable _before_ recursing. */
|
/* Fill the DFS tree info calculatable _before_ recursing. */
|
if (bb != en_block)
|
if (bb != en_block)
|
my_i = di->dfs_order[bb->index];
|
my_i = di->dfs_order[bb->index];
|
else
|
else
|
my_i = di->dfs_order[last_basic_block];
|
my_i = di->dfs_order[last_basic_block];
|
child_i = di->dfs_order[bn->index] = di->dfsnum++;
|
child_i = di->dfs_order[bn->index] = di->dfsnum++;
|
di->dfs_to_bb[child_i] = bn;
|
di->dfs_to_bb[child_i] = bn;
|
di->dfs_parent[child_i] = my_i;
|
di->dfs_parent[child_i] = my_i;
|
|
|
/* Save the current point in the CFG on the stack, and recurse. */
|
/* Save the current point in the CFG on the stack, and recurse. */
|
stack[sp++] = ei;
|
stack[sp++] = ei;
|
ei = einext;
|
ei = einext;
|
}
|
}
|
|
|
if (!sp)
|
if (!sp)
|
break;
|
break;
|
ei = stack[--sp];
|
ei = stack[--sp];
|
|
|
/* OK. The edge-list was exhausted, meaning normally we would
|
/* OK. The edge-list was exhausted, meaning normally we would
|
end the recursion. After returning from the recursive call,
|
end the recursion. After returning from the recursive call,
|
there were (may be) other statements which were run after a
|
there were (may be) other statements which were run after a
|
child node was completely considered by DFS. Here is the
|
child node was completely considered by DFS. Here is the
|
point to do it in the non-recursive variant.
|
point to do it in the non-recursive variant.
|
E.g. The block just completed is in e->dest for forward DFS,
|
E.g. The block just completed is in e->dest for forward DFS,
|
the block not yet completed (the parent of the one above)
|
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
|
in e->src. This could be used e.g. for computing the number of
|
descendants or the tree depth. */
|
descendants or the tree depth. */
|
ei_next (&ei);
|
ei_next (&ei);
|
}
|
}
|
free (stack);
|
free (stack);
|
}
|
}
|
|
|
/* The main entry for calculating the DFS tree or forest. DI is our working
|
/* 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
|
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,
|
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. */
|
because there may be nodes from which the EXIT_BLOCK is unreachable. */
|
|
|
static void
|
static void
|
calc_dfs_tree (struct dom_info *di, bool reverse)
|
calc_dfs_tree (struct dom_info *di, bool reverse)
|
{
|
{
|
/* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */
|
/* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */
|
basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
|
basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
|
di->dfs_order[last_basic_block] = di->dfsnum;
|
di->dfs_order[last_basic_block] = di->dfsnum;
|
di->dfs_to_bb[di->dfsnum] = begin;
|
di->dfs_to_bb[di->dfsnum] = begin;
|
di->dfsnum++;
|
di->dfsnum++;
|
|
|
calc_dfs_tree_nonrec (di, begin, reverse);
|
calc_dfs_tree_nonrec (di, begin, reverse);
|
|
|
if (reverse)
|
if (reverse)
|
{
|
{
|
/* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
|
/* 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
|
They are reverse-unreachable. In the dom-case we disallow such
|
nodes, but in post-dom we have to deal with them.
|
nodes, but in post-dom we have to deal with them.
|
|
|
There are two situations in which this occurs. First, noreturn
|
There are two situations in which this occurs. First, noreturn
|
functions. Second, infinite loops. In the first case we need to
|
functions. Second, infinite loops. In the first case we need to
|
pretend that there is an edge to the exit block. In the second
|
pretend that there is an edge to the exit block. In the second
|
case, we wind up with a forest. We need to process all noreturn
|
case, we wind up with a forest. We need to process all noreturn
|
blocks before we know if we've got any infinite loops. */
|
blocks before we know if we've got any infinite loops. */
|
|
|
basic_block b;
|
basic_block b;
|
bool saw_unconnected = false;
|
bool saw_unconnected = false;
|
|
|
FOR_EACH_BB_REVERSE (b)
|
FOR_EACH_BB_REVERSE (b)
|
{
|
{
|
if (EDGE_COUNT (b->succs) > 0)
|
if (EDGE_COUNT (b->succs) > 0)
|
{
|
{
|
if (di->dfs_order[b->index] == 0)
|
if (di->dfs_order[b->index] == 0)
|
saw_unconnected = true;
|
saw_unconnected = true;
|
continue;
|
continue;
|
}
|
}
|
bitmap_set_bit (di->fake_exit_edge, b->index);
|
bitmap_set_bit (di->fake_exit_edge, b->index);
|
di->dfs_order[b->index] = di->dfsnum;
|
di->dfs_order[b->index] = di->dfsnum;
|
di->dfs_to_bb[di->dfsnum] = b;
|
di->dfs_to_bb[di->dfsnum] = b;
|
di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
|
di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
|
di->dfsnum++;
|
di->dfsnum++;
|
calc_dfs_tree_nonrec (di, b, reverse);
|
calc_dfs_tree_nonrec (di, b, reverse);
|
}
|
}
|
|
|
if (saw_unconnected)
|
if (saw_unconnected)
|
{
|
{
|
FOR_EACH_BB_REVERSE (b)
|
FOR_EACH_BB_REVERSE (b)
|
{
|
{
|
if (di->dfs_order[b->index])
|
if (di->dfs_order[b->index])
|
continue;
|
continue;
|
bitmap_set_bit (di->fake_exit_edge, b->index);
|
bitmap_set_bit (di->fake_exit_edge, b->index);
|
di->dfs_order[b->index] = di->dfsnum;
|
di->dfs_order[b->index] = di->dfsnum;
|
di->dfs_to_bb[di->dfsnum] = b;
|
di->dfs_to_bb[di->dfsnum] = b;
|
di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
|
di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
|
di->dfsnum++;
|
di->dfsnum++;
|
calc_dfs_tree_nonrec (di, b, reverse);
|
calc_dfs_tree_nonrec (di, b, reverse);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
di->nodes = di->dfsnum - 1;
|
di->nodes = di->dfsnum - 1;
|
|
|
/* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
|
/* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
|
gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
|
gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
|
}
|
}
|
|
|
/* Compress the path from V to the root of its set and update path_min at the
|
/* 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
|
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
|
in and path_min[V] is the node with the smallest key[] value on the path
|
from V to that root. */
|
from V to that root. */
|
|
|
static void
|
static void
|
compress (struct dom_info *di, TBB v)
|
compress (struct dom_info *di, TBB v)
|
{
|
{
|
/* Btw. It's not worth to unrecurse compress() as the depth is usually not
|
/* 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).
|
greater than 5 even for huge graphs (I've not seen call depth > 4).
|
Also performance wise compress() ranges _far_ behind eval(). */
|
Also performance wise compress() ranges _far_ behind eval(). */
|
TBB parent = di->set_chain[v];
|
TBB parent = di->set_chain[v];
|
if (di->set_chain[parent])
|
if (di->set_chain[parent])
|
{
|
{
|
compress (di, parent);
|
compress (di, parent);
|
if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
|
if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
|
di->path_min[v] = di->path_min[parent];
|
di->path_min[v] = di->path_min[parent];
|
di->set_chain[v] = di->set_chain[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
|
/* 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[]
|
changed since the last call). Returns the node with the smallest key[]
|
value on the path from V to the root. */
|
value on the path from V to the root. */
|
|
|
static inline TBB
|
static inline TBB
|
eval (struct dom_info *di, TBB v)
|
eval (struct dom_info *di, TBB v)
|
{
|
{
|
/* The representative of the set V is in, also called root (as the set
|
/* The representative of the set V is in, also called root (as the set
|
representation is a tree). */
|
representation is a tree). */
|
TBB rep = di->set_chain[v];
|
TBB rep = di->set_chain[v];
|
|
|
/* V itself is the root. */
|
/* V itself is the root. */
|
if (!rep)
|
if (!rep)
|
return di->path_min[v];
|
return di->path_min[v];
|
|
|
/* Compress only if necessary. */
|
/* Compress only if necessary. */
|
if (di->set_chain[rep])
|
if (di->set_chain[rep])
|
{
|
{
|
compress (di, v);
|
compress (di, v);
|
rep = di->set_chain[v];
|
rep = di->set_chain[v];
|
}
|
}
|
|
|
if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
|
if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
|
return di->path_min[v];
|
return di->path_min[v];
|
else
|
else
|
return di->path_min[rep];
|
return di->path_min[rep];
|
}
|
}
|
|
|
/* This essentially merges the two sets of V and W, giving a single set with
|
/* 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
|
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
|
balanced tree. Currently link(V,W) is only used with V being the parent
|
of W. */
|
of W. */
|
|
|
static void
|
static void
|
link_roots (struct dom_info *di, TBB v, TBB w)
|
link_roots (struct dom_info *di, TBB v, TBB w)
|
{
|
{
|
TBB s = w;
|
TBB s = w;
|
|
|
/* Rebalance the tree. */
|
/* Rebalance the tree. */
|
while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
|
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]]]
|
if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
|
>= 2 * di->set_size[di->set_child[s]])
|
>= 2 * di->set_size[di->set_child[s]])
|
{
|
{
|
di->set_chain[di->set_child[s]] = s;
|
di->set_chain[di->set_child[s]] = s;
|
di->set_child[s] = di->set_child[di->set_child[s]];
|
di->set_child[s] = di->set_child[di->set_child[s]];
|
}
|
}
|
else
|
else
|
{
|
{
|
di->set_size[di->set_child[s]] = di->set_size[s];
|
di->set_size[di->set_child[s]] = di->set_size[s];
|
s = di->set_chain[s] = di->set_child[s];
|
s = di->set_chain[s] = di->set_child[s];
|
}
|
}
|
}
|
}
|
|
|
di->path_min[s] = di->path_min[w];
|
di->path_min[s] = di->path_min[w];
|
di->set_size[v] += di->set_size[w];
|
di->set_size[v] += di->set_size[w];
|
if (di->set_size[v] < 2 * di->set_size[w])
|
if (di->set_size[v] < 2 * di->set_size[w])
|
{
|
{
|
TBB tmp = s;
|
TBB tmp = s;
|
s = di->set_child[v];
|
s = di->set_child[v];
|
di->set_child[v] = tmp;
|
di->set_child[v] = tmp;
|
}
|
}
|
|
|
/* Merge all subtrees. */
|
/* Merge all subtrees. */
|
while (s)
|
while (s)
|
{
|
{
|
di->set_chain[s] = v;
|
di->set_chain[s] = v;
|
s = di->set_child[s];
|
s = di->set_child[s];
|
}
|
}
|
}
|
}
|
|
|
/* This calculates the immediate dominators (or post-dominators if REVERSE is
|
/* This calculates the immediate dominators (or post-dominators if REVERSE is
|
true). DI is our working structure and should hold the DFS forest.
|
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]. */
|
On return the immediate dominator to node V is in di->dom[V]. */
|
|
|
static void
|
static void
|
calc_idoms (struct dom_info *di, bool reverse)
|
calc_idoms (struct dom_info *di, bool reverse)
|
{
|
{
|
TBB v, w, k, par;
|
TBB v, w, k, par;
|
basic_block en_block;
|
basic_block en_block;
|
edge_iterator ei, einext;
|
edge_iterator ei, einext;
|
|
|
if (reverse)
|
if (reverse)
|
en_block = EXIT_BLOCK_PTR;
|
en_block = EXIT_BLOCK_PTR;
|
else
|
else
|
en_block = ENTRY_BLOCK_PTR;
|
en_block = ENTRY_BLOCK_PTR;
|
|
|
/* Go backwards in DFS order, to first look at the leafs. */
|
/* Go backwards in DFS order, to first look at the leafs. */
|
v = di->nodes;
|
v = di->nodes;
|
while (v > 1)
|
while (v > 1)
|
{
|
{
|
basic_block bb = di->dfs_to_bb[v];
|
basic_block bb = di->dfs_to_bb[v];
|
edge e;
|
edge e;
|
|
|
par = di->dfs_parent[v];
|
par = di->dfs_parent[v];
|
k = v;
|
k = v;
|
|
|
ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
|
ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
|
|
|
if (reverse)
|
if (reverse)
|
{
|
{
|
/* If this block has a fake edge to exit, process that first. */
|
/* If this block has a fake edge to exit, process that first. */
|
if (bitmap_bit_p (di->fake_exit_edge, bb->index))
|
if (bitmap_bit_p (di->fake_exit_edge, bb->index))
|
{
|
{
|
einext = ei;
|
einext = ei;
|
einext.index = 0;
|
einext.index = 0;
|
goto do_fake_exit_edge;
|
goto do_fake_exit_edge;
|
}
|
}
|
}
|
}
|
|
|
/* Search all direct predecessors for the smallest node with a path
|
/* 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
|
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
|
us only over nodes behind us. In effect we search for our
|
semidominator. */
|
semidominator. */
|
while (!ei_end_p (ei))
|
while (!ei_end_p (ei))
|
{
|
{
|
TBB k1;
|
TBB k1;
|
basic_block b;
|
basic_block b;
|
|
|
e = ei_edge (ei);
|
e = ei_edge (ei);
|
b = (reverse) ? e->dest : e->src;
|
b = (reverse) ? e->dest : e->src;
|
einext = ei;
|
einext = ei;
|
ei_next (&einext);
|
ei_next (&einext);
|
|
|
if (b == en_block)
|
if (b == en_block)
|
{
|
{
|
do_fake_exit_edge:
|
do_fake_exit_edge:
|
k1 = di->dfs_order[last_basic_block];
|
k1 = di->dfs_order[last_basic_block];
|
}
|
}
|
else
|
else
|
k1 = di->dfs_order[b->index];
|
k1 = di->dfs_order[b->index];
|
|
|
/* Call eval() only if really needed. If k1 is above V in DFS tree,
|
/* 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. */
|
then we know, that eval(k1) == k1 and key[k1] == k1. */
|
if (k1 > v)
|
if (k1 > v)
|
k1 = di->key[eval (di, k1)];
|
k1 = di->key[eval (di, k1)];
|
if (k1 < k)
|
if (k1 < k)
|
k = k1;
|
k = k1;
|
|
|
ei = einext;
|
ei = einext;
|
}
|
}
|
|
|
di->key[v] = k;
|
di->key[v] = k;
|
link_roots (di, par, v);
|
link_roots (di, par, v);
|
di->next_bucket[v] = di->bucket[k];
|
di->next_bucket[v] = di->bucket[k];
|
di->bucket[k] = v;
|
di->bucket[k] = v;
|
|
|
/* Transform semidominators into dominators. */
|
/* Transform semidominators into dominators. */
|
for (w = di->bucket[par]; w; w = di->next_bucket[w])
|
for (w = di->bucket[par]; w; w = di->next_bucket[w])
|
{
|
{
|
k = eval (di, w);
|
k = eval (di, w);
|
if (di->key[k] < di->key[w])
|
if (di->key[k] < di->key[w])
|
di->dom[w] = k;
|
di->dom[w] = k;
|
else
|
else
|
di->dom[w] = par;
|
di->dom[w] = par;
|
}
|
}
|
/* We don't need to cleanup next_bucket[]. */
|
/* We don't need to cleanup next_bucket[]. */
|
di->bucket[par] = 0;
|
di->bucket[par] = 0;
|
v--;
|
v--;
|
}
|
}
|
|
|
/* Explicitly define the dominators. */
|
/* Explicitly define the dominators. */
|
di->dom[1] = 0;
|
di->dom[1] = 0;
|
for (v = 2; v <= di->nodes; v++)
|
for (v = 2; v <= di->nodes; v++)
|
if (di->dom[v] != di->key[v])
|
if (di->dom[v] != di->key[v])
|
di->dom[v] = di->dom[di->dom[v]];
|
di->dom[v] = di->dom[di->dom[v]];
|
}
|
}
|
|
|
/* Assign dfs numbers starting from NUM to NODE and its sons. */
|
/* Assign dfs numbers starting from NUM to NODE and its sons. */
|
|
|
static void
|
static void
|
assign_dfs_numbers (struct et_node *node, int *num)
|
assign_dfs_numbers (struct et_node *node, int *num)
|
{
|
{
|
struct et_node *son;
|
struct et_node *son;
|
|
|
node->dfs_num_in = (*num)++;
|
node->dfs_num_in = (*num)++;
|
|
|
if (node->son)
|
if (node->son)
|
{
|
{
|
assign_dfs_numbers (node->son, num);
|
assign_dfs_numbers (node->son, num);
|
for (son = node->son->right; son != node->son; son = son->right)
|
for (son = node->son->right; son != node->son; son = son->right)
|
assign_dfs_numbers (son, num);
|
assign_dfs_numbers (son, num);
|
}
|
}
|
|
|
node->dfs_num_out = (*num)++;
|
node->dfs_num_out = (*num)++;
|
}
|
}
|
|
|
/* Compute the data necessary for fast resolving of dominator queries in a
|
/* Compute the data necessary for fast resolving of dominator queries in a
|
static dominator tree. */
|
static dominator tree. */
|
|
|
static void
|
static void
|
compute_dom_fast_query (enum cdi_direction dir)
|
compute_dom_fast_query (enum cdi_direction dir)
|
{
|
{
|
int num = 0;
|
int num = 0;
|
basic_block bb;
|
basic_block bb;
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
gcc_assert (dom_info_available_p (dir));
|
gcc_assert (dom_info_available_p (dir));
|
|
|
if (dom_computed[dir_index] == DOM_OK)
|
if (dom_computed[dir_index] == DOM_OK)
|
return;
|
return;
|
|
|
FOR_ALL_BB (bb)
|
FOR_ALL_BB (bb)
|
{
|
{
|
if (!bb->dom[dir_index]->father)
|
if (!bb->dom[dir_index]->father)
|
assign_dfs_numbers (bb->dom[dir_index], &num);
|
assign_dfs_numbers (bb->dom[dir_index], &num);
|
}
|
}
|
|
|
dom_computed[dir_index] = DOM_OK;
|
dom_computed[dir_index] = DOM_OK;
|
}
|
}
|
|
|
/* The main entry point into this module. DIR is set depending on whether
|
/* The main entry point into this module. DIR is set depending on whether
|
we want to compute dominators or postdominators. */
|
we want to compute dominators or postdominators. */
|
|
|
void
|
void
|
calculate_dominance_info (enum cdi_direction dir)
|
calculate_dominance_info (enum cdi_direction dir)
|
{
|
{
|
struct dom_info di;
|
struct dom_info di;
|
basic_block b;
|
basic_block b;
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
|
bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
|
|
|
if (dom_computed[dir_index] == DOM_OK)
|
if (dom_computed[dir_index] == DOM_OK)
|
return;
|
return;
|
|
|
timevar_push (TV_DOMINANCE);
|
timevar_push (TV_DOMINANCE);
|
if (!dom_info_available_p (dir))
|
if (!dom_info_available_p (dir))
|
{
|
{
|
gcc_assert (!n_bbs_in_dom_tree[dir_index]);
|
gcc_assert (!n_bbs_in_dom_tree[dir_index]);
|
|
|
FOR_ALL_BB (b)
|
FOR_ALL_BB (b)
|
{
|
{
|
b->dom[dir_index] = et_new_tree (b);
|
b->dom[dir_index] = et_new_tree (b);
|
}
|
}
|
n_bbs_in_dom_tree[dir_index] = n_basic_blocks;
|
n_bbs_in_dom_tree[dir_index] = n_basic_blocks;
|
|
|
init_dom_info (&di, dir);
|
init_dom_info (&di, dir);
|
calc_dfs_tree (&di, reverse);
|
calc_dfs_tree (&di, reverse);
|
calc_idoms (&di, reverse);
|
calc_idoms (&di, reverse);
|
|
|
FOR_EACH_BB (b)
|
FOR_EACH_BB (b)
|
{
|
{
|
TBB d = di.dom[di.dfs_order[b->index]];
|
TBB d = di.dom[di.dfs_order[b->index]];
|
|
|
if (di.dfs_to_bb[d])
|
if (di.dfs_to_bb[d])
|
et_set_father (b->dom[dir_index], di.dfs_to_bb[d]->dom[dir_index]);
|
et_set_father (b->dom[dir_index], di.dfs_to_bb[d]->dom[dir_index]);
|
}
|
}
|
|
|
free_dom_info (&di);
|
free_dom_info (&di);
|
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
}
|
}
|
|
|
compute_dom_fast_query (dir);
|
compute_dom_fast_query (dir);
|
|
|
timevar_pop (TV_DOMINANCE);
|
timevar_pop (TV_DOMINANCE);
|
}
|
}
|
|
|
/* Free dominance information for direction DIR. */
|
/* Free dominance information for direction DIR. */
|
void
|
void
|
free_dominance_info (enum cdi_direction dir)
|
free_dominance_info (enum cdi_direction dir)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
if (!dom_info_available_p (dir))
|
if (!dom_info_available_p (dir))
|
return;
|
return;
|
|
|
FOR_ALL_BB (bb)
|
FOR_ALL_BB (bb)
|
{
|
{
|
et_free_tree_force (bb->dom[dir_index]);
|
et_free_tree_force (bb->dom[dir_index]);
|
bb->dom[dir_index] = NULL;
|
bb->dom[dir_index] = NULL;
|
}
|
}
|
et_free_pools ();
|
et_free_pools ();
|
|
|
n_bbs_in_dom_tree[dir_index] = 0;
|
n_bbs_in_dom_tree[dir_index] = 0;
|
|
|
dom_computed[dir_index] = DOM_NONE;
|
dom_computed[dir_index] = DOM_NONE;
|
}
|
}
|
|
|
/* Return the immediate dominator of basic block BB. */
|
/* Return the immediate dominator of basic block BB. */
|
basic_block
|
basic_block
|
get_immediate_dominator (enum cdi_direction dir, basic_block bb)
|
get_immediate_dominator (enum cdi_direction dir, basic_block bb)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
struct et_node *node = bb->dom[dir_index];
|
struct et_node *node = bb->dom[dir_index];
|
|
|
gcc_assert (dom_computed[dir_index]);
|
gcc_assert (dom_computed[dir_index]);
|
|
|
if (!node->father)
|
if (!node->father)
|
return NULL;
|
return NULL;
|
|
|
return (basic_block) node->father->data;
|
return (basic_block) node->father->data;
|
}
|
}
|
|
|
/* Set the immediate dominator of the block possibly removing
|
/* Set the immediate dominator of the block possibly removing
|
existing edge. NULL can be used to remove any edge. */
|
existing edge. NULL can be used to remove any edge. */
|
void
|
void
|
set_immediate_dominator (enum cdi_direction dir, basic_block bb,
|
set_immediate_dominator (enum cdi_direction dir, basic_block bb,
|
basic_block dominated_by)
|
basic_block dominated_by)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
struct et_node *node = bb->dom[dir_index];
|
struct et_node *node = bb->dom[dir_index];
|
|
|
gcc_assert (dom_computed[dir_index]);
|
gcc_assert (dom_computed[dir_index]);
|
|
|
if (node->father)
|
if (node->father)
|
{
|
{
|
if (node->father->data == dominated_by)
|
if (node->father->data == dominated_by)
|
return;
|
return;
|
et_split (node);
|
et_split (node);
|
}
|
}
|
|
|
if (dominated_by)
|
if (dominated_by)
|
et_set_father (node, dominated_by->dom[dir_index]);
|
et_set_father (node, dominated_by->dom[dir_index]);
|
|
|
if (dom_computed[dir_index] == DOM_OK)
|
if (dom_computed[dir_index] == DOM_OK)
|
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
}
|
}
|
|
|
/* Returns the list of basic blocks immediately dominated by BB, in the
|
/* Returns the list of basic blocks immediately dominated by BB, in the
|
direction DIR. */
|
direction DIR. */
|
VEC (basic_block, heap) *
|
VEC (basic_block, heap) *
|
get_dominated_by (enum cdi_direction dir, basic_block bb)
|
get_dominated_by (enum cdi_direction dir, basic_block bb)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
|
struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
|
VEC (basic_block, heap) *bbs = NULL;
|
VEC (basic_block, heap) *bbs = NULL;
|
|
|
gcc_assert (dom_computed[dir_index]);
|
gcc_assert (dom_computed[dir_index]);
|
|
|
if (!son)
|
if (!son)
|
return NULL;
|
return NULL;
|
|
|
VEC_safe_push (basic_block, heap, bbs, (basic_block) son->data);
|
VEC_safe_push (basic_block, heap, bbs, (basic_block) son->data);
|
for (ason = son->right; ason != son; ason = ason->right)
|
for (ason = son->right; ason != son; ason = ason->right)
|
VEC_safe_push (basic_block, heap, bbs, (basic_block) ason->data);
|
VEC_safe_push (basic_block, heap, bbs, (basic_block) ason->data);
|
|
|
return bbs;
|
return bbs;
|
}
|
}
|
|
|
/* Returns the list of basic blocks that are immediately dominated (in
|
/* Returns the list of basic blocks that are immediately dominated (in
|
direction DIR) by some block between N_REGION ones stored in REGION,
|
direction DIR) by some block between N_REGION ones stored in REGION,
|
except for blocks in the REGION itself. */
|
except for blocks in the REGION itself. */
|
|
|
VEC (basic_block, heap) *
|
VEC (basic_block, heap) *
|
get_dominated_by_region (enum cdi_direction dir, basic_block *region,
|
get_dominated_by_region (enum cdi_direction dir, basic_block *region,
|
unsigned n_region)
|
unsigned n_region)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
basic_block dom;
|
basic_block dom;
|
VEC (basic_block, heap) *doms = NULL;
|
VEC (basic_block, heap) *doms = NULL;
|
|
|
for (i = 0; i < n_region; i++)
|
for (i = 0; i < n_region; i++)
|
region[i]->flags |= BB_DUPLICATED;
|
region[i]->flags |= BB_DUPLICATED;
|
for (i = 0; i < n_region; i++)
|
for (i = 0; i < n_region; i++)
|
for (dom = first_dom_son (dir, region[i]);
|
for (dom = first_dom_son (dir, region[i]);
|
dom;
|
dom;
|
dom = next_dom_son (dir, dom))
|
dom = next_dom_son (dir, dom))
|
if (!(dom->flags & BB_DUPLICATED))
|
if (!(dom->flags & BB_DUPLICATED))
|
VEC_safe_push (basic_block, heap, doms, dom);
|
VEC_safe_push (basic_block, heap, doms, dom);
|
for (i = 0; i < n_region; i++)
|
for (i = 0; i < n_region; i++)
|
region[i]->flags &= ~BB_DUPLICATED;
|
region[i]->flags &= ~BB_DUPLICATED;
|
|
|
return doms;
|
return doms;
|
}
|
}
|
|
|
/* Returns the list of basic blocks including BB dominated by BB, in the
|
/* Returns the list of basic blocks including BB dominated by BB, in the
|
direction DIR. The vector will be sorted in preorder. */
|
direction DIR. The vector will be sorted in preorder. */
|
|
|
VEC (basic_block, heap) *
|
VEC (basic_block, heap) *
|
get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
|
get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
|
{
|
{
|
VEC(basic_block, heap) *bbs = NULL;
|
VEC(basic_block, heap) *bbs = NULL;
|
unsigned i;
|
unsigned i;
|
|
|
i = 0;
|
i = 0;
|
VEC_safe_push (basic_block, heap, bbs, bb);
|
VEC_safe_push (basic_block, heap, bbs, bb);
|
|
|
do
|
do
|
{
|
{
|
basic_block son;
|
basic_block son;
|
|
|
bb = VEC_index (basic_block, bbs, i++);
|
bb = VEC_index (basic_block, bbs, i++);
|
for (son = first_dom_son (dir, bb);
|
for (son = first_dom_son (dir, bb);
|
son;
|
son;
|
son = next_dom_son (dir, son))
|
son = next_dom_son (dir, son))
|
VEC_safe_push (basic_block, heap, bbs, son);
|
VEC_safe_push (basic_block, heap, bbs, son);
|
}
|
}
|
while (i < VEC_length (basic_block, bbs));
|
while (i < VEC_length (basic_block, bbs));
|
|
|
return bbs;
|
return bbs;
|
}
|
}
|
|
|
/* Redirect all edges pointing to BB to TO. */
|
/* Redirect all edges pointing to BB to TO. */
|
void
|
void
|
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
|
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
|
basic_block to)
|
basic_block to)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
struct et_node *bb_node, *to_node, *son;
|
struct et_node *bb_node, *to_node, *son;
|
|
|
bb_node = bb->dom[dir_index];
|
bb_node = bb->dom[dir_index];
|
to_node = to->dom[dir_index];
|
to_node = to->dom[dir_index];
|
|
|
gcc_assert (dom_computed[dir_index]);
|
gcc_assert (dom_computed[dir_index]);
|
|
|
if (!bb_node->son)
|
if (!bb_node->son)
|
return;
|
return;
|
|
|
while (bb_node->son)
|
while (bb_node->son)
|
{
|
{
|
son = bb_node->son;
|
son = bb_node->son;
|
|
|
et_split (son);
|
et_split (son);
|
et_set_father (son, to_node);
|
et_set_father (son, to_node);
|
}
|
}
|
|
|
if (dom_computed[dir_index] == DOM_OK)
|
if (dom_computed[dir_index] == DOM_OK)
|
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
}
|
}
|
|
|
/* Find first basic block in the tree dominating both BB1 and BB2. */
|
/* Find first basic block in the tree dominating both BB1 and BB2. */
|
basic_block
|
basic_block
|
nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
|
nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
gcc_assert (dom_computed[dir_index]);
|
gcc_assert (dom_computed[dir_index]);
|
|
|
if (!bb1)
|
if (!bb1)
|
return bb2;
|
return bb2;
|
if (!bb2)
|
if (!bb2)
|
return bb1;
|
return bb1;
|
|
|
return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
|
return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
|
}
|
}
|
|
|
|
|
/* Find the nearest common dominator for the basic blocks in BLOCKS,
|
/* Find the nearest common dominator for the basic blocks in BLOCKS,
|
using dominance direction DIR. */
|
using dominance direction DIR. */
|
|
|
basic_block
|
basic_block
|
nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
|
nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
|
{
|
{
|
unsigned i, first;
|
unsigned i, first;
|
bitmap_iterator bi;
|
bitmap_iterator bi;
|
basic_block dom;
|
basic_block dom;
|
|
|
first = bitmap_first_set_bit (blocks);
|
first = bitmap_first_set_bit (blocks);
|
dom = BASIC_BLOCK (first);
|
dom = BASIC_BLOCK (first);
|
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
|
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
|
if (dom != BASIC_BLOCK (i))
|
if (dom != BASIC_BLOCK (i))
|
dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
|
dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
|
|
|
return dom;
|
return dom;
|
}
|
}
|
|
|
/* Given a dominator tree, we can determine whether one thing
|
/* Given a dominator tree, we can determine whether one thing
|
dominates another in constant time by using two DFS numbers:
|
dominates another in constant time by using two DFS numbers:
|
|
|
1. The number for when we visit a node on the way down the tree
|
1. The number for when we visit a node on the way down the tree
|
2. The number for when we visit a node on the way back up the tree
|
2. The number for when we visit a node on the way back up the tree
|
|
|
You can view these as bounds for the range of dfs numbers the
|
You can view these as bounds for the range of dfs numbers the
|
nodes in the subtree of the dominator tree rooted at that node
|
nodes in the subtree of the dominator tree rooted at that node
|
will contain.
|
will contain.
|
|
|
The dominator tree is always a simple acyclic tree, so there are
|
The dominator tree is always a simple acyclic tree, so there are
|
only three possible relations two nodes in the dominator tree have
|
only three possible relations two nodes in the dominator tree have
|
to each other:
|
to each other:
|
|
|
1. Node A is above Node B (and thus, Node A dominates node B)
|
1. Node A is above Node B (and thus, Node A dominates node B)
|
|
|
A
|
A
|
|
|
|
|
C
|
C
|
/ \
|
/ \
|
B D
|
B D
|
|
|
|
|
In the above case, DFS_Number_In of A will be <= DFS_Number_In of
|
In the above case, DFS_Number_In of A will be <= DFS_Number_In of
|
B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is
|
B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is
|
because we must hit A in the dominator tree *before* B on the walk
|
because we must hit A in the dominator tree *before* B on the walk
|
down, and we will hit A *after* B on the walk back up
|
down, and we will hit A *after* B on the walk back up
|
|
|
2. Node A is below node B (and thus, node B dominates node A)
|
2. Node A is below node B (and thus, node B dominates node A)
|
|
|
|
|
B
|
B
|
|
|
|
|
A
|
A
|
/ \
|
/ \
|
C D
|
C D
|
|
|
In the above case, DFS_Number_In of A will be >= DFS_Number_In of
|
In the above case, DFS_Number_In of A will be >= DFS_Number_In of
|
B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
|
B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
|
|
|
This is because we must hit A in the dominator tree *after* B on
|
This is because we must hit A in the dominator tree *after* B on
|
the walk down, and we will hit A *before* B on the walk back up
|
the walk down, and we will hit A *before* B on the walk back up
|
|
|
3. Node A and B are siblings (and thus, neither dominates the other)
|
3. Node A and B are siblings (and thus, neither dominates the other)
|
|
|
C
|
C
|
|
|
|
|
D
|
D
|
/ \
|
/ \
|
A B
|
A B
|
|
|
In the above case, DFS_Number_In of A will *always* be <=
|
In the above case, DFS_Number_In of A will *always* be <=
|
DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
|
DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
|
DFS_Number_Out of B. This is because we will always finish the dfs
|
DFS_Number_Out of B. This is because we will always finish the dfs
|
walk of one of the subtrees before the other, and thus, the dfs
|
walk of one of the subtrees before the other, and thus, the dfs
|
numbers for one subtree can't intersect with the range of dfs
|
numbers for one subtree can't intersect with the range of dfs
|
numbers for the other subtree. If you swap A and B's position in
|
numbers for the other subtree. If you swap A and B's position in
|
the dominator tree, the comparison changes direction, but the point
|
the dominator tree, the comparison changes direction, but the point
|
is that both comparisons will always go the same way if there is no
|
is that both comparisons will always go the same way if there is no
|
dominance relationship.
|
dominance relationship.
|
|
|
Thus, it is sufficient to write
|
Thus, it is sufficient to write
|
|
|
A_Dominates_B (node A, node B)
|
A_Dominates_B (node A, node B)
|
{
|
{
|
return DFS_Number_In(A) <= DFS_Number_In(B)
|
return DFS_Number_In(A) <= DFS_Number_In(B)
|
&& DFS_Number_Out (A) >= DFS_Number_Out(B);
|
&& DFS_Number_Out (A) >= DFS_Number_Out(B);
|
}
|
}
|
|
|
A_Dominated_by_B (node A, node B)
|
A_Dominated_by_B (node A, node B)
|
{
|
{
|
return DFS_Number_In(A) >= DFS_Number_In(A)
|
return DFS_Number_In(A) >= DFS_Number_In(A)
|
&& DFS_Number_Out (A) <= DFS_Number_Out(B);
|
&& DFS_Number_Out (A) <= DFS_Number_Out(B);
|
} */
|
} */
|
|
|
/* Return TRUE in case BB1 is dominated by BB2. */
|
/* Return TRUE in case BB1 is dominated by BB2. */
|
bool
|
bool
|
dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
|
dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
|
struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
|
|
|
gcc_assert (dom_computed[dir_index]);
|
gcc_assert (dom_computed[dir_index]);
|
|
|
if (dom_computed[dir_index] == DOM_OK)
|
if (dom_computed[dir_index] == DOM_OK)
|
return (n1->dfs_num_in >= n2->dfs_num_in
|
return (n1->dfs_num_in >= n2->dfs_num_in
|
&& n1->dfs_num_out <= n2->dfs_num_out);
|
&& n1->dfs_num_out <= n2->dfs_num_out);
|
|
|
return et_below (n1, n2);
|
return et_below (n1, n2);
|
}
|
}
|
|
|
/* Returns the entry dfs number for basic block BB, in the direction DIR. */
|
/* Returns the entry dfs number for basic block BB, in the direction DIR. */
|
|
|
unsigned
|
unsigned
|
bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
|
bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
struct et_node *n = bb->dom[dir_index];
|
struct et_node *n = bb->dom[dir_index];
|
|
|
gcc_assert (dom_computed[dir_index] == DOM_OK);
|
gcc_assert (dom_computed[dir_index] == DOM_OK);
|
return n->dfs_num_in;
|
return n->dfs_num_in;
|
}
|
}
|
|
|
/* Returns the exit dfs number for basic block BB, in the direction DIR. */
|
/* Returns the exit dfs number for basic block BB, in the direction DIR. */
|
|
|
unsigned
|
unsigned
|
bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
|
bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
struct et_node *n = bb->dom[dir_index];
|
struct et_node *n = bb->dom[dir_index];
|
|
|
gcc_assert (dom_computed[dir_index] == DOM_OK);
|
gcc_assert (dom_computed[dir_index] == DOM_OK);
|
return n->dfs_num_out;
|
return n->dfs_num_out;
|
}
|
}
|
|
|
/* Verify invariants of dominator structure. */
|
/* Verify invariants of dominator structure. */
|
void
|
void
|
verify_dominators (enum cdi_direction dir)
|
verify_dominators (enum cdi_direction dir)
|
{
|
{
|
int err = 0;
|
int err = 0;
|
basic_block bb, imm_bb, imm_bb_correct;
|
basic_block bb, imm_bb, imm_bb_correct;
|
struct dom_info di;
|
struct dom_info di;
|
bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
|
bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
|
|
|
gcc_assert (dom_info_available_p (dir));
|
gcc_assert (dom_info_available_p (dir));
|
|
|
init_dom_info (&di, dir);
|
init_dom_info (&di, dir);
|
calc_dfs_tree (&di, reverse);
|
calc_dfs_tree (&di, reverse);
|
calc_idoms (&di, reverse);
|
calc_idoms (&di, reverse);
|
|
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
{
|
{
|
imm_bb = get_immediate_dominator (dir, bb);
|
imm_bb = get_immediate_dominator (dir, bb);
|
if (!imm_bb)
|
if (!imm_bb)
|
{
|
{
|
error ("dominator of %d status unknown", bb->index);
|
error ("dominator of %d status unknown", bb->index);
|
err = 1;
|
err = 1;
|
}
|
}
|
|
|
imm_bb_correct = di.dfs_to_bb[di.dom[di.dfs_order[bb->index]]];
|
imm_bb_correct = di.dfs_to_bb[di.dom[di.dfs_order[bb->index]]];
|
if (imm_bb != imm_bb_correct)
|
if (imm_bb != imm_bb_correct)
|
{
|
{
|
error ("dominator of %d should be %d, not %d",
|
error ("dominator of %d should be %d, not %d",
|
bb->index, imm_bb_correct->index, imm_bb->index);
|
bb->index, imm_bb_correct->index, imm_bb->index);
|
err = 1;
|
err = 1;
|
}
|
}
|
}
|
}
|
|
|
free_dom_info (&di);
|
free_dom_info (&di);
|
gcc_assert (!err);
|
gcc_assert (!err);
|
}
|
}
|
|
|
/* Determine immediate dominator (or postdominator, according to DIR) of BB,
|
/* Determine immediate dominator (or postdominator, according to DIR) of BB,
|
assuming that dominators of other blocks are correct. We also use it to
|
assuming that dominators of other blocks are correct. We also use it to
|
recompute the dominators in a restricted area, by iterating it until it
|
recompute the dominators in a restricted area, by iterating it until it
|
reaches a fixed point. */
|
reaches a fixed point. */
|
|
|
basic_block
|
basic_block
|
recompute_dominator (enum cdi_direction dir, basic_block bb)
|
recompute_dominator (enum cdi_direction dir, basic_block bb)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
basic_block dom_bb = NULL;
|
basic_block dom_bb = NULL;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
gcc_assert (dom_computed[dir_index]);
|
gcc_assert (dom_computed[dir_index]);
|
|
|
if (dir == CDI_DOMINATORS)
|
if (dir == CDI_DOMINATORS)
|
{
|
{
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
{
|
{
|
if (!dominated_by_p (dir, e->src, bb))
|
if (!dominated_by_p (dir, e->src, bb))
|
dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
|
dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
{
|
{
|
if (!dominated_by_p (dir, e->dest, bb))
|
if (!dominated_by_p (dir, e->dest, bb))
|
dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
|
dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
|
}
|
}
|
}
|
}
|
|
|
return dom_bb;
|
return dom_bb;
|
}
|
}
|
|
|
/* Use simple heuristics (see iterate_fix_dominators) to determine dominators
|
/* Use simple heuristics (see iterate_fix_dominators) to determine dominators
|
of BBS. We assume that all the immediate dominators except for those of the
|
of BBS. We assume that all the immediate dominators except for those of the
|
blocks in BBS are correct. If CONSERVATIVE is true, we also assume that the
|
blocks in BBS are correct. If CONSERVATIVE is true, we also assume that the
|
currently recorded immediate dominators of blocks in BBS really dominate the
|
currently recorded immediate dominators of blocks in BBS really dominate the
|
blocks. The basic blocks for that we determine the dominator are removed
|
blocks. The basic blocks for that we determine the dominator are removed
|
from BBS. */
|
from BBS. */
|
|
|
static void
|
static void
|
prune_bbs_to_update_dominators (VEC (basic_block, heap) *bbs,
|
prune_bbs_to_update_dominators (VEC (basic_block, heap) *bbs,
|
bool conservative)
|
bool conservative)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
bool single;
|
bool single;
|
basic_block bb, dom = NULL;
|
basic_block bb, dom = NULL;
|
edge_iterator ei;
|
edge_iterator ei;
|
edge e;
|
edge e;
|
|
|
for (i = 0; VEC_iterate (basic_block, bbs, i, bb);)
|
for (i = 0; VEC_iterate (basic_block, bbs, i, bb);)
|
{
|
{
|
if (bb == ENTRY_BLOCK_PTR)
|
if (bb == ENTRY_BLOCK_PTR)
|
goto succeed;
|
goto succeed;
|
|
|
if (single_pred_p (bb))
|
if (single_pred_p (bb))
|
{
|
{
|
set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
|
set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
|
goto succeed;
|
goto succeed;
|
}
|
}
|
|
|
if (!conservative)
|
if (!conservative)
|
goto fail;
|
goto fail;
|
|
|
single = true;
|
single = true;
|
dom = NULL;
|
dom = NULL;
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
{
|
{
|
if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
|
if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
|
continue;
|
continue;
|
|
|
if (!dom)
|
if (!dom)
|
dom = e->src;
|
dom = e->src;
|
else
|
else
|
{
|
{
|
single = false;
|
single = false;
|
dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
|
dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
|
}
|
}
|
}
|
}
|
|
|
gcc_assert (dom != NULL);
|
gcc_assert (dom != NULL);
|
if (single
|
if (single
|
|| find_edge (dom, bb))
|
|| find_edge (dom, bb))
|
{
|
{
|
set_immediate_dominator (CDI_DOMINATORS, bb, dom);
|
set_immediate_dominator (CDI_DOMINATORS, bb, dom);
|
goto succeed;
|
goto succeed;
|
}
|
}
|
|
|
fail:
|
fail:
|
i++;
|
i++;
|
continue;
|
continue;
|
|
|
succeed:
|
succeed:
|
VEC_unordered_remove (basic_block, bbs, i);
|
VEC_unordered_remove (basic_block, bbs, i);
|
}
|
}
|
}
|
}
|
|
|
/* Returns root of the dominance tree in the direction DIR that contains
|
/* Returns root of the dominance tree in the direction DIR that contains
|
BB. */
|
BB. */
|
|
|
static basic_block
|
static basic_block
|
root_of_dom_tree (enum cdi_direction dir, basic_block bb)
|
root_of_dom_tree (enum cdi_direction dir, basic_block bb)
|
{
|
{
|
return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
|
return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
|
}
|
}
|
|
|
/* See the comment in iterate_fix_dominators. Finds the immediate dominators
|
/* See the comment in iterate_fix_dominators. Finds the immediate dominators
|
for the sons of Y, found using the SON and BROTHER arrays representing
|
for the sons of Y, found using the SON and BROTHER arrays representing
|
the dominance tree of graph G. BBS maps the vertices of G to the basic
|
the dominance tree of graph G. BBS maps the vertices of G to the basic
|
blocks. */
|
blocks. */
|
|
|
static void
|
static void
|
determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs,
|
determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs,
|
int y, int *son, int *brother)
|
int y, int *son, int *brother)
|
{
|
{
|
bitmap gprime;
|
bitmap gprime;
|
int i, a, nc;
|
int i, a, nc;
|
VEC (int, heap) **sccs;
|
VEC (int, heap) **sccs;
|
basic_block bb, dom, ybb;
|
basic_block bb, dom, ybb;
|
unsigned si;
|
unsigned si;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
if (son[y] == -1)
|
if (son[y] == -1)
|
return;
|
return;
|
if (y == (int) VEC_length (basic_block, bbs))
|
if (y == (int) VEC_length (basic_block, bbs))
|
ybb = ENTRY_BLOCK_PTR;
|
ybb = ENTRY_BLOCK_PTR;
|
else
|
else
|
ybb = VEC_index (basic_block, bbs, y);
|
ybb = VEC_index (basic_block, bbs, y);
|
|
|
if (brother[son[y]] == -1)
|
if (brother[son[y]] == -1)
|
{
|
{
|
/* Handle the common case Y has just one son specially. */
|
/* Handle the common case Y has just one son specially. */
|
bb = VEC_index (basic_block, bbs, son[y]);
|
bb = VEC_index (basic_block, bbs, son[y]);
|
set_immediate_dominator (CDI_DOMINATORS, bb,
|
set_immediate_dominator (CDI_DOMINATORS, bb,
|
recompute_dominator (CDI_DOMINATORS, bb));
|
recompute_dominator (CDI_DOMINATORS, bb));
|
identify_vertices (g, y, son[y]);
|
identify_vertices (g, y, son[y]);
|
return;
|
return;
|
}
|
}
|
|
|
gprime = BITMAP_ALLOC (NULL);
|
gprime = BITMAP_ALLOC (NULL);
|
for (a = son[y]; a != -1; a = brother[a])
|
for (a = son[y]; a != -1; a = brother[a])
|
bitmap_set_bit (gprime, a);
|
bitmap_set_bit (gprime, a);
|
|
|
nc = graphds_scc (g, gprime);
|
nc = graphds_scc (g, gprime);
|
BITMAP_FREE (gprime);
|
BITMAP_FREE (gprime);
|
|
|
sccs = XCNEWVEC (VEC (int, heap) *, nc);
|
sccs = XCNEWVEC (VEC (int, heap) *, nc);
|
for (a = son[y]; a != -1; a = brother[a])
|
for (a = son[y]; a != -1; a = brother[a])
|
VEC_safe_push (int, heap, sccs[g->vertices[a].component], a);
|
VEC_safe_push (int, heap, sccs[g->vertices[a].component], a);
|
|
|
for (i = nc - 1; i >= 0; i--)
|
for (i = nc - 1; i >= 0; i--)
|
{
|
{
|
dom = NULL;
|
dom = NULL;
|
for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
|
for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
|
{
|
{
|
bb = VEC_index (basic_block, bbs, a);
|
bb = VEC_index (basic_block, bbs, a);
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
{
|
{
|
if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
|
if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
|
continue;
|
continue;
|
|
|
dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
|
dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
|
}
|
}
|
}
|
}
|
|
|
gcc_assert (dom != NULL);
|
gcc_assert (dom != NULL);
|
for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
|
for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
|
{
|
{
|
bb = VEC_index (basic_block, bbs, a);
|
bb = VEC_index (basic_block, bbs, a);
|
set_immediate_dominator (CDI_DOMINATORS, bb, dom);
|
set_immediate_dominator (CDI_DOMINATORS, bb, dom);
|
}
|
}
|
}
|
}
|
|
|
for (i = 0; i < nc; i++)
|
for (i = 0; i < nc; i++)
|
VEC_free (int, heap, sccs[i]);
|
VEC_free (int, heap, sccs[i]);
|
free (sccs);
|
free (sccs);
|
|
|
for (a = son[y]; a != -1; a = brother[a])
|
for (a = son[y]; a != -1; a = brother[a])
|
identify_vertices (g, y, a);
|
identify_vertices (g, y, a);
|
}
|
}
|
|
|
/* Recompute dominance information for basic blocks in the set BBS. The
|
/* Recompute dominance information for basic blocks in the set BBS. The
|
function assumes that the immediate dominators of all the other blocks
|
function assumes that the immediate dominators of all the other blocks
|
in CFG are correct, and that there are no unreachable blocks.
|
in CFG are correct, and that there are no unreachable blocks.
|
|
|
If CONSERVATIVE is true, we additionally assume that all the ancestors of
|
If CONSERVATIVE is true, we additionally assume that all the ancestors of
|
a block of BBS in the current dominance tree dominate it. */
|
a block of BBS in the current dominance tree dominate it. */
|
|
|
void
|
void
|
iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
|
iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
|
bool conservative)
|
bool conservative)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
basic_block bb, dom;
|
basic_block bb, dom;
|
struct graph *g;
|
struct graph *g;
|
int n, y;
|
int n, y;
|
size_t dom_i;
|
size_t dom_i;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
struct pointer_map_t *map;
|
struct pointer_map_t *map;
|
int *parent, *son, *brother;
|
int *parent, *son, *brother;
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
/* We only support updating dominators. There are some problems with
|
/* We only support updating dominators. There are some problems with
|
updating postdominators (need to add fake edges from infinite loops
|
updating postdominators (need to add fake edges from infinite loops
|
and noreturn functions), and since we do not currently use
|
and noreturn functions), and since we do not currently use
|
iterate_fix_dominators for postdominators, any attempt to handle these
|
iterate_fix_dominators for postdominators, any attempt to handle these
|
problems would be unused, untested, and almost surely buggy. We keep
|
problems would be unused, untested, and almost surely buggy. We keep
|
the DIR argument for consistency with the rest of the dominator analysis
|
the DIR argument for consistency with the rest of the dominator analysis
|
interface. */
|
interface. */
|
gcc_assert (dir == CDI_DOMINATORS);
|
gcc_assert (dir == CDI_DOMINATORS);
|
gcc_assert (dom_computed[dir_index]);
|
gcc_assert (dom_computed[dir_index]);
|
|
|
/* The algorithm we use takes inspiration from the following papers, although
|
/* The algorithm we use takes inspiration from the following papers, although
|
the details are quite different from any of them:
|
the details are quite different from any of them:
|
|
|
[1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
|
[1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
|
Dominator Tree of a Reducible Flowgraph
|
Dominator Tree of a Reducible Flowgraph
|
[2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
|
[2] V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
|
dominator trees
|
dominator trees
|
[3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
|
[3] K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
|
Algorithm
|
Algorithm
|
|
|
First, we use the following heuristics to decrease the size of the BBS
|
First, we use the following heuristics to decrease the size of the BBS
|
set:
|
set:
|
a) if BB has a single predecessor, then its immediate dominator is this
|
a) if BB has a single predecessor, then its immediate dominator is this
|
predecessor
|
predecessor
|
additionally, if CONSERVATIVE is true:
|
additionally, if CONSERVATIVE is true:
|
b) if all the predecessors of BB except for one (X) are dominated by BB,
|
b) if all the predecessors of BB except for one (X) are dominated by BB,
|
then X is the immediate dominator of BB
|
then X is the immediate dominator of BB
|
c) if the nearest common ancestor of the predecessors of BB is X and
|
c) if the nearest common ancestor of the predecessors of BB is X and
|
X -> BB is an edge in CFG, then X is the immediate dominator of BB
|
X -> BB is an edge in CFG, then X is the immediate dominator of BB
|
|
|
Then, we need to establish the dominance relation among the basic blocks
|
Then, we need to establish the dominance relation among the basic blocks
|
in BBS. We split the dominance tree by removing the immediate dominator
|
in BBS. We split the dominance tree by removing the immediate dominator
|
edges from BBS, creating a forest F. We form a graph G whose vertices
|
edges from BBS, creating a forest F. We form a graph G whose vertices
|
are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
|
are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
|
X' -> Y in CFG such that X' belongs to the tree of the dominance forest
|
X' -> Y in CFG such that X' belongs to the tree of the dominance forest
|
whose root is X. We then determine dominance tree of G. Note that
|
whose root is X. We then determine dominance tree of G. Note that
|
for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
|
for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
|
In this step, we can use arbitrary algorithm to determine dominators.
|
In this step, we can use arbitrary algorithm to determine dominators.
|
We decided to prefer the algorithm [3] to the algorithm of
|
We decided to prefer the algorithm [3] to the algorithm of
|
Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
|
Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
|
10 during gcc bootstrap), and [3] should perform better in this case.
|
10 during gcc bootstrap), and [3] should perform better in this case.
|
|
|
Finally, we need to determine the immediate dominators for the basic
|
Finally, we need to determine the immediate dominators for the basic
|
blocks of BBS. If the immediate dominator of X in G is Y, then
|
blocks of BBS. If the immediate dominator of X in G is Y, then
|
the immediate dominator of X in CFG belongs to the tree of F rooted in
|
the immediate dominator of X in CFG belongs to the tree of F rooted in
|
Y. We process the dominator tree T of G recursively, starting from leaves.
|
Y. We process the dominator tree T of G recursively, starting from leaves.
|
Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
|
Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
|
subtrees of the dominance tree of CFG rooted in X_i are already correct.
|
subtrees of the dominance tree of CFG rooted in X_i are already correct.
|
Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make
|
Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}. We make
|
the following observations:
|
the following observations:
|
(i) the immediate dominator of all blocks in a strongly connected
|
(i) the immediate dominator of all blocks in a strongly connected
|
component of G' is the same
|
component of G' is the same
|
(ii) if X has no predecessors in G', then the immediate dominator of X
|
(ii) if X has no predecessors in G', then the immediate dominator of X
|
is the nearest common ancestor of the predecessors of X in the
|
is the nearest common ancestor of the predecessors of X in the
|
subtree of F rooted in Y
|
subtree of F rooted in Y
|
Therefore, it suffices to find the topological ordering of G', and
|
Therefore, it suffices to find the topological ordering of G', and
|
process the nodes X_i in this order using the rules (i) and (ii).
|
process the nodes X_i in this order using the rules (i) and (ii).
|
Then, we contract all the nodes X_i with Y in G, so that the further
|
Then, we contract all the nodes X_i with Y in G, so that the further
|
steps work correctly. */
|
steps work correctly. */
|
|
|
if (!conservative)
|
if (!conservative)
|
{
|
{
|
/* Split the tree now. If the idoms of blocks in BBS are not
|
/* Split the tree now. If the idoms of blocks in BBS are not
|
conservatively correct, setting the dominators using the
|
conservatively correct, setting the dominators using the
|
heuristics in prune_bbs_to_update_dominators could
|
heuristics in prune_bbs_to_update_dominators could
|
create cycles in the dominance "tree", and cause ICE. */
|
create cycles in the dominance "tree", and cause ICE. */
|
for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
|
for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
|
set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
|
set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
|
}
|
}
|
|
|
prune_bbs_to_update_dominators (bbs, conservative);
|
prune_bbs_to_update_dominators (bbs, conservative);
|
n = VEC_length (basic_block, bbs);
|
n = VEC_length (basic_block, bbs);
|
|
|
if (n == 0)
|
if (n == 0)
|
return;
|
return;
|
|
|
if (n == 1)
|
if (n == 1)
|
{
|
{
|
bb = VEC_index (basic_block, bbs, 0);
|
bb = VEC_index (basic_block, bbs, 0);
|
set_immediate_dominator (CDI_DOMINATORS, bb,
|
set_immediate_dominator (CDI_DOMINATORS, bb,
|
recompute_dominator (CDI_DOMINATORS, bb));
|
recompute_dominator (CDI_DOMINATORS, bb));
|
return;
|
return;
|
}
|
}
|
|
|
/* Construct the graph G. */
|
/* Construct the graph G. */
|
map = pointer_map_create ();
|
map = pointer_map_create ();
|
for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
|
for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
|
{
|
{
|
/* If the dominance tree is conservatively correct, split it now. */
|
/* If the dominance tree is conservatively correct, split it now. */
|
if (conservative)
|
if (conservative)
|
set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
|
set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
|
*pointer_map_insert (map, bb) = (void *) (size_t) i;
|
*pointer_map_insert (map, bb) = (void *) (size_t) i;
|
}
|
}
|
*pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
|
*pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
|
|
|
g = new_graph (n + 1);
|
g = new_graph (n + 1);
|
for (y = 0; y < g->n_vertices; y++)
|
for (y = 0; y < g->n_vertices; y++)
|
g->vertices[y].data = BITMAP_ALLOC (NULL);
|
g->vertices[y].data = BITMAP_ALLOC (NULL);
|
for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
|
for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
|
{
|
{
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
FOR_EACH_EDGE (e, ei, bb->preds)
|
{
|
{
|
dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
|
dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
|
if (dom == bb)
|
if (dom == bb)
|
continue;
|
continue;
|
|
|
dom_i = (size_t) *pointer_map_contains (map, dom);
|
dom_i = (size_t) *pointer_map_contains (map, dom);
|
|
|
/* Do not include parallel edges to G. */
|
/* Do not include parallel edges to G. */
|
if (bitmap_bit_p ((bitmap) g->vertices[dom_i].data, i))
|
if (bitmap_bit_p ((bitmap) g->vertices[dom_i].data, i))
|
continue;
|
continue;
|
|
|
bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i);
|
bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i);
|
add_edge (g, dom_i, i);
|
add_edge (g, dom_i, i);
|
}
|
}
|
}
|
}
|
for (y = 0; y < g->n_vertices; y++)
|
for (y = 0; y < g->n_vertices; y++)
|
BITMAP_FREE (g->vertices[y].data);
|
BITMAP_FREE (g->vertices[y].data);
|
pointer_map_destroy (map);
|
pointer_map_destroy (map);
|
|
|
/* Find the dominator tree of G. */
|
/* Find the dominator tree of G. */
|
son = XNEWVEC (int, n + 1);
|
son = XNEWVEC (int, n + 1);
|
brother = XNEWVEC (int, n + 1);
|
brother = XNEWVEC (int, n + 1);
|
parent = XNEWVEC (int, n + 1);
|
parent = XNEWVEC (int, n + 1);
|
graphds_domtree (g, n, parent, son, brother);
|
graphds_domtree (g, n, parent, son, brother);
|
|
|
/* Finally, traverse the tree and find the immediate dominators. */
|
/* Finally, traverse the tree and find the immediate dominators. */
|
for (y = n; son[y] != -1; y = son[y])
|
for (y = n; son[y] != -1; y = son[y])
|
continue;
|
continue;
|
while (y != -1)
|
while (y != -1)
|
{
|
{
|
determine_dominators_for_sons (g, bbs, y, son, brother);
|
determine_dominators_for_sons (g, bbs, y, son, brother);
|
|
|
if (brother[y] != -1)
|
if (brother[y] != -1)
|
{
|
{
|
y = brother[y];
|
y = brother[y];
|
while (son[y] != -1)
|
while (son[y] != -1)
|
y = son[y];
|
y = son[y];
|
}
|
}
|
else
|
else
|
y = parent[y];
|
y = parent[y];
|
}
|
}
|
|
|
free (son);
|
free (son);
|
free (brother);
|
free (brother);
|
free (parent);
|
free (parent);
|
|
|
free_graph (g);
|
free_graph (g);
|
}
|
}
|
|
|
void
|
void
|
add_to_dominance_info (enum cdi_direction dir, basic_block bb)
|
add_to_dominance_info (enum cdi_direction dir, basic_block bb)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
gcc_assert (dom_computed[dir_index]);
|
gcc_assert (dom_computed[dir_index]);
|
gcc_assert (!bb->dom[dir_index]);
|
gcc_assert (!bb->dom[dir_index]);
|
|
|
n_bbs_in_dom_tree[dir_index]++;
|
n_bbs_in_dom_tree[dir_index]++;
|
|
|
bb->dom[dir_index] = et_new_tree (bb);
|
bb->dom[dir_index] = et_new_tree (bb);
|
|
|
if (dom_computed[dir_index] == DOM_OK)
|
if (dom_computed[dir_index] == DOM_OK)
|
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
}
|
}
|
|
|
void
|
void
|
delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
|
delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
gcc_assert (dom_computed[dir_index]);
|
gcc_assert (dom_computed[dir_index]);
|
|
|
et_free_tree (bb->dom[dir_index]);
|
et_free_tree (bb->dom[dir_index]);
|
bb->dom[dir_index] = NULL;
|
bb->dom[dir_index] = NULL;
|
n_bbs_in_dom_tree[dir_index]--;
|
n_bbs_in_dom_tree[dir_index]--;
|
|
|
if (dom_computed[dir_index] == DOM_OK)
|
if (dom_computed[dir_index] == DOM_OK)
|
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
|
}
|
}
|
|
|
/* Returns the first son of BB in the dominator or postdominator tree
|
/* Returns the first son of BB in the dominator or postdominator tree
|
as determined by DIR. */
|
as determined by DIR. */
|
|
|
basic_block
|
basic_block
|
first_dom_son (enum cdi_direction dir, basic_block bb)
|
first_dom_son (enum cdi_direction dir, basic_block bb)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
struct et_node *son = bb->dom[dir_index]->son;
|
struct et_node *son = bb->dom[dir_index]->son;
|
|
|
return (basic_block) (son ? son->data : NULL);
|
return (basic_block) (son ? son->data : NULL);
|
}
|
}
|
|
|
/* Returns the next dominance son after BB in the dominator or postdominator
|
/* Returns the next dominance son after BB in the dominator or postdominator
|
tree as determined by DIR, or NULL if it was the last one. */
|
tree as determined by DIR, or NULL if it was the last one. */
|
|
|
basic_block
|
basic_block
|
next_dom_son (enum cdi_direction dir, basic_block bb)
|
next_dom_son (enum cdi_direction dir, basic_block bb)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
struct et_node *next = bb->dom[dir_index]->right;
|
struct et_node *next = bb->dom[dir_index]->right;
|
|
|
return (basic_block) (next->father->son == next ? NULL : next->data);
|
return (basic_block) (next->father->son == next ? NULL : next->data);
|
}
|
}
|
|
|
/* Return dominance availability for dominance info DIR. */
|
/* Return dominance availability for dominance info DIR. */
|
|
|
enum dom_state
|
enum dom_state
|
dom_info_state (enum cdi_direction dir)
|
dom_info_state (enum cdi_direction dir)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
return dom_computed[dir_index];
|
return dom_computed[dir_index];
|
}
|
}
|
|
|
/* Set the dominance availability for dominance info DIR to NEW_STATE. */
|
/* Set the dominance availability for dominance info DIR to NEW_STATE. */
|
|
|
void
|
void
|
set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
|
set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
dom_computed[dir_index] = new_state;
|
dom_computed[dir_index] = new_state;
|
}
|
}
|
|
|
/* Returns true if dominance information for direction DIR is available. */
|
/* Returns true if dominance information for direction DIR is available. */
|
|
|
bool
|
bool
|
dom_info_available_p (enum cdi_direction dir)
|
dom_info_available_p (enum cdi_direction dir)
|
{
|
{
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
unsigned int dir_index = dom_convert_dir_to_idx (dir);
|
|
|
return dom_computed[dir_index] != DOM_NONE;
|
return dom_computed[dir_index] != DOM_NONE;
|
}
|
}
|
|
|
void
|
void
|
debug_dominance_info (enum cdi_direction dir)
|
debug_dominance_info (enum cdi_direction dir)
|
{
|
{
|
basic_block bb, bb2;
|
basic_block bb, bb2;
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
if ((bb2 = get_immediate_dominator (dir, bb)))
|
if ((bb2 = get_immediate_dominator (dir, bb)))
|
fprintf (stderr, "%i %i\n", bb->index, bb2->index);
|
fprintf (stderr, "%i %i\n", bb->index, bb2->index);
|
}
|
}
|
|
|
/* Prints to stderr representation of the dominance tree (for direction DIR)
|
/* Prints to stderr representation of the dominance tree (for direction DIR)
|
rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false,
|
rooted in ROOT, indented by INDENT tabulators. If INDENT_FIRST is false,
|
the first line of the output is not indented. */
|
the first line of the output is not indented. */
|
|
|
static void
|
static void
|
debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
|
debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
|
unsigned indent, bool indent_first)
|
unsigned indent, bool indent_first)
|
{
|
{
|
basic_block son;
|
basic_block son;
|
unsigned i;
|
unsigned i;
|
bool first = true;
|
bool first = true;
|
|
|
if (indent_first)
|
if (indent_first)
|
for (i = 0; i < indent; i++)
|
for (i = 0; i < indent; i++)
|
fprintf (stderr, "\t");
|
fprintf (stderr, "\t");
|
fprintf (stderr, "%d\t", root->index);
|
fprintf (stderr, "%d\t", root->index);
|
|
|
for (son = first_dom_son (dir, root);
|
for (son = first_dom_son (dir, root);
|
son;
|
son;
|
son = next_dom_son (dir, son))
|
son = next_dom_son (dir, son))
|
{
|
{
|
debug_dominance_tree_1 (dir, son, indent + 1, !first);
|
debug_dominance_tree_1 (dir, son, indent + 1, !first);
|
first = false;
|
first = false;
|
}
|
}
|
|
|
if (first)
|
if (first)
|
fprintf (stderr, "\n");
|
fprintf (stderr, "\n");
|
}
|
}
|
|
|
/* Prints to stderr representation of the dominance tree (for direction DIR)
|
/* Prints to stderr representation of the dominance tree (for direction DIR)
|
rooted in ROOT. */
|
rooted in ROOT. */
|
|
|
void
|
void
|
debug_dominance_tree (enum cdi_direction dir, basic_block root)
|
debug_dominance_tree (enum cdi_direction dir, basic_block root)
|
{
|
{
|
debug_dominance_tree_1 (dir, root, 0, false);
|
debug_dominance_tree_1 (dir, root, 0, false);
|
}
|
}
|
|
|
