/* DDG - Data Dependence Graph implementation.
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
- Free Software Foundation, Inc.
+ Copyright (C) 2004-2020 Free Software Foundation, Inc.
Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "toplev.h"
+#include "backend.h"
#include "rtl.h"
-#include "tm_p.h"
-#include "hard-reg-set.h"
-#include "regs.h"
-#include "function.h"
-#include "flags.h"
-#include "insn-config.h"
+#include "df.h"
#include "insn-attr.h"
-#include "except.h"
-#include "recog.h"
#include "sched-int.h"
-#include "target.h"
-#include "cfglayout.h"
-#include "cfgloop.h"
-#include "sbitmap.h"
-#include "expr.h"
-#include "bitmap.h"
#include "ddg.h"
+#include "rtl-iter.h"
#ifdef INSN_SCHEDULING
-/* A flag indicating that a ddg edge belongs to an SCC or not. */
-enum edge_flag {NOT_IN_SCC = 0, IN_SCC};
-
/* Forward declarations. */
static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr);
static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
/* Auxiliary variable for mem_read_insn_p/mem_write_insn_p. */
static bool mem_ref_p;
-/* Auxiliary function for mem_read_insn_p. */
-static int
-mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED)
-{
- if (MEM_P (*x))
- mem_ref_p = true;
- return 0;
-}
-
/* Auxiliary function for mem_read_insn_p. */
static void
-mark_mem_use_1 (rtx *x, void *data)
+mark_mem_use (rtx *x, void *)
{
- for_each_rtx (x, mark_mem_use, data);
+ subrtx_iterator::array_type array;
+ FOR_EACH_SUBRTX (iter, array, *x, NONCONST)
+ if (MEM_P (*iter))
+ {
+ mem_ref_p = true;
+ break;
+ }
}
/* Returns nonzero if INSN reads from memory. */
static bool
-mem_read_insn_p (rtx insn)
+mem_read_insn_p (rtx_insn *insn)
{
mem_ref_p = false;
- note_uses (&PATTERN (insn), mark_mem_use_1, NULL);
+ note_uses (&PATTERN (insn), mark_mem_use, NULL);
return mem_ref_p;
}
/* Returns nonzero if INSN writes to memory. */
static bool
-mem_write_insn_p (rtx insn)
+mem_write_insn_p (rtx_insn *insn)
{
mem_ref_p = false;
- note_stores (PATTERN (insn), mark_mem_store, NULL);
+ note_stores (insn, mark_mem_store, NULL);
return mem_ref_p;
}
/* Returns nonzero if INSN reads to or writes from memory. */
static bool
-mem_access_insn_p (rtx insn)
+mem_access_insn_p (rtx_insn *insn)
{
return rtx_mem_access_p (PATTERN (insn));
}
+/* Return true if DEF_INSN contains address being auto-inc or auto-dec
+ which is used in USE_INSN. Otherwise return false. The result is
+ being used to decide whether to remove the edge between def_insn and
+ use_insn when -fmodulo-sched-allow-regmoves is set. This function
+ doesn't need to consider the specific address register; no reg_moves
+ will be allowed for any life range defined by def_insn and used
+ by use_insn, if use_insn uses an address register auto-inc'ed by
+ def_insn. */
+bool
+autoinc_var_is_used_p (rtx_insn *def_insn, rtx_insn *use_insn)
+{
+ rtx note;
+
+ for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
+ if (REG_NOTE_KIND (note) == REG_INC
+ && reg_referenced_p (XEXP (note, 0), PATTERN (use_insn)))
+ return true;
+
+ return false;
+}
+
+/* Return true if one of the definitions in INSN has MODE_CC. Otherwise
+ return false. */
+static bool
+def_has_ccmode_p (rtx_insn *insn)
+{
+ df_ref def;
+
+ FOR_EACH_INSN_DEF (def, insn)
+ {
+ machine_mode mode = GET_MODE (DF_REF_REG (def));
+
+ if (GET_MODE_CLASS (mode) == MODE_CC)
+ return true;
+ }
+
+ return false;
+}
+
/* Computes the dependence parameters (latency, distance etc.), creates
a ddg_edge and adds it to the given DDG. */
static void
else if (DEP_TYPE (link) == REG_DEP_OUTPUT)
t = OUTPUT_DEP;
- gcc_assert (!DEBUG_INSN_P (dest_node->insn) || t == ANTI_DEP);
- gcc_assert (!DEBUG_INSN_P (src_node->insn) || t == ANTI_DEP);
-
/* We currently choose not to create certain anti-deps edges and
compensate for that by generating reg-moves based on the life-range
analysis. The anti-deps that will be deleted are the ones which
have true-deps edges in the opposite direction (in other words
- the kernel has only one def of the relevant register). TODO:
- support the removal of all anti-deps edges, i.e. including those
+ the kernel has only one def of the relevant register).
+ If the address that is being auto-inc or auto-dec in DEST_NODE
+ is used in SRC_NODE then do not remove the edge to make sure
+ reg-moves will not be created for this address.
+ TODO: support the removal of all anti-deps edges, i.e. including those
whose register has multiple defs in the loop. */
- if (flag_modulo_sched_allow_regmoves && (t == ANTI_DEP && dt == REG_DEP))
+ if (flag_modulo_sched_allow_regmoves
+ && (t == ANTI_DEP && dt == REG_DEP)
+ && !def_has_ccmode_p (dest_node->insn)
+ && !autoinc_var_is_used_p (dest_node->insn, src_node->insn))
{
rtx set;
{
int regno = REGNO (SET_DEST (set));
df_ref first_def;
- struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
+ class df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
first_def = df_bb_regno_first_def_find (g->bb, regno);
gcc_assert (first_def);
}
}
- latency = dep_cost (link);
- e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
- add_edge_to_ddg (g, e);
+ latency = dep_cost (link);
+ e = create_ddg_edge (src_node, dest_node, t, dt, latency, distance);
+ add_edge_to_ddg (g, e);
}
/* The same as the above function, but it doesn't require a link parameter. */
enum reg_note dep_kind;
struct _dep _dep, *dep = &_dep;
- gcc_assert (!DEBUG_INSN_P (to->insn) || d_t == ANTI_DEP);
- gcc_assert (!DEBUG_INSN_P (from->insn) || d_t == ANTI_DEP);
-
if (d_t == ANTI_DEP)
dep_kind = REG_DEP_ANTI;
else if (d_t == OUTPUT_DEP)
static void
add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
{
- int regno = DF_REF_REGNO (last_def);
struct df_link *r_use;
int has_use_in_bb_p = false;
- rtx def_insn = DF_REF_INSN (last_def);
- ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn);
- ddg_node_ptr use_node;
-#ifdef ENABLE_CHECKING
- struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
-#endif
+ int regno = DF_REF_REGNO (last_def);
+ ddg_node_ptr last_def_node = get_node_of_insn (g, DF_REF_INSN (last_def));
df_ref first_def = df_bb_regno_first_def_find (g->bb, regno);
+ ddg_node_ptr first_def_node = get_node_of_insn (g, DF_REF_INSN (first_def));
+ ddg_node_ptr use_node;
- gcc_assert (last_def_node);
- gcc_assert (first_def);
+ gcc_assert (last_def_node && first_def && first_def_node);
-#ifdef ENABLE_CHECKING
- if (DF_REF_ID (last_def) != DF_REF_ID (first_def))
- gcc_assert (!bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)));
-#endif
+ if (flag_checking && DF_REF_ID (last_def) != DF_REF_ID (first_def))
+ {
+ class df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
+ gcc_assert (!bitmap_bit_p (&bb_info->gen, DF_REF_ID (first_def)));
+ }
/* Create inter-loop true dependences and anti dependences. */
for (r_use = DF_REF_CHAIN (last_def); r_use != NULL; r_use = r_use->next)
{
- rtx use_insn = DF_REF_INSN (r_use->ref);
+ if (DF_REF_BB (r_use->ref) != g->bb)
+ continue;
+
+ gcc_assert (!DF_REF_IS_ARTIFICIAL (r_use->ref)
+ && DF_REF_INSN_INFO (r_use->ref) != NULL);
- if (BLOCK_FOR_INSN (use_insn) != g->bb)
+ rtx_insn *use_insn = DF_REF_INSN (r_use->ref);
+
+ if (DEBUG_INSN_P (use_insn))
continue;
/* ??? Do not handle uses with DF_REF_IN_NOTE notes. */
iteration. Any such upwards exposed use appears before
the last_def def. */
create_ddg_dep_no_link (g, last_def_node, use_node,
- DEBUG_INSN_P (use_insn) ? ANTI_DEP : TRUE_DEP,
- REG_DEP, 1);
+ TRUE_DEP, REG_DEP, 1);
}
- else if (!DEBUG_INSN_P (use_insn))
+ else
{
/* Add anti deps from last_def's uses in the current iteration
to the first def in the next iteration. We do not add ANTI
dep when there is an intra-loop TRUE dep in the opposite
direction, but use regmoves to fix such disregarded ANTI
deps when broken. If the first_def reaches the USE then
- there is such a dep. */
- ddg_node_ptr first_def_node = get_node_of_insn (g,
- DF_REF_INSN (first_def));
-
- gcc_assert (first_def_node);
-
- if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
- || !flag_modulo_sched_allow_regmoves)
- create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
- REG_DEP, 1);
-
+ there is such a dep.
+ Always create the edge if the use node is a branch in
+ order to prevent the creation of reg-moves.
+ If the address that is being auto-inc or auto-dec in LAST_DEF
+ is used in USE_INSN then do not remove the edge to make sure
+ reg-moves will not be created for that address. */
+ if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
+ || !flag_modulo_sched_allow_regmoves
+ || JUMP_P (use_node->insn)
+ || autoinc_var_is_used_p (DF_REF_INSN (last_def), use_insn)
+ || def_has_ccmode_p (DF_REF_INSN (last_def)))
+ create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
+ REG_DEP, 1);
}
}
/* Create an inter-loop output dependence between LAST_DEF (which is the
defs starting with a true dependence to a use which can be in the
next iteration; followed by an anti dependence of that use to the
first def (i.e. if there is a use between the two defs.) */
- if (!has_use_in_bb_p)
- {
- ddg_node_ptr dest_node;
-
- if (DF_REF_ID (last_def) == DF_REF_ID (first_def))
- return;
-
- dest_node = get_node_of_insn (g, DF_REF_INSN (first_def));
- gcc_assert (dest_node);
- create_ddg_dep_no_link (g, last_def_node, dest_node,
- OUTPUT_DEP, REG_DEP, 1);
- }
+ if (!has_use_in_bb_p && DF_REF_ID (last_def) != DF_REF_ID (first_def))
+ create_ddg_dep_no_link (g, last_def_node, first_def_node,
+ OUTPUT_DEP, REG_DEP, 1);
}
+
/* Build inter-loop dependencies, by looking at DF analysis backwards. */
static void
build_inter_loop_deps (ddg_ptr g)
{
unsigned rd_num;
- struct df_rd_bb_info *rd_bb_info;
+ class df_rd_bb_info *rd_bb_info;
bitmap_iterator bi;
rd_bb_info = DF_RD_BB_INFO (g->bb);
}
+/* Return true if two specified instructions have mem expr with conflict
+ alias sets. */
+static bool
+insns_may_alias_p (rtx_insn *insn1, rtx_insn *insn2)
+{
+ subrtx_iterator::array_type array1;
+ subrtx_iterator::array_type array2;
+ FOR_EACH_SUBRTX (iter1, array1, PATTERN (insn1), NONCONST)
+ {
+ const_rtx x1 = *iter1;
+ if (MEM_P (x1))
+ FOR_EACH_SUBRTX (iter2, array2, PATTERN (insn2), NONCONST)
+ {
+ const_rtx x2 = *iter2;
+ if (MEM_P (x2) && may_alias_p (x2, x1))
+ return true;
+ }
+ }
+ return false;
+}
+
+/* Given two nodes, analyze their RTL insns and add intra-loop mem deps
+ to ddg G. */
+static void
+add_intra_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
+{
+
+ if ((from->cuid == to->cuid)
+ || !insns_may_alias_p (from->insn, to->insn))
+ /* Do not create edge if memory references have disjoint alias sets
+ or 'to' and 'from' are the same instruction. */
+ return;
+
+ if (mem_write_insn_p (from->insn))
+ {
+ if (mem_read_insn_p (to->insn))
+ create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 0);
+ else
+ create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 0);
+ }
+ else if (!mem_read_insn_p (to->insn))
+ create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 0);
+}
+
/* Given two nodes, analyze their RTL insns and add inter-loop mem deps
to ddg G. */
static void
add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
{
- if (!insn_alias_sets_conflict_p (from->insn, to->insn))
+ if (!insns_may_alias_p (from->insn, to->insn))
/* Do not create edge if memory references have disjoint alias sets. */
return;
if (mem_write_insn_p (from->insn))
{
if (mem_read_insn_p (to->insn))
- create_ddg_dep_no_link (g, from, to,
- DEBUG_INSN_P (to->insn)
- ? ANTI_DEP : TRUE_DEP, MEM_DEP, 1);
+ create_ddg_dep_no_link (g, from, to, TRUE_DEP, MEM_DEP, 1);
else if (from->cuid != to->cuid)
- create_ddg_dep_no_link (g, from, to,
- DEBUG_INSN_P (to->insn)
- ? ANTI_DEP : OUTPUT_DEP, MEM_DEP, 1);
+ create_ddg_dep_no_link (g, from, to, OUTPUT_DEP, MEM_DEP, 1);
}
else
{
else if (from->cuid != to->cuid)
{
create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
- if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn))
- create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1);
- else
- create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
+ create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
}
}
-
}
/* Perform intra-block Data Dependency analysis and connect the nodes in
{
int i;
/* Hold the dependency analysis state during dependency calculations. */
- struct deps_desc tmp_deps;
- rtx head, tail;
+ class deps_desc tmp_deps;
+ rtx_insn *head, *tail;
/* Build the dependence information, using the sched_analyze function. */
init_deps_global ();
sd_iterator_def sd_it;
dep_t dep;
- if (! INSN_P (dest_node->insn))
- continue;
-
FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
{
- ddg_node_ptr src_node = get_node_of_insn (g, DEP_PRO (dep));
+ rtx_insn *src_insn = DEP_PRO (dep);
+ ddg_node_ptr src_node = get_node_of_insn (g, src_insn);
if (!src_node)
continue;
for (j = 0; j <= i; j++)
{
ddg_node_ptr j_node = &g->nodes[j];
- if (DEBUG_INSN_P (j_node->insn))
- continue;
+
if (mem_access_insn_p (j_node->insn))
- /* Don't bother calculating inter-loop dep if an intra-loop dep
- already exists. */
- if (! TEST_BIT (dest_node->successors, j))
+ {
+ /* Don't bother calculating inter-loop dep if an intra-loop dep
+ already exists. */
+ if (! bitmap_bit_p (dest_node->successors, j))
add_inter_loop_mem_dep (g, dest_node, j_node);
+ /* If -fmodulo-sched-allow-regmoves
+ is set certain anti-dep edges are not created.
+ It might be that these anti-dep edges are on the
+ path from one memory instruction to another such that
+ removing these edges could cause a violation of the
+ memory dependencies. Thus we add intra edges between
+ every two memory instructions in this case. */
+ if (flag_modulo_sched_allow_regmoves
+ && !bitmap_bit_p (dest_node->predecessors, j))
+ add_intra_loop_mem_dep (g, j_node, dest_node);
+ }
}
}
}
create_ddg (basic_block bb, int closing_branch_deps)
{
ddg_ptr g;
- rtx insn, first_note;
- int i;
+ rtx_insn *insn, *first_note;
+ int i, j;
int num_nodes = 0;
g = (ddg_ptr) xcalloc (1, sizeof (struct ddg));
for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
insn = NEXT_INSN (insn))
{
- if (! INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
+ if (!INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
continue;
- if (DEBUG_INSN_P (insn))
- g->num_debug++;
- else
+ if (NONDEBUG_INSN_P (insn))
{
if (mem_read_insn_p (insn))
g->num_loads++;
if (mem_write_insn_p (insn))
g->num_stores++;
+ num_nodes++;
}
- num_nodes++;
}
/* There is nothing to do for this BB. */
g->nodes = (ddg_node_ptr) xcalloc (num_nodes, sizeof (struct ddg_node));
g->closing_branch = NULL;
i = 0;
- first_note = NULL_RTX;
+ first_note = NULL;
for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
insn = NEXT_INSN (insn))
{
- if (! INSN_P (insn))
- {
- if (! first_note && NOTE_P (insn)
- && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK)
- first_note = insn;
- continue;
- }
+ if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn))
+ continue;
+
+ if (!first_note && (INSN_P (insn) || NOTE_P (insn)))
+ first_note = insn;
+
+ if (!INSN_P (insn) || GET_CODE (PATTERN (insn)) == USE)
+ continue;
+
if (JUMP_P (insn))
{
gcc_assert (!g->closing_branch);
g->closing_branch = &g->nodes[i];
}
- else if (GET_CODE (PATTERN (insn)) == USE)
+
+ if (NONDEBUG_INSN_P (insn))
{
- if (! first_note)
- first_note = insn;
- continue;
- }
+ g->nodes[i].cuid = i;
+ g->nodes[i].successors = sbitmap_alloc (num_nodes);
+ bitmap_clear (g->nodes[i].successors);
+ g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
+ bitmap_clear (g->nodes[i].predecessors);
+
+ gcc_checking_assert (first_note);
+ g->nodes[i].first_note = first_note;
+
+ g->nodes[i].aux.count = -1;
+ g->nodes[i].max_dist = XCNEWVEC (int, num_nodes);
+ for (j = 0; j < num_nodes; j++)
+ g->nodes[i].max_dist[j] = -1;
- g->nodes[i].cuid = i;
- g->nodes[i].successors = sbitmap_alloc (num_nodes);
- sbitmap_zero (g->nodes[i].successors);
- g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
- sbitmap_zero (g->nodes[i].predecessors);
- g->nodes[i].first_note = (first_note ? first_note : insn);
- g->nodes[i++].insn = insn;
- first_note = NULL_RTX;
+ g->nodes[i++].insn = insn;
+ }
+ first_note = NULL;
}
/* We must have found a branch in DDG. */
}
sbitmap_free (g->nodes[i].successors);
sbitmap_free (g->nodes[i].predecessors);
+ free (g->nodes[i].max_dist);
}
if (g->num_backarcs > 0)
free (g->backarcs);
}
/* Print the given DDG in VCG format. */
-void
+DEBUG_FUNCTION void
vcg_print_ddg (FILE *file, ddg_ptr g)
{
int src_cuid;
for (i = 0; i < sccs->num_sccs; i++)
{
fprintf (file, "SCC number: %d\n", i);
- EXECUTE_IF_SET_IN_SBITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
+ EXECUTE_IF_SET_IN_BITMAP (sccs->sccs[i]->nodes, 0, u, sbi)
{
fprintf (file, "insn num %d\n", u);
print_rtl_single (file, g->nodes[u].insn);
e->latency = l;
e->distance = d;
e->next_in = e->next_out = NULL;
- e->aux.info = 0;
+ e->in_scc = false;
return e;
}
/* Should have allocated the sbitmaps. */
gcc_assert (src->successors && dest->predecessors);
- SET_BIT (src->successors, dest->cuid);
- SET_BIT (dest->predecessors, src->cuid);
+ bitmap_set_bit (src->successors, dest->cuid);
+ bitmap_set_bit (dest->predecessors, src->cuid);
e->next_in = dest->in;
dest->in = e;
e->next_out = src->out;
for now that cycles in the data dependence graph contain a single backarc.
This simplifies the algorithm, and can be generalized later. */
static void
-set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
+set_recurrence_length (ddg_scc_ptr scc)
{
int j;
int result = -1;
for (j = 0; j < scc->num_backarcs; j++)
{
ddg_edge_ptr backarc = scc->backarcs[j];
- int length;
int distance = backarc->distance;
ddg_node_ptr src = backarc->dest;
ddg_node_ptr dest = backarc->src;
+ int length = src->max_dist[dest->cuid];
+
+ if (length < 0)
+ continue;
- length = longest_simple_path (g, src->cuid, dest->cuid, scc->nodes);
- if (length < 0 )
- {
- /* fprintf (stderr, "Backarc not on simple cycle in SCC.\n"); */
- continue;
- }
length += backarc->latency;
result = MAX (result, (length / distance));
}
}
/* Create a new SCC given the set of its nodes. Compute its recurrence_length
- and mark edges that belong to this scc as IN_SCC. */
+ and mark edges that belong to this scc. */
static ddg_scc_ptr
-create_scc (ddg_ptr g, sbitmap nodes)
+create_scc (ddg_ptr g, sbitmap nodes, int id)
{
ddg_scc_ptr scc;
unsigned int u = 0;
scc->backarcs = NULL;
scc->num_backarcs = 0;
scc->nodes = sbitmap_alloc (g->num_nodes);
- sbitmap_copy (scc->nodes, nodes);
+ bitmap_copy (scc->nodes, nodes);
/* Mark the backarcs that belong to this SCC. */
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u, sbi)
+ EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi)
{
ddg_edge_ptr e;
ddg_node_ptr n = &g->nodes[u];
+ gcc_assert (n->aux.count == -1);
+ n->aux.count = id;
+
for (e = n->out; e; e = e->next_out)
- if (TEST_BIT (nodes, e->dest->cuid))
+ if (bitmap_bit_p (nodes, e->dest->cuid))
{
- e->aux.count = IN_SCC;
+ e->in_scc = true;
if (e->distance > 0)
add_backarc_to_scc (scc, e);
}
}
- set_recurrence_length (scc, g);
return scc;
}
/* Given the instruction INSN return the node that represents it. */
ddg_node_ptr
-get_node_of_insn (ddg_ptr g, rtx insn)
+get_node_of_insn (ddg_ptr g, rtx_insn *insn)
{
int i;
unsigned int i = 0;
sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
+ EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi)
{
const sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
- sbitmap_a_or_b (succ, succ, node_succ);
+ bitmap_ior (succ, succ, node_succ);
};
/* We want those that are not in ops. */
- sbitmap_difference (succ, succ, ops);
+ bitmap_and_compl (succ, succ, ops);
}
/* Given a set OPS of nodes in the DDG, find the set of their predecessors
unsigned int i = 0;
sbitmap_iterator sbi;
- EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i, sbi)
+ EXECUTE_IF_SET_IN_BITMAP (ops, 0, i, sbi)
{
const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
- sbitmap_a_or_b (preds, preds, node_preds);
+ bitmap_ior (preds, preds, node_preds);
};
/* We want those that are not in ops. */
- sbitmap_difference (preds, preds, ops);
+ bitmap_and_compl (preds, preds, ops);
}
(int (*) (const void *, const void *)) compare_sccs);
}
-#ifdef ENABLE_CHECKING
/* Check that every node in SCCS belongs to exactly one strongly connected
component and that no element of SCCS is empty. */
static void
check_sccs (ddg_all_sccs_ptr sccs, int num_nodes)
{
int i = 0;
- sbitmap tmp = sbitmap_alloc (num_nodes);
+ auto_sbitmap tmp (num_nodes);
- sbitmap_zero (tmp);
+ bitmap_clear (tmp);
for (i = 0; i < sccs->num_sccs; i++)
{
- gcc_assert (!sbitmap_empty_p (sccs->sccs[i]->nodes));
+ gcc_assert (!bitmap_empty_p (sccs->sccs[i]->nodes));
/* Verify that every node in sccs is in exactly one strongly
connected component. */
- gcc_assert (!sbitmap_any_common_bits (tmp, sccs->sccs[i]->nodes));
- sbitmap_a_or_b (tmp, tmp, sccs->sccs[i]->nodes);
+ gcc_assert (!bitmap_intersect_p (tmp, sccs->sccs[i]->nodes));
+ bitmap_ior (tmp, tmp, sccs->sccs[i]->nodes);
}
- sbitmap_free (tmp);
}
-#endif
/* Perform the Strongly Connected Components decomposing algorithm on the
DDG and return DDG_ALL_SCCS structure that contains them. */
ddg_all_sccs_ptr
create_ddg_all_sccs (ddg_ptr g)
{
- int i;
+ int i, j, k, scc, way;
int num_nodes = g->num_nodes;
- sbitmap from = sbitmap_alloc (num_nodes);
- sbitmap to = sbitmap_alloc (num_nodes);
- sbitmap scc_nodes = sbitmap_alloc (num_nodes);
+ auto_sbitmap from (num_nodes);
+ auto_sbitmap to (num_nodes);
+ auto_sbitmap scc_nodes (num_nodes);
ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
xmalloc (sizeof (struct ddg_all_sccs));
ddg_node_ptr dest = backarc->dest;
/* If the backarc already belongs to an SCC, continue. */
- if (backarc->aux.count == IN_SCC)
+ if (backarc->in_scc)
continue;
- sbitmap_zero (scc_nodes);
- sbitmap_zero (from);
- sbitmap_zero (to);
- SET_BIT (from, dest->cuid);
- SET_BIT (to, src->cuid);
+ bitmap_clear (scc_nodes);
+ bitmap_clear (from);
+ bitmap_clear (to);
+ bitmap_set_bit (from, dest->cuid);
+ bitmap_set_bit (to, src->cuid);
if (find_nodes_on_paths (scc_nodes, g, from, to))
{
- scc = create_scc (g, scc_nodes);
+ scc = create_scc (g, scc_nodes, sccs->num_sccs);
add_scc_to_ddg (sccs, scc);
}
}
+
+ /* Init max_dist arrays for Floyd–Warshall-like
+ longest patch calculation algorithm. */
+ for (k = 0; k < num_nodes; k++)
+ {
+ ddg_edge_ptr e;
+ ddg_node_ptr n = &g->nodes[k];
+
+ if (n->aux.count == -1)
+ continue;
+
+ n->max_dist[k] = 0;
+ for (e = n->out; e; e = e->next_out)
+ if (e->distance == 0 && g->nodes[e->dest->cuid].aux.count == n->aux.count)
+ n->max_dist[e->dest->cuid] = e->latency;
+ }
+
+ /* Run main Floid-Warshall loop. We use only non-backarc edges
+ inside each scc. */
+ for (k = 0; k < num_nodes; k++)
+ {
+ scc = g->nodes[k].aux.count;
+ if (scc != -1)
+ {
+ for (i = 0; i < num_nodes; i++)
+ if (g->nodes[i].aux.count == scc)
+ for (j = 0; j < num_nodes; j++)
+ if (g->nodes[j].aux.count == scc
+ && g->nodes[i].max_dist[k] >= 0
+ && g->nodes[k].max_dist[j] >= 0)
+ {
+ way = g->nodes[i].max_dist[k] + g->nodes[k].max_dist[j];
+ if (g->nodes[i].max_dist[j] < way)
+ g->nodes[i].max_dist[j] = way;
+ }
+ }
+ }
+
+ /* Calculate recurrence_length using max_dist info. */
+ for (i = 0; i < sccs->num_sccs; i++)
+ set_recurrence_length (sccs->sccs[i]);
+
order_sccs (sccs);
- sbitmap_free (from);
- sbitmap_free (to);
- sbitmap_free (scc_nodes);
-#ifdef ENABLE_CHECKING
- check_sccs (sccs, num_nodes);
-#endif
+
+ if (flag_checking)
+ check_sccs (sccs, num_nodes);
+
return sccs;
}
for (i = 0; i < all_sccs->num_sccs; i++)
free_scc (all_sccs->sccs[i]);
+ free (all_sccs->sccs);
free (all_sccs);
}
int
find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
{
- int answer;
int change;
unsigned int u = 0;
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);
- sbitmap tmp = sbitmap_alloc (num_nodes);
+ auto_sbitmap workset (num_nodes);
+ auto_sbitmap reachable_from (num_nodes);
+ auto_sbitmap reach_to (num_nodes);
+ auto_sbitmap tmp (num_nodes);
- sbitmap_copy (reachable_from, from);
- sbitmap_copy (tmp, from);
+ bitmap_copy (reachable_from, from);
+ bitmap_copy (tmp, from);
change = 1;
while (change)
{
change = 0;
- sbitmap_copy (workset, tmp);
- sbitmap_zero (tmp);
- EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
+ bitmap_copy (workset, tmp);
+ bitmap_clear (tmp);
+ EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi)
{
ddg_edge_ptr e;
ddg_node_ptr u_node = &g->nodes[u];
ddg_node_ptr v_node = e->dest;
int v = v_node->cuid;
- if (!TEST_BIT (reachable_from, v))
+ if (!bitmap_bit_p (reachable_from, v))
{
- SET_BIT (reachable_from, v);
- SET_BIT (tmp, v);
+ bitmap_set_bit (reachable_from, v);
+ bitmap_set_bit (tmp, v);
change = 1;
}
}
}
}
- sbitmap_copy (reach_to, to);
- sbitmap_copy (tmp, to);
+ bitmap_copy (reach_to, to);
+ bitmap_copy (tmp, to);
change = 1;
while (change)
{
change = 0;
- sbitmap_copy (workset, tmp);
- sbitmap_zero (tmp);
- EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
+ bitmap_copy (workset, tmp);
+ bitmap_clear (tmp);
+ EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi)
{
ddg_edge_ptr e;
ddg_node_ptr u_node = &g->nodes[u];
ddg_node_ptr v_node = e->src;
int v = v_node->cuid;
- if (!TEST_BIT (reach_to, v))
+ if (!bitmap_bit_p (reach_to, v))
{
- SET_BIT (reach_to, v);
- SET_BIT (tmp, v);
+ bitmap_set_bit (reach_to, v);
+ bitmap_set_bit (tmp, v);
change = 1;
}
}
}
}
- answer = sbitmap_a_and_b_cg (result, reachable_from, reach_to);
- sbitmap_free (workset);
- sbitmap_free (reachable_from);
- sbitmap_free (reach_to);
- sbitmap_free (tmp);
- return answer;
-}
-
-
-/* Updates the counts of U_NODE's successors (that belong to NODES) to be
- at-least as large as the count of U_NODE plus the latency between them.
- Sets a bit in TMP for each successor whose count was changed (increased).
- Returns nonzero if any count was changed. */
-static int
-update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
-{
- ddg_edge_ptr e;
- int result = 0;
-
- for (e = u_node->out; e; e = e->next_out)
- {
- ddg_node_ptr v_node = e->dest;
- int v = v_node->cuid;
-
- if (TEST_BIT (nodes, v)
- && (e->distance == 0)
- && (v_node->aux.count < u_node->aux.count + e->latency))
- {
- v_node->aux.count = u_node->aux.count + e->latency;
- SET_BIT (tmp, v);
- result = 1;
- }
- }
- return result;
-}
-
-
-/* Find the length of a longest path from SRC to DEST in G,
- going only through NODES, and disregarding backarcs. */
-int
-longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
-{
- int i;
- unsigned int u = 0;
- int change = 1;
- int result;
- int num_nodes = g->num_nodes;
- sbitmap workset = sbitmap_alloc (num_nodes);
- sbitmap tmp = sbitmap_alloc (num_nodes);
-
-
- /* Data will hold the distance of the longest path found so far from
- src to each node. Initialize to -1 = less than minimum. */
- for (i = 0; i < g->num_nodes; i++)
- g->nodes[i].aux.count = -1;
- g->nodes[src].aux.count = 0;
-
- sbitmap_zero (tmp);
- SET_BIT (tmp, src);
-
- while (change)
- {
- sbitmap_iterator sbi;
-
- change = 0;
- sbitmap_copy (workset, tmp);
- sbitmap_zero (tmp);
- 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);
- sbitmap_free (tmp);
- return result;
+ return bitmap_and (result, reachable_from, reach_to);
}
#endif /* INSN_SCHEDULING */
projects / thirdparty / gcc.git / blobdiff