This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[lno] Speed up the users of data dependence


Hi,

This patch cleans up the use of the data dependence information.

Bootstrapped on i686 and amd64.  Results of the vectorizer testsuite
are the same.

Sebastian

Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.213
diff -d -u -p -r1.1.2.213 ChangeLog.lno
--- ChangeLog.lno	8 Jul 2004 04:49:41 -0000	1.1.2.213
+++ ChangeLog.lno	8 Jul 2004 13:28:41 -0000
@@ -1,3 +1,40 @@
+2004-07-08  Sebastian Pop  <pop@cri.ensmp.fr>
+
+	* Makefile.in (OBJS-common): Remove tree-dg.o.
+	(tree-dg.o): Removed.
+	(GTFILES): Remove tree-dg.h.
+	* gengtype.c (open_base_files): Remove tree-dg.h.
+	* tree-data-ref.c (subscript_dependence_tester): Don't define.
+	(dump_data_dependence_relation): Print data references only
+	when they are not NULL.
+	(analyze_array_top): Removed.
+	(initialize_data_dependence_relation): Is extern now.
+	When the data references are NULL the relation is not known.
+	(compute_affine_dependence): Is extern now.
+	(find_data_references_in_loop): Returns chrec_dont_know when
+	failing to analyze a difficult case.  
+	(compute_data_dependences_for_loop): Terminate earlier when 
+	find_data_references_in_loop fails.
+	* tree-data-ref.h (data_dependence_relation): Update comments.
+	(initialize_data_dependence_relation, compute_affine_dependence): 
+	Declared extern.
+	* tree-dg.c, tree-dg.h: Removed.
+	* tree-flow-inline.h (dg_node_for_stmt): Removed.
+	* tree-flow.h: Don't include tree-dg.h.
+	(stmt_ann_d): Remove dependence_node field.
+	* tree-ssa-loop.c: Include tree-data-ref.h.
+	(tree_vectorize, tree_linear_transform): Don't construct the dg_graph.
+	* tree-vectorizer.c: Remove some declarations of static functions.
+	(vect_analyze_data_ref_dependence): Extra parameter for the vectorized 
+	loop.  Don't rely on the information provided by the data
+	reference structure.  Compute directly the relation between
+	the data references instead of querying this information in
+	the dg_graph.
+	(vect_analyze_data_ref_dependences): Pass to
+	vect_analyze_data_ref_dependence the information about the
+	vectorized loop.
+	* varray.h (varray_data_tag): Remove dependence_node_def.
+
 2004-07-07  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
 
 	* tree-ssa-loop-ivopts.c (cand_value_at): Handle types correctly.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.158.2.36
diff -d -u -p -r1.903.2.158.2.36 Makefile.in
--- Makefile.in	1 Jul 2004 04:24:33 -0000	1.903.2.158.2.36
+++ Makefile.in	8 Jul 2004 13:28:41 -0000
@@ -897,7 +897,7 @@ OBJS-common = \
  tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
  tree-ssa-loop-unswitch.o tree-ssa-loop-niter.o tree-ssa-loop-ch.o	   \
  tree-vectorizer.o tree-ssa-loop-im.o tree-ssa-loop-manip.o		   \
- tree-ssa-loop-ivopts.o tree-ssa-loop-ivcanon.o tree-dg.o loop-invariant.o \
+ tree-ssa-loop-ivopts.o tree-ssa-loop-ivcanon.o loop-invariant.o           \
  alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	  	   \
  cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
  cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o	   \
@@ -1735,10 +1735,6 @@ tree-data-ref.o: tree-data-ref.c $(CONFI
    errors.h $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) diagnostic.h \
    $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h \
    tree-data-ref.h $(SCEV_H) tree-pass.h
-tree-dg.o: tree-dg.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) flags.h \
-   errors.h $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) \
-   $(TIMEVAR_H) cfgloop.h tree-data-ref.h \
-   tree-pass.h tree-dg.h $(TIMEVAR_H) $(TREE_DUMP_H) diagnostic.h $(SCEV_H)
 tree-elim-check.o: tree-elim-check.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    errors.h $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) diagnostic.h \
    $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h $(SCEV_H) \
