/* DDG - Data Dependence Graph implementation.
- Copyright (C) 2004
+ Copyright (C) 2004, 2005
Free Software Foundation, Inc.
Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#include "config.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
-#include "basic-block.h"
#include "regs.h"
#include "function.h"
#include "flags.h"
if (interloop)
distance = 1;
- if (!link)
- abort ();
+ gcc_assert (link);
/* Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!! */
if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
else
free (e);
}
+ else if (t == ANTI_DEP && dt == REG_DEP)
+ free (e); /* We can fix broken anti register deps using reg-moves. */
else
add_edge_to_ddg (g, e);
}
rtx use_insn = DF_REF_INSN (r_use->ref);
ddg_node_ptr dest_node = get_node_of_insn (g, use_insn);
- if (!src_node || !dest_node)
- abort ();
+ gcc_assert (src_node && dest_node);
/* Any such upwards exposed use appears before the rd def. */
use_before_def = true;
use_node = get_node_of_insn (g, use->insn);
def_node = get_node_of_insn (g, first_def->insn);
- if (!use_node || !def_node)
- abort ();
+ gcc_assert (use_node && def_node);
/* Make sure there are no defs after USE. */
for (i = use_node->cuid + 1; i < g->num_nodes; i++)
if (df_find_def (df, g->nodes[i].insn, use->reg))
return;
/* We must not add ANTI dep when there is an intra-loop TRUE dep in
- the opozite direction. If the first_def reaches the USE then there is
+ the opposite direction. If the first_def reaches the USE then there is
such a dep. */
if (! bitmap_bit_p (bb_info->rd_gen, first_def->id))
create_ddg_dep_no_link (g, use_node, def_node, ANTI_DEP, REG_DEP, 1);
static void
build_inter_loop_deps (ddg_ptr g, struct df *df)
{
- int rd_num, u_num;
+ unsigned rd_num, u_num;
struct bb_info *bb_info;
+ bitmap_iterator bi;
bb_info = DF_BB_INFO (df, g->bb);
/* Find inter-loop output and true deps by connecting downward exposed defs
to the first def of the BB and to upwards exposed uses. */
- EXECUTE_IF_SET_IN_BITMAP (bb_info->rd_gen, 0, rd_num,
+ EXECUTE_IF_SET_IN_BITMAP (bb_info->rd_gen, 0, rd_num, bi)
{
struct ref *rd = df->defs[rd_num];
add_deps_for_def (g, df, rd);
- });
+ }
/* Find inter-loop anti deps. We are interested in uses of the block that
appear below all defs; this implies that these uses are killed. */
- EXECUTE_IF_SET_IN_BITMAP (bb_info->ru_kill, 0, u_num,
+ EXECUTE_IF_SET_IN_BITMAP (bb_info->ru_kill, 0, u_num, bi)
{
struct ref *use = df->uses[u_num];
/* We are interested in uses of this BB. */
if (BLOCK_FOR_INSN (use->insn) == g->bb)
add_deps_for_use (g, df,use);
- });
+ }
}
/* Given two nodes, analyze their RTL insns and add inter-loop mem deps
{
if (! INSN_P (insn))
{
- if (! first_note && GET_CODE (insn) == NOTE
+ if (! first_note && NOTE_P (insn)
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
first_note = insn;
continue;
}
- if (GET_CODE (insn) == JUMP_INSN)
+ if (JUMP_P (insn))
{
- if (g->closing_branch)
- abort (); /* Found two branches in DDG. */
- else
- g->closing_branch = &g->nodes[i];
+ gcc_assert (!g->closing_branch);
+ g->closing_branch = &g->nodes[i];
}
else if (GET_CODE (PATTERN (insn)) == USE)
{
g->nodes[i++].insn = insn;
first_note = NULL_RTX;
}
-
- if (!g->closing_branch)
- abort (); /* Found no branch in DDG. */
+
+ /* We must have found a branch in DDG. */
+ gcc_assert (g->closing_branch);
+
/* Build the data dependency graph. */
build_intra_loop_deps (g);
ddg_node_ptr src = e->src;
ddg_node_ptr dest = e->dest;
- if (!src->successors || !dest->predecessors)
- abort (); /* Should have allocated the sbitmaps. */
+ /* Should have allocated the sbitmaps. */
+ gcc_assert (src->successors && dest->predecessors);
SET_BIT (src->successors, dest->cuid);
SET_BIT (dest->predecessors, src->cuid);
create_scc (ddg_ptr g, sbitmap nodes)
{
ddg_scc_ptr scc;
- int u;
+ unsigned int u;
+ sbitmap_iterator sbi;
scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
scc->backarcs = NULL;
sbitmap_copy (scc->nodes, nodes);
/* Mark the backarcs that belong to this SCC. */
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
+ EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
{
ddg_edge_ptr e;
ddg_node_ptr n = &g->nodes[u];
if (e->distance > 0)
add_backarc_to_scc (scc, e);
}
- });
+ }
set_recurrence_length (scc, g);
return scc;
void
find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
{
- int i;
+ unsigned int i;
+ sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
+ EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
{
const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
sbitmap_a_or_b (succ, succ, node_succ);
- });
+ };
/* We want those that are not in ops. */
sbitmap_difference (succ, succ, ops);
void
find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
{
- int i;
+ unsigned int i;
+ sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
+ EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
{
const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
sbitmap_a_or_b (preds, preds, node_preds);
- });
+ };
/* We want those that are not in ops. */
sbitmap_difference (preds, preds, ops);
\f
/* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
nodes - find all nodes that lie on paths from FROM to TO (not excluding
- nodes from FROM and TO). Return non zero if nodes exist. */
+ nodes from FROM and TO). Return nonzero if nodes exist. */
int
find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
{
int answer;
- int change, u;
+ int change;
+ unsigned int u;
int num_nodes = g->num_nodes;
+ sbitmap_iterator sbi;
+
sbitmap workset = sbitmap_alloc (num_nodes);
sbitmap reachable_from = sbitmap_alloc (num_nodes);
sbitmap reach_to = sbitmap_alloc (num_nodes);
change = 0;
sbitmap_copy (workset, tmp);
sbitmap_zero (tmp);
- EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
+ EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
{
ddg_edge_ptr e;
ddg_node_ptr u_node = &g->nodes[u];
change = 1;
}
}
- });
+ }
}
sbitmap_copy (reach_to, to);
change = 0;
sbitmap_copy (workset, tmp);
sbitmap_zero (tmp);
- EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
+ EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
{
ddg_edge_ptr e;
ddg_node_ptr u_node = &g->nodes[u];
change = 1;
}
}
- });
+ }
}
answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
int
longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
{
- int i, u;
+ int i;
+ unsigned int u;
int change = 1;
int result;
int num_nodes = g->num_nodes;
while (change)
{
+ sbitmap_iterator sbi;
+
change = 0;
sbitmap_copy (workset, tmp);
sbitmap_zero (tmp);
- EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
+ EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
{
ddg_node_ptr u_node = &g->nodes[u];
change |= update_dist_to_successors (u_node, nodes, tmp);
- });
+ }
}
result = g->nodes[dest].aux.count;
sbitmap_free (workset);
OSDN Git Service
