/* DDG - Data Dependence Graph implementation.
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
- Free Software Foundation, Inc.
+ Copyright (C) 2004-2014 Free Software Foundation, Inc.
Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com>
This file is part of GCC.
#include "tm_p.h"
#include "hard-reg-set.h"
#include "regs.h"
+#include "hashtab.h"
+#include "hash-set.h"
+#include "vec.h"
+#include "machmode.h"
+#include "input.h"
#include "function.h"
#include "flags.h"
#include "insn-config.h"
#include "insn-attr.h"
#include "except.h"
#include "recog.h"
+#include "predict.h"
+#include "basic-block.h"
#include "sched-int.h"
#include "target.h"
#include "cfgloop.h"
#include "sbitmap.h"
#include "expr.h"
#include "bitmap.h"
+#include "df.h"
#include "ddg.h"
+#include "rtl-iter.h"
#ifdef INSN_SCHEDULING
/* 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 (*x))
+ {
+ 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);
/* 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));
}
by use_insn, if use_insn uses an address register auto-inc'ed by
def_insn. */
bool
-autoinc_var_is_used_p (rtx def_insn, rtx use_insn)
+autoinc_var_is_used_p (rtx_insn *def_insn, rtx_insn *use_insn)
{
rtx note;
/* Return true if one of the definitions in INSN has MODE_CC. Otherwise
return false. */
static bool
-def_has_ccmode_p (rtx insn)
+def_has_ccmode_p (rtx_insn *insn)
{
- df_ref *def;
+ df_ref def;
- for (def = DF_INSN_DEFS (insn); *def; def++)
+ FOR_EACH_INSN_DEF (def, insn)
{
- enum machine_mode mode = GET_MODE (DF_REF_REG (*def));
+ machine_mode mode = GET_MODE (DF_REF_REG (def));
if (GET_MODE_CLASS (mode) == MODE_CC)
return true;
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);
+ rtx_insn *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
/* 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);
+ rtx_insn *use_insn = DF_REF_INSN (r_use->ref);
if (BLOCK_FOR_INSN (use_insn) != g->bb)
continue;
}
-static int
-walk_mems_2 (rtx *x, rtx mem)
-{
- if (MEM_P (*x))
- {
- if (may_alias_p (*x, mem))
- return 1;
-
- return -1;
- }
- return 0;
-}
-
-static int
-walk_mems_1 (rtx *x, rtx *pat)
+/* 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)
{
- if (MEM_P (*x))
+ subrtx_iterator::array_type array1;
+ subrtx_iterator::array_type array2;
+ FOR_EACH_SUBRTX (iter1, array1, PATTERN (insn1), NONCONST)
{
- /* Visit all MEMs in *PAT and check indepedence. */
- if (for_each_rtx (pat, (rtx_function) walk_mems_2, *x))
- /* Indicate that dependence was determined and stop traversal. */
- return 1;
-
- return -1;
+ 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 0;
-}
-
-/* Return 1 if two specified instructions have mem expr with conflict alias sets*/
-static int
-insns_may_alias_p (rtx insn1, rtx insn2)
-{
- /* For each pair of MEMs in INSN1 and INSN2 check their independence. */
- return for_each_rtx (&PATTERN (insn1), (rtx_function) walk_mems_1,
- &PATTERN (insn2));
+ return false;
}
/* Given two nodes, analyze their RTL insns and add intra-loop mem deps
int i;
/* Hold the dependency analysis state during dependency calculations. */
struct deps_desc tmp_deps;
- rtx head, tail;
+ rtx_insn *head, *tail;
/* Build the dependence information, using the sched_analyze function. */
init_deps_global ();
FOR_EACH_DEP (dest_node->insn, SD_LIST_BACK, sd_it, dep)
{
- rtx src_insn = DEP_PRO (dep);
+ rtx_insn *src_insn = DEP_PRO (dep);
ddg_node_ptr src_node;
/* Don't add dependencies on debug insns to non-debug insns
{
/* Don't bother calculating inter-loop dep if an intra-loop dep
already exists. */
- if (! TEST_BIT (dest_node->successors, j))
+ 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.
memory dependencies. Thus we add intra edges between
every two memory instructions in this case. */
if (flag_modulo_sched_allow_regmoves
- && !TEST_BIT (dest_node->predecessors, j))
+ && !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;
+ rtx_insn *insn, *first_note;
int i;
int num_nodes = 0;
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))
{
bitmap_clear (g->nodes[i].predecessors);
g->nodes[i].first_note = (first_note ? first_note : insn);
g->nodes[i++].insn = insn;
- first_note = NULL_RTX;
+ first_note = NULL;
}
/* We must have found a branch in DDG. */
}
/* 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);
/* 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;
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];
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;
if (e->distance > 0)
/* 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]);
bitmap_ior (succ, succ, node_succ);
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]);
bitmap_ior (preds, preds, node_preds);
bitmap_clear (scc_nodes);
bitmap_clear (from);
bitmap_clear (to);
- SET_BIT (from, dest->cuid);
- SET_BIT (to, src->cuid);
+ bitmap_set_bit (from, dest->cuid);
+ bitmap_set_bit (to, src->cuid);
if (find_nodes_on_paths (scc_nodes, g, from, to))
{
change = 0;
bitmap_copy (workset, tmp);
bitmap_clear (tmp);
- EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
+ 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;
}
}
change = 0;
bitmap_copy (workset, tmp);
bitmap_clear (tmp);
- EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
+ 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;
}
}
ddg_node_ptr v_node = e->dest;
int v = v_node->cuid;
- if (TEST_BIT (nodes, v)
+ if (bitmap_bit_p (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);
+ bitmap_set_bit (tmp, v);
result = 1;
}
}
g->nodes[src].aux.count = 0;
bitmap_clear (tmp);
- SET_BIT (tmp, src);
+ bitmap_set_bit (tmp, src);
while (change)
{
change = 0;
bitmap_copy (workset, tmp);
bitmap_clear (tmp);
- EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u, sbi)
+ EXECUTE_IF_SET_IN_BITMAP (workset, 0, u, sbi)
{
ddg_node_ptr u_node = &g->nodes[u];