@@ -2383,7 +2379,7 @@ GTFILES = $(srcdir)/input.h $(srcdir)/co
   $(srcdir)/reg-stack.c $(srcdir)/cfglayout.c $(srcdir)/langhooks.c \
   $(srcdir)/sdbout.c $(srcdir)/stmt.c $(srcdir)/stor-layout.c \
   $(srcdir)/stringpool.c $(srcdir)/tree.c $(srcdir)/varasm.c \
-  $(srcdir)/tree-mudflap.c $(srcdir)/tree-dg.h $(srcdir)/tree-flow.h \
+  $(srcdir)/tree-mudflap.c $(srcdir)/tree-flow.h \
   $(srcdir)/c-objc-common.c $(srcdir)/c-common.c $(srcdir)/c-parse.in \
   $(srcdir)/tree-ssanames.c $(srcdir)/tree-eh.c \
   $(srcdir)/tree-phinodes.c $(srcdir)/tree-cfg.c \
Index: gengtype.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gengtype.c,v
retrieving revision 1.7.4.24.2.8
diff -d -u -p -r1.7.4.24.2.8 gengtype.c
--- gengtype.c	22 Jun 2004 16:03:43 -0000	1.7.4.24.2.8
+++ gengtype.c	8 Jul 2004 13:28:41 -0000
@@ -1109,7 +1109,7 @@ open_base_files (void)
       "basic-block.h", "cselib.h", "insn-addr.h", "optabs.h",
       "libfuncs.h", "debug.h", "ggc.h", "cgraph.h",
       "tree-alias-type.h", "tree-flow.h", "reload.h",
-      "tree-data-ref.h", "cpp-id-data.h", "tree-dg.h",
+      "tree-data-ref.h", "cpp-id-data.h",
       "tree-chrec.h",
       NULL
     };
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-data-ref.c,v
retrieving revision 1.1.2.25
diff -d -u -p -r1.1.2.25 tree-data-ref.c
--- tree-data-ref.c	6 Jul 2004 19:25:09 -0000	1.1.2.25
+++ tree-data-ref.c	8 Jul 2004 13:28:41 -0000
@@ -91,8 +91,6 @@ Software Foundation, 59 Temple Place - S
 #include "tree-pass.h"
 #include "lambda.h"
 
-static void subscript_dependence_tester (struct data_dependence_relation *);
-
 static unsigned int data_ref_id = 0;
 
 
@@ -311,7 +309,10 @@ dump_data_dependence_relation (FILE *out
   dra = DDR_A (ddr);
   drb = DDR_B (ddr);
   
-  fprintf (outf, "(Data Dep (A = %d, B = %d):", DR_ID (dra), DR_ID (drb));  
+  if (dra && drb)
+    fprintf (outf, "(Data Dep (A = %d, B = %d):", DR_ID (dra), DR_ID (drb));
+  else
+    fprintf (outf, "(Data Dep:");
 
   if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
     fprintf (outf, "    (don't know)\n");
@@ -524,35 +525,6 @@ init_data_ref (tree stmt, 
   return res;
 }
 
-
-/* For a data reference REF contained in the statemet STMT, initialize
-   a DATA_REFERENCE structure, and return it.  Set the IS_READ flag to
-   true when REF is in the right hand side of an assignment.  */
-
-static struct data_reference *
-analyze_array_top (tree stmt)
-{
-  struct data_reference *res;
-
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file, "(analyze_array_top \n");
-
-  res = ggc_alloc (sizeof (struct data_reference));
-
-  DR_ID (res) = data_ref_id++;
-  DR_STMT (res) = stmt;
-  DR_REF (res) = NULL_TREE;
-  DR_BASE_NAME (res) = NULL_TREE;
-
-  VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 1, "access_fns");
-  VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), chrec_dont_know);
-
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    fprintf (dump_file, ")\n");
-
-  return res;
-}
-
 
 
 /* When there exists a dependence relation, determine its distance
@@ -587,7 +559,7 @@ compute_distance_vector (struct data_dep
 
 /* Initialize a ddr.  */
 
