#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "ggc.h"
-#include "flags.h"
-#include "tree.h"
-#include "basic-block.h"
-#include "tree-pretty-print.h"
#include "gimple-pretty-print.h"
#include "tree-flow.h"
-#include "tree-dump.h"
-#include "timevar.h"
#include "cfgloop.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
loop->num);
}
-/* Returns true if A and B are accesses to different objects, or to different
- fields of the same object. */
-
-static bool
-disjoint_objects_p (tree a, tree b)
-{
- tree base_a, base_b;
- VEC (tree, heap) *comp_a = NULL, *comp_b = NULL;
- bool ret;
-
- base_a = get_base_address (a);
- base_b = get_base_address (b);
-
- if (DECL_P (base_a)
- && DECL_P (base_b)
- && base_a != base_b)
- return true;
-
- if (!operand_equal_p (base_a, base_b, 0))
- return false;
-
- /* Compare the component references of A and B. We must start from the inner
- ones, so record them to the vector first. */
- while (handled_component_p (a))
- {
- VEC_safe_push (tree, heap, comp_a, a);
- a = TREE_OPERAND (a, 0);
- }
- while (handled_component_p (b))
- {
- VEC_safe_push (tree, heap, comp_b, b);
- b = TREE_OPERAND (b, 0);
- }
-
- ret = false;
- while (1)
- {
- if (VEC_length (tree, comp_a) == 0
- || VEC_length (tree, comp_b) == 0)
- break;
-
- a = VEC_pop (tree, comp_a);
- b = VEC_pop (tree, comp_b);
-
- /* Real and imaginary part of a variable do not alias. */
- if ((TREE_CODE (a) == REALPART_EXPR
- && TREE_CODE (b) == IMAGPART_EXPR)
- || (TREE_CODE (a) == IMAGPART_EXPR
- && TREE_CODE (b) == REALPART_EXPR))
- {
- ret = true;
- break;
- }
-
- if (TREE_CODE (a) != TREE_CODE (b))
- break;
-
- /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
- DR_BASE_OBJECT are always zero. */
- if (TREE_CODE (a) == ARRAY_REF)
- continue;
- else if (TREE_CODE (a) == COMPONENT_REF)
- {
- if (operand_equal_p (TREE_OPERAND (a, 1), TREE_OPERAND (b, 1), 0))
- continue;
-
- /* Different fields of unions may overlap. */
- base_a = TREE_OPERAND (a, 0);
- if (TREE_CODE (TREE_TYPE (base_a)) == UNION_TYPE)
- break;
-
- /* Different fields of structures cannot. */
- ret = true;
- break;
- }
- else
- break;
- }
-
- VEC_free (tree, heap, comp_a);
- VEC_free (tree, heap, comp_b);
-
- return ret;
-}
-
/* Returns false if we can prove that data references A and B do not alias,
true otherwise. */
bool
dr_may_alias_p (const struct data_reference *a, const struct data_reference *b)
{
- const_tree addr_a = DR_BASE_ADDRESS (a);
- const_tree addr_b = DR_BASE_ADDRESS (b);
- const_tree type_a, type_b;
- const_tree decl_a = NULL_TREE, decl_b = NULL_TREE;
+ tree addr_a = DR_BASE_OBJECT (a);
+ tree addr_b = DR_BASE_OBJECT (b);
- /* If the accessed objects are disjoint, the memory references do not
- alias. */
- if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b)))
- return false;
-
- /* Query the alias oracle. */
if (DR_IS_WRITE (a) && DR_IS_WRITE (b))
- {
- if (!refs_output_dependent_p (DR_REF (a), DR_REF (b)))
- return false;
- }
+ return refs_output_dependent_p (addr_a, addr_b);
else if (DR_IS_READ (a) && DR_IS_WRITE (b))
- {
- if (!refs_anti_dependent_p (DR_REF (a), DR_REF (b)))
- return false;
- }
- else if (!refs_may_alias_p (DR_REF (a), DR_REF (b)))
- return false;
-
- if (!addr_a || !addr_b)
- return true;
-
- /* If the references are based on different static objects, they cannot
- alias (PTA should be able to disambiguate such accesses, but often
- it fails to). */
- if (TREE_CODE (addr_a) == ADDR_EXPR
- && TREE_CODE (addr_b) == ADDR_EXPR)
- return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0);
-
- /* An instruction writing through a restricted pointer is "independent" of any
- instruction reading or writing through a different restricted pointer,
- in the same block/scope. */
-
- type_a = TREE_TYPE (addr_a);
- type_b = TREE_TYPE (addr_b);
- gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
-
- if (TREE_CODE (addr_a) == SSA_NAME)
- decl_a = SSA_NAME_VAR (addr_a);
- if (TREE_CODE (addr_b) == SSA_NAME)
- decl_b = SSA_NAME_VAR (addr_b);
-
- if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b)
- && (DR_IS_WRITE (a) || DR_IS_WRITE (b))
- && decl_a && DECL_P (decl_a)
- && decl_b && DECL_P (decl_b)
- && decl_a != decl_b
- && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
- && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
- return false;
-
- return true;
+ return refs_anti_dependent_p (addr_a, addr_b);
+ return refs_may_alias_p (addr_a, addr_b);
}
static void compute_self_dependence (struct data_dependence_relation *);
/* If they are the same chrec, and are affine, they overlap
on every iteration. */
else if (eq_evolutions_p (chrec_a, chrec_b)
- && evolution_function_is_affine_multivariate_p (chrec_a, lnn))
+ && (evolution_function_is_affine_multivariate_p (chrec_a, lnn)
+ || operand_equal_p (chrec_a, chrec_b, 0)))
{
dependence_stats.num_same_subscript_function++;
*overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
}
/* If they aren't the same, and aren't affine, we can't do anything
- yet. */
+ yet. */
else if ((chrec_contains_symbols (chrec_a)
|| chrec_contains_symbols (chrec_b))
&& (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
tree fun_a = chrec_convert (type, access_fun_a, NULL);
tree fun_b = chrec_convert (type, access_fun_b, NULL);
tree difference = chrec_fold_minus (type, fun_a, fun_b);
+ tree minus_one;
/* When the fun_a - fun_b is not constant, the dependence is not
captured by the classic distance vector representation. */
return true;
}
- fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node);
+ minus_one = build_int_cst (type, -1);
+ fun_b = chrec_fold_multiply (type, fun_b, minus_one);
eq = omega_add_zero_eq (pb, omega_black);
if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
bool
compute_data_dependences_for_loop (struct loop *loop,
bool compute_self_and_read_read_dependences,
+ VEC (loop_p, heap) **loop_nest,
VEC (data_reference_p, heap) **datarefs,
VEC (ddr_p, heap) **dependence_relations)
{
bool res = true;
- VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
memset (&dependence_stats, 0, sizeof (dependence_stats));
is not computable, give up without spending time to compute other
dependences. */
if (!loop
- || !find_loop_nest (loop, &vloops)
+ || !find_loop_nest (loop, loop_nest)
|| find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
{
struct data_dependence_relation *ddr;
/* Insert a single relation into dependence_relations:
chrec_dont_know. */
- ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
+ ddr = initialize_data_dependence_relation (NULL, NULL, *loop_nest);
VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
res = false;
}
else
- compute_all_dependences (*datarefs, dependence_relations, vloops,
+ compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
compute_self_and_read_read_dependences);
if (dump_file && (dump_flags & TDF_STATS))
VEC_alloc (data_reference_p, heap, nb_data_refs);
VEC (ddr_p, heap) *dependence_relations =
VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
+ VEC (loop_p, heap) *loop_nest = VEC_alloc (loop_p, heap, 3);
/* Compute DDs on the whole function. */
- compute_data_dependences_for_loop (loop, false, &datarefs,
+ compute_data_dependences_for_loop (loop, false, &loop_nest, &datarefs,
&dependence_relations);
if (dump_file)
}
}
+ VEC_free (loop_p, heap, loop_nest);
free_dependence_relations (dependence_relations);
free_data_refs (datarefs);
}
{
unsigned int i;
struct data_dependence_relation *ddr;
- VEC (loop_p, heap) *loop_nest = NULL;
FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
- {
- if (ddr == NULL)
- continue;
- if (loop_nest == NULL)
- loop_nest = DDR_LOOP_NEST (ddr);
- else
- gcc_assert (DDR_LOOP_NEST (ddr) == NULL
- || DDR_LOOP_NEST (ddr) == loop_nest);
+ if (ddr)
free_dependence_relation (ddr);
- }
- if (loop_nest)
- VEC_free (loop_p, heap, loop_nest);
VEC_free (ddr_p, heap, dependence_relations);
}
for (e = v->succ; e; e = e->succ_next)
fprintf (file, " %d", e->dest);
- fprintf (file, ") \n");
+ fprintf (file, ")\n");
print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
fprintf (file, ")\n");
}
dump_rdg (stderr, rdg);
}
+static void
+dot_rdg_1 (FILE *file, struct graph *rdg)
+{
+ int i;
+
+ fprintf (file, "digraph RDG {\n");
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ {
+ struct vertex *v = &(rdg->vertices[i]);
+ struct graph_edge *e;
+
+ /* Highlight reads from memory. */
+ if (RDG_MEM_READS_STMT (rdg, i))
+ fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
+
+ /* Highlight stores to memory. */
+ if (RDG_MEM_WRITE_STMT (rdg, i))
+ fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
+
+ if (v->succ)
+ for (e = v->succ; e; e = e->succ_next)
+ switch (RDGE_TYPE (e))
+ {
+ case input_dd:
+ fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
+ break;
+
+ case output_dd:
+ fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
+ break;
+
+ case flow_dd:
+ /* These are the most common dependences: don't print these. */
+ fprintf (file, "%d -> %d \n", i, e->dest);
+ break;
+
+ case anti_dd:
+ fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ }
+
+ fprintf (file, "}\n\n");
+}
+
+/* Display the Reduced Dependence Graph using dotty. */
+extern void dot_rdg (struct graph *);
+
+DEBUG_FUNCTION void
+dot_rdg (struct graph *rdg)
+{
+ /* When debugging, enable the following code. This cannot be used
+ in production compilers because it calls "system". */
+#if 0
+ FILE *file = fopen ("/tmp/rdg.dot", "w");
+ gcc_assert (file != NULL);
+
+ dot_rdg_1 (file, rdg);
+ fclose (file);
+
+ system ("dotty /tmp/rdg.dot &");
+#else
+ dot_rdg_1 (stderr, rdg);
+#endif
+}
+
/* This structure is used for recording the mapping statement index in
the RDG. */
scalar dependence. */
struct graph *
-build_rdg (struct loop *loop)
+build_rdg (struct loop *loop,
+ VEC (loop_p, heap) **loop_nest,
+ VEC (ddr_p, heap) **dependence_relations,
+ VEC (data_reference_p, heap) **datarefs)
{
- int nb_data_refs = 10;
struct graph *rdg = NULL;
- VEC (ddr_p, heap) *dependence_relations;
- VEC (data_reference_p, heap) *datarefs;
- VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, nb_data_refs);
-
- dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
- datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
- compute_data_dependences_for_loop (loop,
- false,
- &datarefs,
- &dependence_relations);
-
- if (!known_dependences_p (dependence_relations))
- {
- free_dependence_relations (dependence_relations);
- free_data_refs (datarefs);
- VEC_free (gimple, heap, stmts);
-
- return rdg;
- }
+ VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10);
- stmts_from_loop (loop, &stmts);
- rdg = build_empty_rdg (VEC_length (gimple, stmts));
+ compute_data_dependences_for_loop (loop, false, loop_nest, datarefs,
+ dependence_relations);
- rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
- eq_stmt_vertex_info, hash_stmt_vertex_del);
- create_rdg_vertices (rdg, stmts);
- create_rdg_edges (rdg, dependence_relations);
+ if (known_dependences_p (*dependence_relations))
+ {
+ stmts_from_loop (loop, &stmts);
+ rdg = build_empty_rdg (VEC_length (gimple, stmts));
+ create_rdg_vertices (rdg, stmts);
+ create_rdg_edges (rdg, *dependence_relations);
+ }
VEC_free (gimple, heap, stmts);
return rdg;
int i;
for (i = 0; i < rdg->n_vertices; i++)
- free (rdg->vertices[i].data);
+ {
+ struct vertex *v = &(rdg->vertices[i]);
+ struct graph_edge *e;
+
+ for (e = v->succ; e; e = e->succ_next)
+ if (e->data)
+ free (e->data);
+
+ if (v->data)
+ free (v->data);
+ }
htab_delete (rdg->indices);
free_graph (rdg);
free (bbs);
}
+/* Returns true when the statement at STMT is of the form "A[i] = 0"
+ that contains a data reference on its LHS with a stride of the same
+ size as its unit type. */
+
+bool
+stmt_with_adjacent_zero_store_dr_p (gimple stmt)
+{
+ tree op0, op1;
+ bool res;
+ struct data_reference *dr;
+
+ if (!stmt
+ || !gimple_vdef (stmt)
+ || !is_gimple_assign (stmt)
+ || !gimple_assign_single_p (stmt)
+ || !(op1 = gimple_assign_rhs1 (stmt))
+ || !(integer_zerop (op1) || real_zerop (op1)))
+ return false;
+
+ dr = XCNEW (struct data_reference);
+ op0 = gimple_assign_lhs (stmt);
+
+ DR_STMT (dr) = stmt;
+ DR_REF (dr) = op0;
+
+ res = dr_analyze_innermost (dr)
+ && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0));
+
+ free_data_ref (dr);
+ return res;
+}
+
/* Initialize STMTS with all the statements of LOOP that contain a
store to memory of the form "A[i] = 0". */
basic_block bb;
gimple_stmt_iterator si;
gimple stmt;
- tree op;
basic_block *bbs = get_loop_body_in_dom_order (loop);
for (i = 0; i < loop->num_nodes; i++)
for (bb = bbs[i], si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
if ((stmt = gsi_stmt (si))
- && gimple_vdef (stmt)
- && is_gimple_assign (stmt)
- && gimple_assign_rhs_code (stmt) == INTEGER_CST
- && (op = gimple_assign_rhs1 (stmt))
- && (integer_zerop (op) || real_zerop (op)))
+ && stmt_with_adjacent_zero_store_dr_p (stmt))
VEC_safe_push (gimple, heap, *stmts, gsi_stmt (si));
free (bbs);
OSDN Git Service
