This moves the RDG implementation private to its only user,
loop distribution, and away from the unrelated data-reference/dependence
code.
The patch also moves the loops bitmap passed around into the
partition struct.
Bootstrapped and tested on x86_64-unknown-linux-gnu, applied.
Richard.
2013-09-11 Richard Biener <rguent...@suse.de>
* tree-data-ref.c (dump_rdg_vertex, debug_rdg_vertex,
dump_rdg_component, debug_rdg_component, dump_rdg, debug_rdg,
dot_rdg_1, dot_rdg, rdg_vertex_for_stmt, create_rdg_edge_for_ddr,
create_rdg_edges_for_scalar, create_rdg_edges, create_rdg_vertices,
stmts_from_loop, known_dependences_p, build_empty_rdg,
build_rdg, free_rdg, rdg_defs_used_in_other_loops_p): Move ...
* tree-loop-distribution.c: ... here.
* tree-data-ref.h (struct rdg_vertex, RDGV_STMT, RDGV_DATAREFS,
RDGV_HAS_MEM_WRITE, RDGV_HAS_MEM_READS, RDG_STMT, RDG_DATAREFS,
RDG_MEM_WRITE_STMT, RDG_MEM_READS_STMT, enum rdg_dep_type,
struct rdg_edge, RDGE_TYPE, RDGE_LEVEL, RDGE_RELATION): Move ...
* tree-loop-distribution.c: ... here.
* tree-loop-distribution.c: Include gimple-pretty-print.h.
(struct partition_s): Add loops member.
(partition_alloc, partition_free, rdg_flag_uses, rdg_flag_vertex,
rdg_flag_vertex_and_dependent, rdg_flag_loop_exits,
build_rdg_partition_for_component, rdg_build_partitions): Adjust.
Index: gcc/tree-data-ref.c
===================================================================
*** gcc/tree-data-ref.c (revision 202431)
--- gcc/tree-data-ref.c (working copy)
*************** free_data_refs (vec<data_reference_p> da
*** 4798,5268 ****
free_data_ref (dr);
datarefs.release ();
}
-
-
-
- /* Dump vertex I in RDG to FILE. */
-
- static void
- dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
- {
- struct vertex *v = &(rdg->vertices[i]);
- struct graph_edge *e;
-
- fprintf (file, "(vertex %d: (%s%s) (in:", i,
- RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
- RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
-
- if (v->pred)
- for (e = v->pred; e; e = e->pred_next)
- fprintf (file, " %d", e->src);
-
- fprintf (file, ") (out:");
-
- if (v->succ)
- for (e = v->succ; e; e = e->succ_next)
- fprintf (file, " %d", e->dest);
-
- fprintf (file, ")\n");
- print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
- fprintf (file, ")\n");
- }
-
- /* Call dump_rdg_vertex on stderr. */
-
- DEBUG_FUNCTION void
- debug_rdg_vertex (struct graph *rdg, int i)
- {
- dump_rdg_vertex (stderr, rdg, i);
- }
-
- /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
- dumped vertices to that bitmap. */
-
- static void
- dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
- {
- int i;
-
- fprintf (file, "(%d\n", c);
-
- for (i = 0; i < rdg->n_vertices; i++)
- if (rdg->vertices[i].component == c)
- {
- if (dumped)
- bitmap_set_bit (dumped, i);
-
- dump_rdg_vertex (file, rdg, i);
- }
-
- fprintf (file, ")\n");
- }
-
- /* Call dump_rdg_vertex on stderr. */
-
- DEBUG_FUNCTION void
- debug_rdg_component (struct graph *rdg, int c)
- {
- dump_rdg_component (stderr, rdg, c, NULL);
- }
-
- /* Dump the reduced dependence graph RDG to FILE. */
-
- void
- dump_rdg (FILE *file, struct graph *rdg)
- {
- int i;
- bitmap dumped = BITMAP_ALLOC (NULL);
-
- fprintf (file, "(rdg\n");
-
- for (i = 0; i < rdg->n_vertices; i++)
- if (!bitmap_bit_p (dumped, i))
- dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
-
- fprintf (file, ")\n");
- BITMAP_FREE (dumped);
- }
-
- /* Call dump_rdg on stderr. */
-
- DEBUG_FUNCTION void
- debug_rdg (struct graph *rdg)
- {
- 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
- }
-
- /* Returns the index of STMT in RDG. */
-
- int
- rdg_vertex_for_stmt (struct graph *rdg ATTRIBUTE_UNUSED, gimple stmt)
- {
- int index = gimple_uid (stmt);
- gcc_checking_assert (index == -1 || RDG_STMT (rdg, index) == stmt);
- return index;
- }
-
- /* Creates an edge in RDG for each distance vector from DDR. The
- order that we keep track of in the RDG is the order in which
- statements have to be executed. */
-
- static void
- create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
- {
- struct graph_edge *e;
- int va, vb;
- data_reference_p dra = DDR_A (ddr);
- data_reference_p drb = DDR_B (ddr);
- unsigned level = ddr_dependence_level (ddr);
-
- /* For non scalar dependences, when the dependence is REVERSED,
- statement B has to be executed before statement A. */
- if (level > 0
- && !DDR_REVERSED_P (ddr))
- {
- data_reference_p tmp = dra;
- dra = drb;
- drb = tmp;
- }
-
- va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
- vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
-
- if (va < 0 || vb < 0)
- return;
-
- e = add_edge (rdg, va, vb);
- e->data = XNEW (struct rdg_edge);
-
- RDGE_LEVEL (e) = level;
- RDGE_RELATION (e) = ddr;
-
- /* Determines the type of the data dependence. */
- if (DR_IS_READ (dra) && DR_IS_READ (drb))
- RDGE_TYPE (e) = input_dd;
- else if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
- RDGE_TYPE (e) = output_dd;
- else if (DR_IS_WRITE (dra) && DR_IS_READ (drb))
- RDGE_TYPE (e) = flow_dd;
- else if (DR_IS_READ (dra) && DR_IS_WRITE (drb))
- RDGE_TYPE (e) = anti_dd;
- }
-
- /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
- the index of DEF in RDG. */
-
- static void
- create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
- {
- use_operand_p imm_use_p;
- imm_use_iterator iterator;
-
- FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
- {
- struct graph_edge *e;
- int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
-
- if (use < 0)
- continue;
-
- e = add_edge (rdg, idef, use);
- e->data = XNEW (struct rdg_edge);
- RDGE_TYPE (e) = flow_dd;
- RDGE_RELATION (e) = NULL;
- }
- }
-
- /* Creates the edges of the reduced dependence graph RDG. */
-
- static void
- create_rdg_edges (struct graph *rdg, vec<ddr_p> ddrs)
- {
- int i;
- struct data_dependence_relation *ddr;
- def_operand_p def_p;
- ssa_op_iter iter;
-
- FOR_EACH_VEC_ELT (ddrs, i, ddr)
- if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- create_rdg_edge_for_ddr (rdg, ddr);
-
- for (i = 0; i < rdg->n_vertices; i++)
- FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
- iter, SSA_OP_DEF)
- create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
- }
-
- /* Build the vertices of the reduced dependence graph RDG. Return false
- if that failed. */
-
- static bool
- create_rdg_vertices (struct graph *rdg, vec<gimple> stmts, loop_p loop,
- vec<data_reference_p> *datarefs)
- {
- int i;
- gimple stmt;
-
- FOR_EACH_VEC_ELT (stmts, i, stmt)
- {
- struct vertex *v = &(rdg->vertices[i]);
-
- /* Record statement to vertex mapping. */
- gimple_set_uid (stmt, i);
-
- v->data = XNEW (struct rdg_vertex);
- RDGV_STMT (v) = stmt;
- RDGV_DATAREFS (v).create (0);
- RDGV_HAS_MEM_WRITE (v) = false;
- RDGV_HAS_MEM_READS (v) = false;
- if (gimple_code (stmt) == GIMPLE_PHI)
- continue;
-
- unsigned drp = datarefs->length ();
- if (!find_data_references_in_stmt (loop, stmt, datarefs))
- return false;
- for (unsigned j = drp; j < datarefs->length (); ++j)
- {
- data_reference_p dr = (*datarefs)[j];
- if (DR_IS_READ (dr))
- RDGV_HAS_MEM_READS (v) = true;
- else
- RDGV_HAS_MEM_WRITE (v) = true;
- RDGV_DATAREFS (v).safe_push (dr);
- }
- }
- return true;
- }
-
- /* Initialize STMTS with all the statements of LOOP. When
- INCLUDE_PHIS is true, include also the PHI nodes. The order in
- which we discover statements is important as
- generate_loops_for_partition is using the same traversal for
- identifying statements. */
-
- static void
- stmts_from_loop (struct loop *loop, vec<gimple> *stmts)
- {
- unsigned int i;
- basic_block *bbs = get_loop_body_in_dom_order (loop);
-
- for (i = 0; i < loop->num_nodes; i++)
- {
- basic_block bb = bbs[i];
- gimple_stmt_iterator bsi;
- gimple stmt;
-
- for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
- stmts->safe_push (gsi_stmt (bsi));
-
- for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
- {
- stmt = gsi_stmt (bsi);
- if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
- stmts->safe_push (stmt);
- }
- }
-
- free (bbs);
- }
-
- /* Returns true when all the dependences are computable. */
-
- static bool
- known_dependences_p (vec<ddr_p> dependence_relations)
- {
- ddr_p ddr;
- unsigned int i;
-
- FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
- if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
- return false;
-
- return true;
- }
-
- /* Build the Reduced Dependence Graph (RDG) with one vertex per
- statement of the loop nest, and one edge per data dependence or
- scalar dependence. */
-
- struct graph *
- build_empty_rdg (int n_stmts)
- {
- struct graph *rdg = new_graph (n_stmts);
- return rdg;
- }
-
- /* Build the Reduced Dependence Graph (RDG) with one vertex per
- statement of the loop nest, and one edge per data dependence or
- scalar dependence. */
-
- struct graph *
- build_rdg (struct loop *loop)
- {
- struct graph *rdg;
- vec<loop_p> loop_nest;
- vec<gimple> stmts;
- vec<data_reference_p> datarefs;
- vec<ddr_p> dependence_relations;
-
- loop_nest.create (3);
- if (!find_loop_nest (loop, &loop_nest))
- {
- loop_nest.release ();
- return NULL;
- }
-
- stmts.create (10);
- stmts_from_loop (loop, &stmts);
- rdg = build_empty_rdg (stmts.length ());
- datarefs.create (10);
- if (!create_rdg_vertices (rdg, stmts, loop, &datarefs))
- {
- stmts.release ();
- free_rdg (rdg);
- return NULL;
- }
- stmts.release ();
- dependence_relations.create (100);
- if (!compute_all_dependences (datarefs, &dependence_relations, loop_nest,
- false)
- || !known_dependences_p (dependence_relations))
- {
- loop_nest.release ();
- datarefs.release ();
- dependence_relations.release ();
- free_rdg (rdg);
- return NULL;
- }
- loop_nest.release ();
- create_rdg_edges (rdg, dependence_relations);
- dependence_relations.release ();
-
- return rdg;
- }
-
- /* Free the reduced dependence graph RDG. */
-
- void
- free_rdg (struct graph *rdg)
- {
- int i;
-
- for (i = 0; i < rdg->n_vertices; i++)
- {
- struct vertex *v = &(rdg->vertices[i]);
- struct graph_edge *e;
-
- for (e = v->succ; e; e = e->succ_next)
- {
- free_dependence_relation (RDGE_RELATION (e));
- free (e->data);
- }
-
- if (v->data)
- {
- gimple_set_uid (RDGV_STMT (v), -1);
- free_data_refs (RDGV_DATAREFS (v));
- free (v->data);
- }
- }
-
- free_graph (rdg);
- }
-
- /* Determines whether the statement from vertex V of the RDG has a
- definition used outside the loop that contains this statement. */
-
- bool
- rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
- {
- gimple stmt = RDG_STMT (rdg, v);
- struct loop *loop = loop_containing_stmt (stmt);
- use_operand_p imm_use_p;
- imm_use_iterator iterator;
- ssa_op_iter it;
- def_operand_p def_p;
-
- if (!loop)
- return true;
-
- FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
- {
- FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
- {
- if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
- return true;
- }
- }
-
- return false;
- }
--- 4798,4800 ----
Index: gcc/tree-data-ref.h
===================================================================
*** gcc/tree-data-ref.h (revision 202431)
--- gcc/tree-data-ref.h (working copy)
*************** ddr_dependence_level (ddr_p ddr)
*** 515,593 ****
return level;
}
-
-
- /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
- typedef struct rdg_vertex
- {
- /* The statement represented by this vertex. */
- gimple stmt;
-
- /* Vector of data-references in this statement. */
- vec<data_reference_p> datarefs;
-
- /* True when the statement contains a write to memory. */
- bool has_mem_write;
-
- /* True when the statement contains a read from memory. */
- bool has_mem_reads;
- } *rdg_vertex_p;
-
- #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
- #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
- #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *)
((V)->data))->has_mem_write
- #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *)
((V)->data))->has_mem_reads
- #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
- #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
- #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
- #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
-
- void debug_rdg_vertex (struct graph *, int);
- void debug_rdg_component (struct graph *, int);
- void dump_rdg (FILE *, struct graph *);
- void debug_rdg (struct graph *);
- int rdg_vertex_for_stmt (struct graph *, gimple);
-
- /* Data dependence type. */
-
- enum rdg_dep_type
- {
- /* Read After Write (RAW). */
- flow_dd = 'f',
-
- /* Write After Read (WAR). */
- anti_dd = 'a',
-
- /* Write After Write (WAW). */
- output_dd = 'o',
-
- /* Read After Read (RAR). */
- input_dd = 'i'
- };
-
- /* Dependence information attached to an edge of the RDG. */
-
- typedef struct rdg_edge
- {
- /* Type of the dependence. */
- enum rdg_dep_type type;
-
- /* Levels of the dependence: the depth of the loops that carry the
- dependence. */
- unsigned level;
-
- /* Dependence relation between data dependences, NULL when one of
- the vertices is a scalar. */
- ddr_p relation;
- } *rdg_edge_p;
-
- #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
- #define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level
- #define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation
-
- struct graph *build_rdg (struct loop *);
- void free_rdg (struct graph *);
-
/* Return the index of the variable VAR in the LOOP_NEST array. */
static inline int
--- 515,520 ----
*************** index_in_loop_nest (int var, vec<loop_p>
*** 604,611 ****
return var_index;
}
- bool rdg_defs_used_in_other_loops_p (struct graph *, int);
-
/* Returns true when the data reference DR the form "A[i] = ..."
with a stride equal to its unit type size. */
--- 531,536 ----
*************** adjacent_dr_p (struct data_reference *dr
*** 626,644 ****
TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
}
- /* In tree-data-ref.c */
void split_constant_offset (tree , tree *, tree *);
- /* Strongly connected components of the reduced data dependence graph. */
-
- typedef struct rdg_component
- {
- int num;
- vec<int> vertices;
- } *rdgc;
-
-
-
/* Compute the greatest common divisor of a VECTOR of SIZE numbers. */
static inline int
--- 551,558 ----
Index: gcc/tree-loop-distribution.c
===================================================================
*** gcc/tree-loop-distribution.c (revision 202431)
--- gcc/tree-loop-distribution.c (working copy)
*************** along with GCC; see the file COPYING3.
*** 50,55 ****
--- 50,594 ----
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
+ #include "gimple-pretty-print.h"
+
+
+ /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
+ typedef struct rdg_vertex
+ {
+ /* The statement represented by this vertex. */
+ gimple stmt;
+
+ /* Vector of data-references in this statement. */
+ vec<data_reference_p> datarefs;
+
+ /* True when the statement contains a write to memory. */
+ bool has_mem_write;
+
+ /* True when the statement contains a read from memory. */
+ bool has_mem_reads;
+ } *rdg_vertex_p;
+
+ #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
+ #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
+ #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *)
((V)->data))->has_mem_write
+ #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *)
((V)->data))->has_mem_reads
+ #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
+ #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
+ #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
+ #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
+
+ /* Data dependence type. */
+
+ enum rdg_dep_type
+ {
+ /* Read After Write (RAW). */
+ flow_dd = 'f',
+
+ /* Write After Read (WAR). */
+ anti_dd = 'a',
+
+ /* Write After Write (WAW). */
+ output_dd = 'o',
+
+ /* Read After Read (RAR). */
+ input_dd = 'i'
+ };
+
+ /* Dependence information attached to an edge of the RDG. */
+
+ typedef struct rdg_edge
+ {
+ /* Type of the dependence. */
+ enum rdg_dep_type type;
+
+ /* Levels of the dependence: the depth of the loops that carry the
+ dependence. */
+ unsigned level;
+
+ /* Dependence relation between data dependences, NULL when one of
+ the vertices is a scalar. */
+ ddr_p relation;
+ } *rdg_edge_p;
+
+ #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
+ #define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level
+ #define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation
+
+ /* Strongly connected components of the reduced data dependence graph. */
+
+ typedef struct rdg_component
+ {
+ int num;
+ vec<int> vertices;
+ } *rdgc;
+
+ /* Dump vertex I in RDG to FILE. */
+
+ static void
+ dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
+ {
+ struct vertex *v = &(rdg->vertices[i]);
+ struct graph_edge *e;
+
+ fprintf (file, "(vertex %d: (%s%s) (in:", i,
+ RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
+ RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
+
+ if (v->pred)
+ for (e = v->pred; e; e = e->pred_next)
+ fprintf (file, " %d", e->src);
+
+ fprintf (file, ") (out:");
+
+ if (v->succ)
+ for (e = v->succ; e; e = e->succ_next)
+ fprintf (file, " %d", e->dest);
+
+ fprintf (file, ")\n");
+ print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
+ fprintf (file, ")\n");
+ }
+
+ /* Call dump_rdg_vertex on stderr. */
+
+ DEBUG_FUNCTION void
+ debug_rdg_vertex (struct graph *rdg, int i)
+ {
+ dump_rdg_vertex (stderr, rdg, i);
+ }
+
+ /* Dump component C of RDG to FILE. If DUMPED is non-null, set the
+ dumped vertices to that bitmap. */
+
+ static void
+ dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
+ {
+ int i;
+
+ fprintf (file, "(%d\n", c);
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ if (rdg->vertices[i].component == c)
+ {
+ if (dumped)
+ bitmap_set_bit (dumped, i);
+
+ dump_rdg_vertex (file, rdg, i);
+ }
+
+ fprintf (file, ")\n");
+ }
+
+ /* Call dump_rdg_vertex on stderr. */
+
+ DEBUG_FUNCTION void
+ debug_rdg_component (struct graph *rdg, int c)
+ {
+ dump_rdg_component (stderr, rdg, c, NULL);
+ }
+
+ /* Dump the reduced dependence graph RDG to FILE. */
+
+ static void
+ dump_rdg (FILE *file, struct graph *rdg)
+ {
+ int i;
+ bitmap dumped = BITMAP_ALLOC (NULL);
+
+ fprintf (file, "(rdg\n");
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ if (!bitmap_bit_p (dumped, i))
+ dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
+
+ fprintf (file, ")\n");
+ BITMAP_FREE (dumped);
+ }
+
+ /* Call dump_rdg on stderr. */
+
+ DEBUG_FUNCTION void
+ debug_rdg (struct graph *rdg)
+ {
+ 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. */
+
+ 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
+ }
+
+ /* Returns the index of STMT in RDG. */
+
+ static int
+ rdg_vertex_for_stmt (struct graph *rdg ATTRIBUTE_UNUSED, gimple stmt)
+ {
+ int index = gimple_uid (stmt);
+ gcc_checking_assert (index == -1 || RDG_STMT (rdg, index) == stmt);
+ return index;
+ }
+
+ /* Creates an edge in RDG for each distance vector from DDR. The
+ order that we keep track of in the RDG is the order in which
+ statements have to be executed. */
+
+ static void
+ create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
+ {
+ struct graph_edge *e;
+ int va, vb;
+ data_reference_p dra = DDR_A (ddr);
+ data_reference_p drb = DDR_B (ddr);
+ unsigned level = ddr_dependence_level (ddr);
+
+ /* For non scalar dependences, when the dependence is REVERSED,
+ statement B has to be executed before statement A. */
+ if (level > 0
+ && !DDR_REVERSED_P (ddr))
+ {
+ data_reference_p tmp = dra;
+ dra = drb;
+ drb = tmp;
+ }
+
+ va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
+ vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
+
+ if (va < 0 || vb < 0)
+ return;
+
+ e = add_edge (rdg, va, vb);
+ e->data = XNEW (struct rdg_edge);
+
+ RDGE_LEVEL (e) = level;
+ RDGE_RELATION (e) = ddr;
+
+ /* Determines the type of the data dependence. */
+ if (DR_IS_READ (dra) && DR_IS_READ (drb))
+ RDGE_TYPE (e) = input_dd;
+ else if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
+ RDGE_TYPE (e) = output_dd;
+ else if (DR_IS_WRITE (dra) && DR_IS_READ (drb))
+ RDGE_TYPE (e) = flow_dd;
+ else if (DR_IS_READ (dra) && DR_IS_WRITE (drb))
+ RDGE_TYPE (e) = anti_dd;
+ }
+
+ /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
+ the index of DEF in RDG. */
+
+ static void
+ create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
+ {
+ use_operand_p imm_use_p;
+ imm_use_iterator iterator;
+
+ FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
+ {
+ struct graph_edge *e;
+ int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
+
+ if (use < 0)
+ continue;
+
+ e = add_edge (rdg, idef, use);
+ e->data = XNEW (struct rdg_edge);
+ RDGE_TYPE (e) = flow_dd;
+ RDGE_RELATION (e) = NULL;
+ }
+ }
+
+ /* Creates the edges of the reduced dependence graph RDG. */
+
+ static void
+ create_rdg_edges (struct graph *rdg, vec<ddr_p> ddrs)
+ {
+ int i;
+ struct data_dependence_relation *ddr;
+ def_operand_p def_p;
+ ssa_op_iter iter;
+
+ FOR_EACH_VEC_ELT (ddrs, i, ddr)
+ if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+ create_rdg_edge_for_ddr (rdg, ddr);
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
+ iter, SSA_OP_DEF)
+ create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
+ }
+
+ /* Build the vertices of the reduced dependence graph RDG. Return false
+ if that failed. */
+
+ static bool
+ create_rdg_vertices (struct graph *rdg, vec<gimple> stmts, loop_p loop,
+ vec<data_reference_p> *datarefs)
+ {
+ int i;
+ gimple stmt;
+
+ FOR_EACH_VEC_ELT (stmts, i, stmt)
+ {
+ struct vertex *v = &(rdg->vertices[i]);
+
+ /* Record statement to vertex mapping. */
+ gimple_set_uid (stmt, i);
+
+ v->data = XNEW (struct rdg_vertex);
+ RDGV_STMT (v) = stmt;
+ RDGV_DATAREFS (v).create (0);
+ RDGV_HAS_MEM_WRITE (v) = false;
+ RDGV_HAS_MEM_READS (v) = false;
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ continue;
+
+ unsigned drp = datarefs->length ();
+ if (!find_data_references_in_stmt (loop, stmt, datarefs))
+ return false;
+ for (unsigned j = drp; j < datarefs->length (); ++j)
+ {
+ data_reference_p dr = (*datarefs)[j];
+ if (DR_IS_READ (dr))
+ RDGV_HAS_MEM_READS (v) = true;
+ else
+ RDGV_HAS_MEM_WRITE (v) = true;
+ RDGV_DATAREFS (v).safe_push (dr);
+ }
+ }
+ return true;
+ }
+
+ /* Initialize STMTS with all the statements of LOOP. When
+ INCLUDE_PHIS is true, include also the PHI nodes. The order in
+ which we discover statements is important as
+ generate_loops_for_partition is using the same traversal for
+ identifying statements. */
+
+ static void
+ stmts_from_loop (struct loop *loop, vec<gimple> *stmts)
+ {
+ unsigned int i;
+ basic_block *bbs = get_loop_body_in_dom_order (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = bbs[i];
+ gimple_stmt_iterator bsi;
+ gimple stmt;
+
+ for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ stmts->safe_push (gsi_stmt (bsi));
+
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ {
+ stmt = gsi_stmt (bsi);
+ if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
+ stmts->safe_push (stmt);
+ }
+ }
+
+ free (bbs);
+ }
+
+ /* Returns true when all the dependences are computable. */
+
+ static bool
+ known_dependences_p (vec<ddr_p> dependence_relations)
+ {
+ ddr_p ddr;
+ unsigned int i;
+
+ FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+ return false;
+
+ return true;
+ }
+
+ /* Build the Reduced Dependence Graph (RDG) with one vertex per
+ statement of the loop nest, and one edge per data dependence or
+ scalar dependence. */
+
+ struct graph *
+ build_empty_rdg (int n_stmts)
+ {
+ struct graph *rdg = new_graph (n_stmts);
+ return rdg;
+ }
+
+ /* Free the reduced dependence graph RDG. */
+
+ static void
+ free_rdg (struct graph *rdg)
+ {
+ int i;
+
+ for (i = 0; i < rdg->n_vertices; i++)
+ {
+ struct vertex *v = &(rdg->vertices[i]);
+ struct graph_edge *e;
+
+ for (e = v->succ; e; e = e->succ_next)
+ {
+ free_dependence_relation (RDGE_RELATION (e));
+ free (e->data);
+ }
+
+ if (v->data)
+ {
+ gimple_set_uid (RDGV_STMT (v), -1);
+ free_data_refs (RDGV_DATAREFS (v));
+ free (v->data);
+ }
+ }
+
+ free_graph (rdg);
+ }
+
+ /* Build the Reduced Dependence Graph (RDG) with one vertex per
+ statement of the loop nest, and one edge per data dependence or
+ scalar dependence. */
+
+ static struct graph *
+ build_rdg (struct loop *loop)
+ {
+ struct graph *rdg;
+ vec<loop_p> loop_nest;
+ vec<gimple> stmts;
+ vec<data_reference_p> datarefs;
+ vec<ddr_p> dependence_relations;
+
+ loop_nest.create (3);
+ if (!find_loop_nest (loop, &loop_nest))
+ {
+ loop_nest.release ();
+ return NULL;
+ }
+
+ stmts.create (10);
+ stmts_from_loop (loop, &stmts);
+ rdg = build_empty_rdg (stmts.length ());
+ datarefs.create (10);
+ if (!create_rdg_vertices (rdg, stmts, loop, &datarefs))
+ {
+ stmts.release ();
+ free_rdg (rdg);
+ return NULL;
+ }
+ stmts.release ();
+ dependence_relations.create (100);
+ if (!compute_all_dependences (datarefs, &dependence_relations, loop_nest,
+ false)
+ || !known_dependences_p (dependence_relations))
+ {
+ loop_nest.release ();
+ datarefs.release ();
+ dependence_relations.release ();
+ free_rdg (rdg);
+ return NULL;
+ }
+ loop_nest.release ();
+ create_rdg_edges (rdg, dependence_relations);
+ dependence_relations.release ();
+
+ return rdg;
+ }
+
+ /* Determines whether the statement from vertex V of the RDG has a
+ definition used outside the loop that contains this statement. */
+
+ static bool
+ rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
+ {
+ gimple stmt = RDG_STMT (rdg, v);
+ struct loop *loop = loop_containing_stmt (stmt);
+ use_operand_p imm_use_p;
+ imm_use_iterator iterator;
+ ssa_op_iter it;
+ def_operand_p def_p;
+
+ if (!loop)
+ return true;
+
+ FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
+ {
+ FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
+ {
+ if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+
enum partition_kind {
PKIND_NORMAL, PKIND_REDUCTION, PKIND_MEMSET, PKIND_MEMCPY
*************** enum partition_kind {
*** 58,63 ****
--- 597,603 ----
typedef struct partition_s
{
bitmap stmts;
+ bitmap loops;
bool has_writes;
enum partition_kind kind;
/* data-references a kind != PKIND_NORMAL partition is about. */
*************** typedef struct partition_s
*** 69,78 ****
/* Allocate and initialize a partition from BITMAP. */
static partition_t
! partition_alloc (bitmap stmts)
{
partition_t partition = XCNEW (struct partition_s);
partition->stmts = stmts ? stmts : BITMAP_ALLOC (NULL);
partition->has_writes = false;
partition->kind = PKIND_NORMAL;
return partition;
--- 609,619 ----
/* Allocate and initialize a partition from BITMAP. */
static partition_t
! partition_alloc (bitmap stmts, bitmap loops)
{
partition_t partition = XCNEW (struct partition_s);
partition->stmts = stmts ? stmts : BITMAP_ALLOC (NULL);
+ partition->loops = loops ? loops : BITMAP_ALLOC (NULL);
partition->has_writes = false;
partition->kind = PKIND_NORMAL;
return partition;
*************** static void
*** 84,89 ****
--- 625,631 ----
partition_free (partition_t partition)
{
BITMAP_FREE (partition->stmts);
+ BITMAP_FREE (partition->loops);
free (partition);
}
*************** has_upstream_mem_writes (int u)
*** 626,638 ****
}
static void rdg_flag_vertex_and_dependent (struct graph *, int, partition_t,
! bitmap, bitmap);
/* Flag the uses of U stopping following the information from
upstream_mem_writes. */
static void
! rdg_flag_uses (struct graph *rdg, int u, partition_t partition, bitmap loops,
bitmap processed)
{
struct vertex *x = &(rdg->vertices[u]);
--- 1168,1180 ----
}
static void rdg_flag_vertex_and_dependent (struct graph *, int, partition_t,
! bitmap);
/* Flag the uses of U stopping following the information from
upstream_mem_writes. */
static void
! rdg_flag_uses (struct graph *rdg, int u, partition_t partition,
bitmap processed)
{
struct vertex *x = &(rdg->vertices[u]);
*************** rdg_flag_uses (struct graph *rdg, int u,
*** 647,654 ****
int v = anti_dep->dest;
if (!already_processed_vertex_p (processed, v))
! rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
! processed);
}
if (is_gimple_assign (stmt) && has_upstream_mem_writes (u))
--- 1189,1195 ----
int v = anti_dep->dest;
if (!already_processed_vertex_p (processed, v))
! rdg_flag_vertex_and_dependent (rdg, v, partition, processed);
}
if (is_gimple_assign (stmt) && has_upstream_mem_writes (u))
*************** rdg_flag_uses (struct graph *rdg, int u,
*** 667,674 ****
int v = rdg_vertex_for_stmt (rdg, USE_STMT (use_p));
if (!already_processed_vertex_p (processed, v))
! rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
! processed);
}
}
}
--- 1208,1214 ----
int v = rdg_vertex_for_stmt (rdg, USE_STMT (use_p));
if (!already_processed_vertex_p (processed, v))
! rdg_flag_vertex_and_dependent (rdg, v, partition, processed);
}
}
}
*************** rdg_flag_uses (struct graph *rdg, int u,
*** 678,684 ****
in LOOPS. */
static void
! rdg_flag_vertex (struct graph *rdg, int v, partition_t partition, bitmap
loops)
{
struct loop *loop;
--- 1218,1224 ----
in LOOPS. */
static void
! rdg_flag_vertex (struct graph *rdg, int v, partition_t partition)
{
struct loop *loop;
*************** rdg_flag_vertex (struct graph *rdg, int
*** 686,692 ****
return;
loop = loop_containing_stmt (RDG_STMT (rdg, v));
! bitmap_set_bit (loops, loop->num);
if (rdg_cannot_recompute_vertex_p (rdg, v))
{
--- 1226,1232 ----
return;
loop = loop_containing_stmt (RDG_STMT (rdg, v));
! bitmap_set_bit (partition->loops, loop->num);
if (rdg_cannot_recompute_vertex_p (rdg, v))
{
*************** rdg_flag_vertex (struct graph *rdg, int
*** 700,706 ****
static void
rdg_flag_vertex_and_dependent (struct graph *rdg, int v, partition_t
partition,
! bitmap loops, bitmap processed)
{
unsigned i;
vec<int> nodes;
--- 1240,1246 ----
static void
rdg_flag_vertex_and_dependent (struct graph *rdg, int v, partition_t
partition,
! bitmap processed)
{
unsigned i;
vec<int> nodes;
*************** rdg_flag_vertex_and_dependent (struct gr
*** 708,720 ****
int x;
bitmap_set_bit (processed, v);
! rdg_flag_uses (rdg, v, partition, loops, processed);
graphds_dfs (rdg, &v, 1, &nodes, false, remaining_stmts);
! rdg_flag_vertex (rdg, v, partition, loops);
FOR_EACH_VEC_ELT (nodes, i, x)
if (!already_processed_vertex_p (processed, x))
! rdg_flag_vertex_and_dependent (rdg, x, partition, loops, processed);
nodes.release ();
}
--- 1248,1260 ----
int x;
bitmap_set_bit (processed, v);
! rdg_flag_uses (rdg, v, partition, processed);
graphds_dfs (rdg, &v, 1, &nodes, false, remaining_stmts);
! rdg_flag_vertex (rdg, v, partition);
FOR_EACH_VEC_ELT (nodes, i, x)
if (!already_processed_vertex_p (processed, x))
! rdg_flag_vertex_and_dependent (rdg, x, partition, processed);
nodes.release ();
}
*************** collect_condition_stmts (struct loop *lo
*** 745,751 ****
RDG. */
static void
! rdg_flag_loop_exits (struct graph *rdg, bitmap loops, partition_t partition,
bitmap processed)
{
unsigned i;
--- 1285,1291 ----
RDG. */
static void
! rdg_flag_loop_exits (struct graph *rdg, partition_t partition,
bitmap processed)
{
unsigned i;
*************** rdg_flag_loop_exits (struct graph *rdg,
*** 753,775 ****
vec<gimple> conds;
conds.create (3);
! EXECUTE_IF_SET_IN_BITMAP (loops, 0, i, bi)
collect_condition_stmts (get_loop (cfun, i), &conds);
while (!conds.is_empty ())
{
gimple cond = conds.pop ();
int v = rdg_vertex_for_stmt (rdg, cond);
- bitmap new_loops = BITMAP_ALLOC (NULL);
-
if (!already_processed_vertex_p (processed, v))
! rdg_flag_vertex_and_dependent (rdg, v, partition, new_loops, processed);
!
! EXECUTE_IF_SET_IN_BITMAP (new_loops, 0, i, bi)
! if (bitmap_set_bit (loops, i))
! collect_condition_stmts (get_loop (cfun, i), &conds);
!
! BITMAP_FREE (new_loops);
}
conds.release ();
--- 1293,1315 ----
vec<gimple> conds;
conds.create (3);
! EXECUTE_IF_SET_IN_BITMAP (partition->loops, 0, i, bi)
collect_condition_stmts (get_loop (cfun, i), &conds);
while (!conds.is_empty ())
{
gimple cond = conds.pop ();
int v = rdg_vertex_for_stmt (rdg, cond);
if (!already_processed_vertex_p (processed, v))
! {
! bitmap saved_loops = BITMAP_ALLOC (NULL);
! bitmap_copy (saved_loops, partition->loops);
! rdg_flag_vertex_and_dependent (rdg, v, partition, processed);
! EXECUTE_IF_AND_COMPL_IN_BITMAP (partition->loops, saved_loops,
! 0, i, bi)
! collect_condition_stmts (get_loop (cfun, i), &conds);
! BITMAP_FREE (saved_loops);
! }
}
conds.release ();
*************** static partition_t
*** 783,800 ****
build_rdg_partition_for_component (struct graph *rdg, rdgc c)
{
int i, v;
! partition_t partition = partition_alloc (NULL);
! bitmap loops = BITMAP_ALLOC (NULL);
bitmap processed = BITMAP_ALLOC (NULL);
FOR_EACH_VEC_ELT (c->vertices, i, v)
if (!already_processed_vertex_p (processed, v))
! rdg_flag_vertex_and_dependent (rdg, v, partition, loops, processed);
! rdg_flag_loop_exits (rdg, loops, partition, processed);
BITMAP_FREE (processed);
- BITMAP_FREE (loops);
return partition;
}
--- 1323,1338 ----
build_rdg_partition_for_component (struct graph *rdg, rdgc c)
{
int i, v;
! partition_t partition = partition_alloc (NULL, NULL);
bitmap processed = BITMAP_ALLOC (NULL);
FOR_EACH_VEC_ELT (c->vertices, i, v)
if (!already_processed_vertex_p (processed, v))
! rdg_flag_vertex_and_dependent (rdg, v, partition, processed);
! rdg_flag_loop_exits (rdg, partition, processed);
BITMAP_FREE (processed);
return partition;
}
*************** rdg_build_partitions (struct graph *rdg,
*** 1080,1086 ****
{
int i;
rdgc x;
! partition_t partition = partition_alloc (NULL);
FOR_EACH_VEC_ELT (components, i, x)
{
--- 1618,1624 ----
{
int i;
rdgc x;
! partition_t partition = partition_alloc (NULL, NULL);
FOR_EACH_VEC_ELT (components, i, x)
{
*************** rdg_build_partitions (struct graph *rdg,
*** 1105,1111 ****
}
partitions->safe_push (partition);
! partition = partition_alloc (NULL);
}
}
--- 1643,1649 ----
}
partitions->safe_push (partition);
! partition = partition_alloc (NULL, NULL);
}
}