-static struct data_dependence_relation *
+struct data_dependence_relation *
 initialize_data_dependence_relation (struct data_reference *a, 
 				     struct data_reference *b)
 {
@@ -597,7 +569,8 @@ initialize_data_dependence_relation (str
   DDR_A (res) = a;
   DDR_B (res) = b;
 
-  if (DR_BASE_NAME (a) == NULL_TREE
+  if (a == NULL || b == NULL 
+      || DR_BASE_NAME (a) == NULL_TREE
       || DR_BASE_NAME (b) == NULL_TREE)
     DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
 
@@ -1620,7 +1593,7 @@ access_functions_are_affine_or_constant_
    relation the first time we detect a CHREC_KNOWN element for a given
    subscript.  */
 
-static void
+void
 compute_affine_dependence (struct data_dependence_relation *ddr)
 {
   struct data_reference *dra = DDR_A (ddr);
@@ -1690,14 +1663,15 @@ compute_rw_wr_ww_dependences (varray_typ
 }
 
 /* Search the data references in LOOP, and record the information into
-   DATAREFS.
+   DATAREFS.  Returns chrec_dont_know when failing to analyze a
+   difficult case, returns NULL_TREE otherwise.
    
    FIXME: This is a "dumb" walker over all the trees in the loop body.
    Find another technique that avoids this costly walk.  This is
    acceptable for the moment, since this function is used only for
    debugging purposes.  */
 
-static void 
+static tree 
 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
 {
   basic_block bb;
@@ -1734,10 +1708,11 @@ find_data_references_in_loop (struct loo
 					       true));
 
   	  else
-	    VARRAY_PUSH_GENERIC_PTR (*datarefs, 
-				     analyze_array_top (stmt));
+	    return chrec_dont_know;
 	}
     }
+
+  return NULL_TREE;
 }
 
 
@@ -1757,7 +1732,21 @@ compute_data_dependences_for_loop (unsig
 {
   unsigned int i;
 
-  find_data_references_in_loop (loop, datarefs);
+  /* If one of the data references is not computable, give up without
+     spending time to compute other dependences.  */
+  if (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);
+      VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
+      build_classic_dist_vector (ddr, classic_dist, nb_loops, loop->num);
+      build_classic_dir_vector (ddr, classic_dir, nb_loops, loop->num);
+      return;
+    }
+
   compute_rw_wr_ww_dependences (*datarefs, dependence_relations);
 
   for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++)
Index: tree-data-ref.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-data-ref.h,v
retrieving revision 1.1.2.14
diff -d -u -p -r1.1.2.14 tree-data-ref.h
--- tree-data-ref.h	14 Jun 2004 12:55:47 -0000	1.1.2.14
+++ tree-data-ref.h	8 Jul 2004 13:28:41 -0000
@@ -120,10 +120,10 @@ struct data_dependence_relation GTY(())
        relation between A and B, and the description of this relation
        is given in the SUBSCRIPTS array,
      
-     - when "ARE_DEPENDENT == CHREC_BOT", there is no dependence and
+     - when "ARE_DEPENDENT == chrec_known", there is no dependence and
        SUBSCRIPTS is empty,
      
-     - when "ARE_DEPENDENT == CHREC_TOP", there may be a dependence,
+     - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence,
        but the analyzer cannot be more specific.  */
   tree are_dependent;
   
@@ -144,6 +144,9 @@ struct data_dependence_relation GTY(())
 
 
 
+struct data_dependence_relation *initialize_data_dependence_relation 
+(struct data_reference *, struct data_reference *);
+void compute_affine_dependence (struct data_dependence_relation *);
 extern void analyze_all_data_dependences (struct loops *);
 extern void compute_data_dependences_for_loop (unsigned, struct loop *, 
 					       varray_type *, varray_type *, 
Index: tree-dg.c
===================================================================
RCS file: tree-dg.c
diff -N tree-dg.c
--- tree-dg.c	6 Jul 2004 19:25:09 -0000	1.1.2.13
+++ /dev/null	1 Jan 1970 00:00:00 -0000
@@ -1,588 +0,0 @@
-/* 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-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, loops->parray[0], 
-				     &datarefs, &dependence_relations, 
-				     &classic_dist, &classic_dir);
-  
-  /* Initialize.  */
-  dg_init_graph ();
-
-  /* Using data references, 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_known)
-	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;
-
-  if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
-    return dir_star;
-
-  /* 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 Predecessors */
-      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 (chrec_contains_undetermined (DDR_ARE_DEPENDENT (e->ddr)))
-	    fprintf (file, "don't know\n");
-
-	  if (DDR_ARE_DEPENDENT (e->ddr) != chrec_dont_know)
-	    {
-	      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);
-}
Index: tree-dg.h
===================================================================
RCS file: tree-dg.h
diff -N tree-dg.h
--- tree-dg.h	15 Apr 2004 15:27:51 -0000	1.1.2.4
+++ /dev/null	1 Jan 1970 00:00:00 -0000
@@ -1,87 +0,0 @@
-/* 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.  */
-
-#ifndef GCC_TREE_SSA_DG_H
-#define GCC_TREE_SSA_DG_H
-
-#include "tree-data-ref.h"
-
-struct dependence_edge_def GTY (())
-{
-  /* Dependence relation */
-  struct data_dependence_relation *ddr;
-
-  /* Links through the predessor and successor lists.  */
-  struct dependence_edge_def *pred_next;
-  struct dependence_edge_def *succ_next;
-
-  /* Source and destination.  */
-  struct dependence_node_def *src;
-  struct dependence_node_def *dst;
-
-  /* Auxiliary info.  */
-  /* PTR GTY ((skip (""))) aux; */
-};
-
-typedef struct dependence_edge_def *dependence_edge;
-
-struct dependence_node_def GTY (())
-{
-
-  int node_id;
-
-  /* Statement */
-  tree stmt;
-
-  /* Dependece ddges */
-  dependence_edge pred;
-  dependence_edge succ;
-
-  /* Next and previous nodes in the chain.  */
-  struct dependence_node_def *next;
-  struct dependence_node_def *prev;
-
-};
-
-typedef struct dependence_node_def *dependence_node;
-
-#define DN_STMT(node) (node->stmt)
-#define DN_ID(node) (node->node_id)
-
-/* Create dependency graph.  */
-extern void dg_create_graph (struct loops *);
-
-/* Delete dependency graph.  */
-extern void dg_delete_graph (void);
-
-/* Delete edge from the dependency graph.  */
-void dg_delete_edge (dependence_edge);
-
-/* Debug dependence graph.  */
-extern void debug_dg (int);
-
-/* Find data dependence direction between two statements.  */
-enum data_dependence_direction ddg_direction_between_stmts (tree, tree, int);
-
-/* Find data dependence distance between two statements.  */
-tree ddg_distance_between_stmts (tree, tree, int);
-
-#endif
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 1.1.2.64.2.11
diff -d -u -p -r1.1.2.64.2.11 tree-flow-inline.h
--- tree-flow-inline.h	6 Jul 2004 19:25:09 -0000	1.1.2.64.2.11
+++ tree-flow-inline.h	8 Jul 2004 13:28:41 -0000
@@ -119,14 +119,6 @@ bb_for_stmt (tree t)
   return ann ? ann->bb : NULL;
 }
 
