aboutsummaryrefslogtreecommitdiff
path: root/gcc/tree-dg.c
diff options
context:
space:
mode:
Diffstat (limited to 'gcc/tree-dg.c')
-rw-r--r--gcc/tree-dg.c583
1 files changed, 583 insertions, 0 deletions
diff --git a/gcc/tree-dg.c b/gcc/tree-dg.c
new file mode 100644
index 00000000000..fee51bd5bf5
--- /dev/null
+++ b/gcc/tree-dg.c
@@ -0,0 +1,583 @@
+/* Dependence Graph
+ Copyright (C) 2004 Free Software Foundation, Inc.
+ Contributed by Devang Patel <dpatel@apple.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+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. */
+
+/* This pass build data dependence graph based on the information
+ collected by scalar evolution analyzer.
+
+ A short description of data dependence graph:
+
+ Each node in the graph represents one GIMPLE statement.
+
+ Nodes are connected using dependence edge that describes data
+ dependence relation between two nodes. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "errors.h"
+#include "ggc.h"
+#include "tree.h"
+#include "flags.h"
+#include "timevar.h"
+#include "varray.h"
+#include "rtl.h"
+#include "basic-block.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "cfgloop.h"
+#include "tree-fold-const.h"
+#include "tree-chrec.h"
+#include "tree-data-ref.h"
+#include "tree-scalar-evolution.h"
+#include "tree-pass.h"
+#include "tree-dg.h"
+
+/* local function prototypes */
+static void dg_init_graph (void);
+static void set_dg_node_for_stmt (tree, dependence_node);
+static dependence_node dg_get_node_for_stmt (tree, bool);
+static dependence_node alloc_dependence_node (void);
+static dependence_edge alloc_dependence_edge (void);
+static dependence_node dg_create_node (tree);
+static dependence_edge dg_find_edge (dependence_node, dependence_node, bool);
+static void dump_dg (FILE *, int);
+static void dg_delete_edges (void);
+static void dg_delete_node (dependence_node);
+static struct data_dependence_relation * find_ddr_between_stmts (tree, tree);
+
+/* Initial dependence graph capacity. */
+static int dependence_graph_size = 25;
+
+/* The dependence graph. */
+static GTY (()) varray_type dependence_graph;
+static GTY (()) varray_type datarefs;
+static GTY (()) varray_type dependence_relations;
+static GTY (()) varray_type classic_dist;
+static GTY (()) varray_type classic_dir;
+
+/* Total dependence node count. */
+static int n_dependence_node = 0;
+
+#define DEPENDENCE_GRAPH(N) (VARRAY_DG (dependence_graph, (N)))
+
+/* Initialize data dependence graph. */
+static
+void dg_init_graph (void)
+{
+ VARRAY_DG_INIT (dependence_graph, dependence_graph_size, "dependence_graph");
+}
+
+/* Create dependency graph. */
+void dg_create_graph (struct loops *loops)
+{
+ unsigned int i;
+
+ VARRAY_GENERIC_PTR_INIT (classic_dist, 10, "classic_dist");
+ VARRAY_GENERIC_PTR_INIT (classic_dir, 10, "classic_dir");
+ VARRAY_GENERIC_PTR_INIT (datarefs, 10, "datarefs");
+ VARRAY_GENERIC_PTR_INIT (dependence_relations, 10 * 10,
+ "dependence_relations");
+
+ /* Analyze data references and dependence relations using scev. */
+
+ compute_data_dependences_for_loop (loops->num, loop_from_num (loops, 0),
+ &datarefs, &dependence_relations,
+ &classic_dist, &classic_dir);
+
+ /* Initialize. */
+ dg_init_graph ();
+
+ /* Using data refernces, populate graph. */
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+ {
+ dependence_edge connecting_edge;
+
+ struct data_reference *first_dr, *second_dr;
+ struct data_dependence_relation *ddr;
+ tree first_stmt, second_stmt;
+
+ ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
+
+ /* If there is no dependence than do not create an edge. */
+ if (DDR_ARE_DEPENDENT (ddr) == chrec_bot)
+ continue;
+
+ /* Get dependence references */
+ first_dr = DDR_A (ddr);
+ second_dr = DDR_B (ddr);
+
+ /* Get statements */
+ first_stmt = DR_STMT (first_dr);
+ second_stmt = DR_STMT(second_dr);
+
+ /* Find connecting edge. */
+ connecting_edge = dg_find_edge (dg_get_node_for_stmt (first_stmt, true),
+ dg_get_node_for_stmt (second_stmt, true),
+ true);
+
+ /* Record data dependence relation. */
+ connecting_edge->ddr = ddr;
+ }
+
+ if (dump_file)
+ {
+ dump_dg (dump_file, dump_flags);
+ }
+}
+
+/* Delete data dependence graph. */
+void
+dg_delete_graph (void)
+{
+ if (dependence_graph)
+ {
+
+ /* Delete all edges. */
+ dg_delete_edges ();
+
+ /* Reset node count. */
+ n_dependence_node = 0;
+
+ /* Clear data reference and dependence relations. */
+ if (datarefs)
+ VARRAY_CLEAR (datarefs);
+
+ if (dependence_relations)
+ VARRAY_CLEAR (dependence_relations);
+
+ if (classic_dir)
+ VARRAY_CLEAR (classic_dir);
+
+ if (classic_dist)
+ VARRAY_CLEAR (classic_dist);
+
+ /* Clear dependence graph itself. */
+ VARRAY_CLEAR (dependence_graph);
+
+ datarefs = NULL;
+ dependence_relations = NULL;
+ dependence_graph = NULL;
+ }
+
+}
+
+
+/*---------------------------------------------------------------------------
+ Dependence node
+---------------------------------------------------------------------------*/
+
+/* Allocate memory for dependence_node. */
+
+static dependence_node
+alloc_dependence_node (void)
+{
+ dependence_node dg_node;
+ dg_node = ggc_alloc_cleared (sizeof (*dg_node));
+ return dg_node;
+}
+
+/* Create new dependency_node. */
+
+static dependence_node
+dg_create_node (tree stmt)
+{
+ dependence_node dg_node;
+ if (!stmt)
+ return NULL;
+
+ /* Allocate */
+ dg_node = alloc_dependence_node ();
+
+ /* Assign id. */
+ dg_node->node_id = n_dependence_node;
+
+ VARRAY_PUSH_DG (dependence_graph, dg_node);
+
+ /* Increment count. */
+ n_dependence_node++;
+
+ /* Connect dg_node and stmt with each other. */
+ dg_node->stmt = stmt;
+ set_dg_node_for_stmt (stmt, dg_node);
+
+ return dg_node;
+}
+
+/* Delete dependence node. */
+static void
+dg_delete_node (dependence_node node)
+{
+ stmt_ann_t ann = stmt_ann (node->stmt);
+
+#ifdef ENABLE_CHECKING
+ /* If node has live edges, then it is a problem. */
+ if (node->succ || node->pred)
+ abort ();
+#endif
+
+ /* Clear dg_node entry in stmt_ann */
+ if (ann)
+ ann->dg_node = NULL;
+
+ /* Delete node. */
+ node = NULL;
+}
+
+/*---------------------------------------------------------------------------
+ Dependence edge
+---------------------------------------------------------------------------*/
+
+/* Allocate memory for dependence_edge. */
+
+static dependence_edge
+alloc_dependence_edge (void)
+{
+ dependence_edge dg_edge;
+ dg_edge = ggc_alloc_cleared (sizeof (*dg_edge));
+ return dg_edge;
+}
+
+/* Find edge in the dependence graph that connects two nodes.
+ If required, create new edge. */
+
+static dependence_edge
+dg_find_edge (dependence_node n1, dependence_node n2, bool create)
+{
+ tree stmt1, stmt2;
+ dependence_edge e;
+
+ if (!n1 || !n2)
+ abort ();
+
+ stmt1 = DN_STMT (n1);
+ stmt2 = DN_STMT (n2);
+
+ if (!stmt1 || !stmt2)
+ abort ();
+
+ /* Browse succ edges and see if dst of any edge is stmt2.
+ If there is one then return that edge. */
+ for (e = n1->succ; e; e = e->succ_next)
+ {
+ if (DN_STMT (e->dst) == stmt2)
+ return e;
+ }
+
+ /* Browse pred edges and see if src of any edge is stmt2.
+ If there is one then return that edge. */
+ for (e = n1->pred; e; e = e->pred_next)
+ {
+ if (DN_STMT (e->src) == stmt2)
+ return e;
+ }
+
+ if (!create)
+ return NULL;
+
+ /* OK, time to create new edge to connect these two nodes. */
+ e = alloc_dependence_edge ();
+
+ /* Set source and destination nodes. */
+ e->src = n1;
+ e->dst = n2;
+
+ /* Set succ and pred */
+ if (n1->succ)
+ e->succ_next = n1->succ;
+ n1->succ = e;
+
+ if (n2->pred)
+ e->pred_next = n2->pred;
+ n2->pred = e;
+
+ /* Return newly created edge. */
+ return e;
+}
+
+/* Delete edge 'e' from the graph. After deleting edge 'e'
+ if source or destination node does not have any more edges
+ associated then delete nodes also. */
+void
+dg_delete_edge (dependence_edge e)
+{
+ dependence_edge current_edge,prev_edge;
+ dependence_node src, dst;
+
+ src = e->src;
+ dst = e->dst;
+
+ /* Remove edge from the list of source successors. */
+ prev_edge = NULL;
+ for (current_edge = src->succ;
+ current_edge;
+ current_edge = current_edge->succ_next)
+ {
+ if (current_edge == e)
+ {
+ /* Found edge 'e' in the list. Remove it from the link list. */
+ if (prev_edge)
+ prev_edge->succ_next = current_edge->succ_next;
+ else
+ src->succ = current_edge->succ_next;
+ }
+ else
+ /* If this is not edge 'e' then make it prev_edge for next
+ iteration. */
+ prev_edge = current_edge;
+ }
+
+ /* If source is not associated with any edge then delete it. */
+ if (!src->succ && !src->pred)
+ dg_delete_node (src);
+
+ /* Remove edge from the list of destination predecessors. */
+ prev_edge = NULL;
+ for (current_edge = dst->pred;
+ current_edge;
+ current_edge = current_edge->pred_next)
+ {
+ if (current_edge == e)
+ {
+ /* Found edge 'e' in the list. Remove it from the link list. */
+ if (prev_edge)
+ prev_edge->pred_next = current_edge->pred_next;
+ else
+ dst->pred = current_edge->pred_next;
+ }
+ else
+ /* If this is not edge 'e' then make it prev_edge for next
+ iteration. */
+ prev_edge = current_edge;
+ }
+
+ /* If source is not associated with any edge then delete it. */
+ if (!dst->succ && !dst->pred)
+ dg_delete_node (dst);
+
+
+ /* Now, actually delete this edge. */
+ e = NULL;
+}
+
+/* Delete all edges in the dependence graph. */
+static void
+dg_delete_edges (void)
+{
+ unsigned int i;
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_graph); i++)
+ {
+ dependence_edge e;
+ dependence_node dg_node = DEPENDENCE_GRAPH (i);
+
+ if (!dg_node)
+ continue;
+
+ /* One by one delete all edges. */
+ for (e = dg_node->succ; e; e = e->succ_next)
+ dg_delete_edge (e);
+ }
+
+}
+
+/*---------------------------------------------------------------------------
+ stmt_ann manipulation for dg_node
+---------------------------------------------------------------------------*/
+
+/* Find dependence_node for the given input tree. If there is not one,
+ create new one. */
+
+static
+dependence_node dg_get_node_for_stmt (tree t, bool create)
+{
+ dependence_node dg_node = dg_node_for_stmt (t);
+
+ /* If there is none, create one. */
+ if (!dg_node && create)
+ dg_node = dg_create_node (t);
+
+ return dg_node;
+}
+
+/* Set the dg_node for the input tree. */
+static void
+set_dg_node_for_stmt (tree t, dependence_node dg_node)
+{
+ stmt_ann_t ann;
+
+ if (!t)
+ abort ();
+
+ ann = get_stmt_ann (t);
+ if (!ann)
+ abort ();
+
+ ann->dg_node = dg_node;
+}
+
+/*---------------------------------------------------------------------------
+ Dependence Info Access
+---------------------------------------------------------------------------*/
+
+/* Find data dependence relation between two statements. If there is no
+ relation between two statements then return NULL. */
+
+static struct data_dependence_relation *
+find_ddr_between_stmts (tree stmt1, tree stmt2)
+{
+ dependence_edge e = NULL;
+ dependence_node n1 = NULL;
+ dependence_node n2 = NULL;
+
+
+#ifdef ENABLE_CHECKING
+ if (!stmt1 || !stmt2)
+ abort ();
+#endif
+
+ /* First find nodes for the statements. */
+ n1 = dg_node_for_stmt (stmt1);
+ n2 = dg_node_for_stmt (stmt2);
+
+ /* If associated dependence node does not exist then this
+ two statements are independent. */
+ if (!n1 || !n2)
+ return NULL;
+
+ /* Find edge between these two statements. */
+ e = dg_find_edge (n1, n2, false /* Do not create new edge */);
+
+ /* Absence of edge indicates that this two statements are independent. */
+ if (!e)
+ return NULL;
+
+ return e->ddr;
+
+}
+
+/* Find data dependence direction between two statements. */
+
+enum data_dependence_direction
+ddg_direction_between_stmts (tree stmt1, tree stmt2, int loop_num)
+{
+ struct subscript *sub = NULL;
+ struct data_dependence_relation *ddr = find_ddr_between_stmts (stmt1, stmt2);
+
+ /* If there is no relation then statements are independent. */
+ if (!ddr)
+ return dir_independent;
+
+ /* Get subscript info. */
+ sub = DDR_SUBSCRIPT (ddr, loop_num);
+ if (!sub)
+ abort ();
+
+ return SUB_DIRECTION (sub);
+}
+
+/* Find data dependence distance between two statements. */
+
+tree
+ddg_distance_between_stmts (tree stmt1, tree stmt2, int loop_num)
+{
+ struct subscript *sub = NULL;
+ struct data_dependence_relation *ddr = find_ddr_between_stmts (stmt1, stmt2);
+
+ /* If there is no relation then statements are independent. */
+ if (!ddr)
+ return NULL_TREE;
+
+ /* Get subscript info. */
+ sub = DDR_SUBSCRIPT (ddr, loop_num);
+ if (!sub)
+ abort ();
+
+ return SUB_DISTANCE (sub);
+}
+
+/*---------------------------------------------------------------------------
+ Printing and debugging
+---------------------------------------------------------------------------*/
+
+/* Print dependency graph in the dump file. */
+static void
+dump_dg (FILE *file, int flags ATTRIBUTE_UNUSED)
+{
+ unsigned int i, j;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_graph); i++)
+ {
+ dependence_edge e;
+ dependence_node dg_node = DEPENDENCE_GRAPH (i);
+
+ if (!dg_node)
+ abort ();
+
+ fprintf (file, "# Dependence Node %d\n", dg_node->node_id);
+
+ /* Print Predecssors */
+ fprintf (file, "# Pred :");
+ for (e = dg_node->pred; e; e = e->pred_next)
+ if (e->dst == dg_node)
+ fprintf (file, "%d ", DN_ID(e->src));
+ fprintf (file, "\n");
+
+ /* Print Successors */
+ fprintf (file, "# Succ :");
+ for (e = dg_node->succ; e; e = e->succ_next)
+ if (e->src == dg_node)
+ fprintf (file, "%d ", DN_ID(e->dst));
+ fprintf (file, "\n");
+
+ fprintf (file, "# Statement :");
+ print_generic_stmt (file, DN_STMT (dg_node), 0);
+
+ fprintf (file, "# From\tTo\tDirection Vector\n");
+ for (e = dg_node->succ; e; e = e->succ_next)
+ {
+
+ fprintf (file," %d\t", DN_ID(e->src));
+ fprintf (file,"%d\t", DN_ID(e->dst));
+
+ if (DDR_ARE_DEPENDENT (e->ddr) == chrec_top)
+ fprintf (file, "don't know\n");
+
+ for (j = 0; j < DDR_NUM_SUBSCRIPTS (e->ddr); j++)
+ {
+ struct subscript *sub = DDR_SUBSCRIPT (e->ddr, j);
+
+ dump_data_dependence_direction (file, SUB_DIRECTION (sub));
+ fprintf (file, " ");
+ }
+ fprintf (file,"\n");
+ }
+
+ /* Add one blank line at the end of this node. */
+ fprintf (file, "\n");
+ }
+}
+
+void
+debug_dg (int flags)
+{
+ dump_dg (stderr, flags);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-17 21:07:20 +0000