OSDN Git Service
(root)
/
pf3gnuchains
/
gcc-fork.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
* tree.h (TREE_ADDRESSABLE): Remove bogus usage for FIELD_DECL.
[pf3gnuchains/gcc-fork.git]
/
gcc
/
dominance.c
diff --git
a/gcc/dominance.c
b/gcc/dominance.c
index
2cc1414
..
f7db0f1
100644
(file)
--- a/
gcc/dominance.c
+++ b/
gcc/dominance.c
@@
-1,6
+1,6
@@
/* 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
Free
- Software Foundation, Inc.
+ Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008
, 2009, 2010
+
Free
Software Foundation, Inc.
Contributed by Michael Matz (matz@ifh.de).
This file is part of GCC.
Contributed by Michael Matz (matz@ifh.de).
This file is part of GCC.
@@
-47,6
+47,7
@@
#include "vecprim.h"
#include "pointer-set.h"
#include "graphds.h"
#include "vecprim.h"
#include "pointer-set.h"
#include "graphds.h"
+#include "bitmap.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
/* 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
@@
-711,13
+712,13
@@
get_immediate_dominator (enum cdi_direction dir, basic_block bb)
/* Set the immediate dominator of the block possibly removing
existing edge. NULL can be used to remove any edge. */
/* Set the immediate dominator of the block possibly removing
existing edge. NULL can be used to remove any edge. */
-
inline
void
+void
set_immediate_dominator (enum cdi_direction dir, basic_block bb,
basic_block dominated_by)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *node = bb->dom[dir_index];
set_immediate_dominator (enum cdi_direction dir, basic_block bb,
basic_block dominated_by)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *node = bb->dom[dir_index];
-
+
gcc_assert (dom_computed[dir_index]);
if (node->father)
gcc_assert (dom_computed[dir_index]);
if (node->father)
@@
-739,7
+740,6
@@
set_immediate_dominator (enum cdi_direction dir, basic_block bb,
VEC (basic_block, heap) *
get_dominated_by (enum cdi_direction dir, basic_block bb)
{
VEC (basic_block, heap) *
get_dominated_by (enum cdi_direction dir, basic_block bb)
{
- int n;
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
VEC (basic_block, heap) *bbs = NULL;
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
VEC (basic_block, heap) *bbs = NULL;
@@
-750,7
+750,7
@@
get_dominated_by (enum cdi_direction dir, basic_block bb)
return NULL;
VEC_safe_push (basic_block, heap, bbs, (basic_block) son->data);
return NULL;
VEC_safe_push (basic_block, heap, bbs, (basic_block) son->data);
- for (ason = son->right
, n = 1
; 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);
return bbs;
VEC_safe_push (basic_block, heap, bbs, (basic_block) ason->data);
return bbs;
@@
-759,7
+759,7
@@
get_dominated_by (enum cdi_direction dir, basic_block bb)
/* Returns the list of basic blocks that are immediately dominated (in
direction DIR) by some block between N_REGION ones stored in REGION,
except for blocks in the REGION itself. */
/* Returns the list of basic blocks that are immediately dominated (in
direction DIR) by some block between N_REGION ones stored in REGION,
except for blocks in the REGION itself. */
-
+
VEC (basic_block, heap) *
get_dominated_by_region (enum cdi_direction dir, basic_block *region,
unsigned n_region)
VEC (basic_block, heap) *
get_dominated_by_region (enum cdi_direction dir, basic_block *region,
unsigned n_region)
@@
-816,7
+816,7
@@
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *bb_node, *to_node, *son;
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *bb_node, *to_node, *son;
-
+
bb_node = bb->dom[dir_index];
to_node = to->dom[dir_index];
bb_node = bb->dom[dir_index];
to_node = to->dom[dir_index];
@@
-863,7
+863,7
@@
nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
unsigned i, first;
bitmap_iterator bi;
basic_block dom;
unsigned i, first;
bitmap_iterator bi;
basic_block dom;
-
+
first = bitmap_first_set_bit (blocks);
dom = BASIC_BLOCK (first);
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
first = bitmap_first_set_bit (blocks);
dom = BASIC_BLOCK (first);
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
@@
-882,11
+882,11
@@
nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
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
will contain.
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
will contain.
-
+
The dominator tree is always a simple acyclic tree, so there are
only three possible relations two nodes in the dominator tree have
to each other:
The dominator tree is always a simple acyclic tree, so there are
only three possible relations two nodes in the dominator tree have
to each other:
-
+
1. Node A is above Node B (and thus, Node A dominates node B)
A
1. Node A is above Node B (and thus, Node A dominates node B)
A
@@
-900,10
+900,10
@@
nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
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
down, and we will hit A *after* B on the walk back up
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
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
|
A
B
|
A
@@
-912,10
+912,10
@@
nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
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.
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 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
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
-
+
3. Node A and B are siblings (and thus, neither dominates the other)
C
3. Node A and B are siblings (and thus, neither dominates the other)
C
@@
-938,7
+938,7
@@
nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
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);
}
@@
-951,10
+951,10
@@
nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
/* Return TRUE in case BB1 is dominated by BB2. */
bool
dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
/* Return TRUE in case BB1 is dominated by BB2. */
bool
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);
struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
-
+
gcc_assert (dom_computed[dir_index]);
if (dom_computed[dir_index] == DOM_OK)
gcc_assert (dom_computed[dir_index]);
if (dom_computed[dir_index] == DOM_OK)
@@
-1390,7
+1390,7
@@
add_to_dominance_info (enum cdi_direction dir, basic_block bb)
gcc_assert (!bb->dom[dir_index]);
n_bbs_in_dom_tree[dir_index]++;
gcc_assert (!bb->dom[dir_index]);
n_bbs_in_dom_tree[dir_index]++;
-
+
bb->dom[dir_index] = et_new_tree (bb);
if (dom_computed[dir_index] == DOM_OK)
bb->dom[dir_index] = et_new_tree (bb);
if (dom_computed[dir_index] == DOM_OK)