-/* Return associated dependence_node with the statement.  */
-static inline dependence_node
-dg_node_for_stmt (tree t)
-{
-  stmt_ann_t ann = stmt_ann (t);
-  return ann ? ann->dg_node : NULL;
-}
-
 static inline varray_type
 may_aliases (tree var)
 {
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 1.1.4.177.2.36
diff -d -u -p -r1.1.4.177.2.36 tree-flow.h
--- tree-flow.h	1 Jul 2004 04:24:34 -0000	1.1.4.177.2.36
+++ tree-flow.h	8 Jul 2004 13:28:41 -0000
@@ -28,7 +28,6 @@ Boston, MA 02111-1307, USA.  */
 #include "hashtab.h"
 #include "tree-gimple.h"
 #include "tree-ssa-operands.h"
-#include "tree-dg.h"
 
 /* Forward declare structures for the garbage collector GTY markers.  */
 #ifndef GCC_BASIC_BLOCK_H
@@ -246,9 +245,6 @@ struct stmt_ann_d GTY(())
   /* Basic block that contains this statement.  */
   basic_block GTY ((skip (""))) bb;
 
-  /* Node representing this stmt in dependence graph.  */
-  dependence_node GTY ((skip (""))) dg_node;
-
   /* Statement operands.  */
   struct def_optype_d * GTY (()) def_ops;
   struct use_optype_d * GTY (()) use_ops;
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop.c,v
retrieving revision 1.1.2.3.2.25
diff -d -u -p -r1.1.2.3.2.25 tree-ssa-loop.c
--- tree-ssa-loop.c	1 Jul 2004 04:24:34 -0000	1.1.2.3.2.25
+++ tree-ssa-loop.c	8 Jul 2004 13:28:41 -0000
@@ -38,6 +38,7 @@ Software Foundation, 59 Temple Place - S
 #include "flags.h"
 #include "tree-inline.h"
 #include "tree-scalar-evolution.h"
+#include "tree-data-ref.h"
 #include "tree-vectorizer.h"
 
 /* The loop tree currently optimized.  */
@@ -330,16 +331,8 @@ tree_vectorize (void)
   if (!current_loops)
     return;
 
-  timevar_push (TV_DEP_GRAPH);
-  dg_create_graph (current_loops);
-  timevar_pop (TV_DEP_GRAPH);
-		 
   bitmap_clear (vars_to_rename);
   vectorize_loops (current_loops);
-
-  timevar_push (TV_DEP_GRAPH);
-  dg_delete_graph ();
-  timevar_pop (TV_DEP_GRAPH);
 }
 
 static bool
@@ -405,15 +398,7 @@ tree_linear_transform (void)
   if (!current_loops)
     return;
 
-  timevar_push (TV_DEP_GRAPH);
-  dg_create_graph (current_loops);
-  timevar_pop (TV_DEP_GRAPH);
-
   linear_transform_loops (current_loops);
-
-  timevar_push (TV_DEP_GRAPH);
-  dg_delete_graph ();
-  timevar_pop (TV_DEP_GRAPH);
 }
 
 static bool
Index: tree-vectorizer.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-vectorizer.c,v
retrieving revision 1.1.2.48
diff -d -u -p -r1.1.2.48 tree-vectorizer.c
--- tree-vectorizer.c	6 Jul 2004 19:25:09 -0000	1.1.2.48
+++ tree-vectorizer.c	8 Jul 2004 13:28:41 -0000
@@ -158,7 +158,6 @@ static loop_vec_info vect_analyze_loop_f
 static bool vect_analyze_data_refs (loop_vec_info);
 static bool vect_mark_stmts_to_be_vectorized (loop_vec_info);
 static bool vect_analyze_scalar_cycles (loop_vec_info);
-static bool vect_analyze_data_ref_dependences (loop_vec_info);
 static bool vect_analyze_data_ref_accesses (loop_vec_info);
 static bool vect_analyze_data_refs_alignment (loop_vec_info);
 static void vect_compute_data_refs_alignment (loop_vec_info);
@@ -189,8 +188,6 @@ static tree vect_get_loop_niters (struct
 static void vect_compute_data_ref_alignment 
   (struct data_reference *, loop_vec_info);
 static bool vect_analyze_data_ref_access (struct data_reference *);
-static bool vect_analyze_data_ref_dependence
-  (struct data_reference *, struct data_reference *);
 static int vect_get_array_first_index (tree);
 static bool vect_force_dr_alignment_p (struct data_reference *);
 static bool vect_analyze_loop_with_symbolic_num_of_iters 
@@ -2819,7 +2816,8 @@ vect_analyze_scalar_cycles (loop_vec_inf
 
 static bool
 vect_analyze_data_ref_dependence (struct data_reference *dra,
-				  struct data_reference *drb)
+				  struct data_reference *drb, 
+				  struct loop *loop)
 {
   tree refa = DR_REF (dra);
   tree refb = DR_REF (drb);
@@ -2827,7 +2825,6 @@ vect_analyze_data_ref_dependence (struct
   tree ptrb = TREE_OPERAND (refb, 0);
   tree ta = TREE_TYPE (ptra);
   tree tb = TREE_TYPE (ptrb);
-  tree stmt = DR_STMT (dra);
 
   /* Both refs are arrays:  */
 
@@ -2836,20 +2833,18 @@ vect_analyze_data_ref_dependence (struct
     {
       if (!array_base_name_differ_p (dra, drb))
         {
-	  int level = (loop_containing_stmt (stmt))->level;
-	  int loop_nest = level - 1;
-
-          /* FORNOW: use most trivial and conservative test.  */
-          enum data_dependence_direction ddd = ddg_direction_between_stmts 
-		(DR_STMT (dra), DR_STMT (drb), loop_nest);
-
-          if (ddd == dir_independent)
-            return false;
+	  /* FORNOW: use most trivial and conservative test.  */
+	  struct data_dependence_relation *ddr = 
+	    initialize_data_dependence_relation (dra, drb);
+	  compute_affine_dependence (ddr);
 
+	  if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
+	    return false;
+	  
           if (dump_file && (dump_flags & TDF_DETAILS))
             fprintf (dump_file,
                 "vect_analyze_data_ref_dependence: same base\n");
-	  vect_debug_stats (loop_containing_stmt (stmt), 
+	  vect_debug_stats (loop, 
 		"not vectorized: can't prove independence of array-refs.");
           return true;
         }
@@ -2877,7 +2872,7 @@ vect_analyze_data_ref_dependence (struct
 	    {
               if (dump_file && (dump_flags & TDF_DETAILS))
 	        fprintf (dump_file,"non restricted pointers. may alias.\n"); 
-	      vect_debug_stats (loop_containing_stmt (stmt), 
+	      vect_debug_stats (loop, 
 		"not vectorized: can't prove independence of pointer-refs.");
 	      return true;
             }
@@ -2922,6 +2917,7 @@ vect_analyze_data_ref_dependences (loop_
   unsigned int i, j;
   varray_type loop_write_refs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
   varray_type loop_read_refs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
+  struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 
   /* examine store-store (output) dependences */
 
@@ -2936,7 +2932,7 @@ vect_analyze_data_ref_dependences (loop_
 	    VARRAY_GENERIC_PTR (loop_write_refs, i);
 	  struct data_reference *drb =
 	    VARRAY_GENERIC_PTR (loop_write_refs, j);
-	  if (vect_analyze_data_ref_dependence (dra, drb))
+	  if (vect_analyze_data_ref_dependence (dra, drb, loop))
 	    return false;
 	}
     }
@@ -2953,7 +2949,7 @@ vect_analyze_data_ref_dependences (loop_
 	  struct data_reference *dra = VARRAY_GENERIC_PTR (loop_read_refs, i);
 	  struct data_reference *drb =
 	    VARRAY_GENERIC_PTR (loop_write_refs, j);
-	  if (vect_analyze_data_ref_dependence (dra, drb))
+	  if (vect_analyze_data_ref_dependence (dra, drb, loop))
 	    return false;
 	}
     }
Index: varray.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/varray.h,v
retrieving revision 1.28.2.8.2.4
diff -d -u -p -r1.28.2.8.2.4 varray.h
--- varray.h	25 Apr 2004 20:33:45 -0000	1.28.2.8.2.4
+++ varray.h	8 Jul 2004 13:28:41 -0000
@@ -134,8 +134,6 @@ typedef union varray_data_tag GTY (()) {
 				tag ("VARRAY_DATA_TE")))	te[1];
   struct edge_def        *GTY ((length ("%0.num_elements"),
 	                        tag ("VARRAY_DATA_EDGE")))	e[1];
-  struct dependence_node_def *GTY ((length ("%0.num_elements"),
-				tag ("VARRAY_DATA_DG")))	dg[1];
   tree                   *GTY ((length ("%0.num_elements"), skip (""),
 	                        tag ("VARRAY_DATA_TREE_PTR")))	tp[1];
 } varray_data;


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]