diff mbox

Fix PR 51389

Message ID 4F225D2B.9060404@ispras.ru
State New
Headers show

Commit Message

Andrey Belevantsev Jan. 27, 2012, 8:15 a.m. UTC 
On 25.01.2012 18:21, Richard Guenther wrote:
> 2012/1/25 Andrey Belevantsev<abel@ispras.ru>:
...
>> Sure, I've just had the impression that the datarefs vector is no use
>> without the dependencies themselves.  The possibility of making
>> find_data_references_in_loop static also kind of hints in this direction.
>> Anyways, I don't have any problem with fixing compute_all_dependences
>> instead.
>
> I'd prefer that.

The below tests fine and passes the test case.  compute_all_dependences now 
returns bool and has the hunk from compute_data_dependences_for_loop for 
creating a single dont-know datadep.  The only caller that needs to be 
fixed is compute_data_dependences_for_bb, others look fine.

Tree prefetching has its own knob for the same goal, 
PREFETCH_MAX_MEM_REFS_PER_LOOP, which is 200.  Do we want to remove it, to 
change it to the new parameter (might be too big), or to leave it as is?

(Interesting enough, with data deps fixed the most time on the test case is 
taken by RTL PRE, 27%.)

Andrey


2012-01-27  Andrey Belevantsev  <abel@ispras.ru>

	PR middle-end/51389
	* Makefile.in (tree-data-ref.o): Depend on $(PARAMS_H).
	* tree-data-ref.h (find_data_references_in_loop): Remove declaration.
	* tree-data-ref.c (find_data_references_in_loop): Make static.
	(compute_all_dependences): Change return type to bool.  Bail out
	for too many datarefs in a loop.  Move the hunk resetting the data
	dependences vector from ...
	(compute_data_dependences_for_loop): ... here.  Account for
	compute_all_dependences returning false.
	(compute_data_dependences_for_bb): Likewise.
	
	* params.def (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS): New param.
	* doc/invoke.texi (loop-max-datarefs-for-datadeps): Document it.

Comments

Richard Biener Jan. 27, 2012, 9:19 a.m. UTC | #1 
2012/1/27 Andrey Belevantsev <abel@ispras.ru>:
> On 25.01.2012 18:21, Richard Guenther wrote:
>>
>> 2012/1/25 Andrey Belevantsev<abel@ispras.ru>:
>
> ...
>
>>> Sure, I've just had the impression that the datarefs vector is no use
>>> without the dependencies themselves.  The possibility of making
>>> find_data_references_in_loop static also kind of hints in this direction.
>>> Anyways, I don't have any problem with fixing compute_all_dependences
>>> instead.
>>
>>
>> I'd prefer that.
>
>
> The below tests fine and passes the test case.  compute_all_dependences now
> returns bool and has the hunk from compute_data_dependences_for_loop for
> creating a single dont-know datadep.  The only caller that needs to be fixed
> is compute_data_dependences_for_bb, others look fine.
>
> Tree prefetching has its own knob for the same goal,
> PREFETCH_MAX_MEM_REFS_PER_LOOP, which is 200.  Do we want to remove it, to
> change it to the new parameter (might be too big), or to leave it as is?

Just keep it for now as is.

Btw, did you check all callers to compute_all_dependences check its
return value?  At least the array-prefetch and phiopt ones don't AFAICS.

Ok for trunk.

Thanks,
Richard.

> (Interesting enough, with data deps fixed the most time on the test case is
> taken by RTL PRE, 27%.)
>
> Andrey
>
>
> 2012-01-27  Andrey Belevantsev  <abel@ispras.ru>
>
>
>        PR middle-end/51389
>        * Makefile.in (tree-data-ref.o): Depend on $(PARAMS_H).
>        * tree-data-ref.h (find_data_references_in_loop): Remove declaration.
>        * tree-data-ref.c (find_data_references_in_loop): Make static.
>        (compute_all_dependences): Change return type to bool.  Bail out
>        for too many datarefs in a loop.  Move the hunk resetting the data
>        dependences vector from ...
>        (compute_data_dependences_for_loop): ... here.  Account for
>        compute_all_dependences returning false.
>        (compute_data_dependences_for_bb): Likewise.
>
>        * params.def (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS): New param.
>        * doc/invoke.texi (loop-max-datarefs-for-datadeps): Document it.
Andrey Belevantsev Jan. 27, 2012, 9:25 a.m. UTC | #2 
On 27.01.2012 13:19, Richard Guenther wrote:
> 2012/1/27 Andrey Belevantsev<abel@ispras.ru>:
>> On 25.01.2012 18:21, Richard Guenther wrote:
>>>
>>> 2012/1/25 Andrey Belevantsev<abel@ispras.ru>:
>>
>> ...
>>
>>>> Sure, I've just had the impression that the datarefs vector is no use
>>>> without the dependencies themselves.  The possibility of making
>>>> find_data_references_in_loop static also kind of hints in this direction.
>>>> Anyways, I don't have any problem with fixing compute_all_dependences
>>>> instead.
>>>
>>>
>>> I'd prefer that.
>>
>>
>> The below tests fine and passes the test case.  compute_all_dependences now
>> returns bool and has the hunk from compute_data_dependences_for_loop for
>> creating a single dont-know datadep.  The only caller that needs to be fixed
>> is compute_data_dependences_for_bb, others look fine.
>>
>> Tree prefetching has its own knob for the same goal,
>> PREFETCH_MAX_MEM_REFS_PER_LOOP, which is 200.  Do we want to remove it, to
>> change it to the new parameter (might be too big), or to leave it as is?
>
> Just keep it for now as is.
>
> Btw, did you check all callers to compute_all_dependences check its
> return value?  At least the array-prefetch and phiopt ones don't AFAICS.

These two don't but the following loops handle the situations of 
chrec_dont_know deps and bail out in this case, so I decided that should be 
fine.  AFAICS, too.

Andrey

>
> Ok for trunk.
>
> Thanks,
> Richard.
>
diff mbox

Patch

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index f450d3e..43295aa 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -2598,7 +2598,7 @@  tree-scalar-evolution.o : tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \
    $(TREE_PASS_H) $(PARAMS_H) gt-tree-scalar-evolution.h
 tree-data-ref.o : tree-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    gimple-pretty-print.h $(TREE_FLOW_H) $(CFGLOOP_H) $(TREE_DATA_REF_H) \
-   $(TREE_PASS_H) langhooks.h tree-affine.h
+   $(TREE_PASS_H) langhooks.h tree-affine.h $(PARAMS_H)
 sese.o : sese.c sese.h $(CONFIG_H) $(SYSTEM_H) coretypes.h tree-pretty-print.h \
    $(TREE_FLOW_H) $(CFGLOOP_H) $(TREE_DATA_REF_H) tree-pass.h value-prof.h
 graphite.o : graphite.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(DIAGNOSTIC_CORE_H) \
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index e3d3789..8a916ef 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -9115,6 +9115,13 @@  with more basic blocks than this parameter won't have loop invariant
 motion optimization performed on them.  The default value of the
 parameter is 1000 for -O1 and 10000 for -O2 and above.
 
+@item loop-max-datarefs-for-datadeps
+Building data dapendencies is expensive for very large loops.  This
+parameter limits the number of data references in loops that are
+considered for data dependence analysis.  These large loops will not
+be handled then by the optimizations using loop data dependencies.
+The default value is 1000.
+
 @item max-vartrack-size
 Sets a maximum number of hash table slots to use during variable
 tracking dataflow analysis of any function.  If this limit is exceeded
diff --git a/gcc/params.def b/gcc/params.def
index 239b684..d7cdd7b 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -820,6 +820,12 @@  DEFPARAM (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION,
 	  "maximum number of basic blocks per function to be analyzed by Graphite",
 	  100, 0, 0)
 
+/* Avoid data dependence analysis on very large loops.  */
+DEFPARAM (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS,
+	  "loop-max-datarefs-for-datadeps",
+	  "Maximum number of datarefs in loop for building loop data dependencies",
+	  1000, 0, 0)
+
 /* Avoid doing loop invariant motion on very large loops.  */
 
 DEFPARAM (PARAM_LOOP_INVARIANT_MAX_BBS_IN_LOOP,
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 09929c7..b8dfa31 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -85,6 +85,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "tree-pass.h"
 #include "langhooks.h"
 #include "tree-affine.h"
+#include "params.h"
 
 static struct datadep_stats
 {
@@ -4134,9 +4135,10 @@  compute_affine_dependence (struct data_dependence_relation *ddr,
 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
    the data references in DATAREFS, in the LOOP_NEST.  When
    COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
-   relations.  */
+   relations.  Return true when successful, i.e. data references number
+   is small enough to be handled.  */
 
-void
+bool
 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
 			 VEC (ddr_p, heap) **dependence_relations,
 			 VEC (loop_p, heap) *loop_nest,
@@ -4146,6 +4148,18 @@  compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
   struct data_reference *a, *b;
   unsigned int i, j;
 
+  if ((int) VEC_length (data_reference_p, datarefs)
+      > PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
+    {
+      struct data_dependence_relation *ddr;
+
+      /* Insert a single relation into dependence_relations:
+	 chrec_dont_know.  */
+      ddr = initialize_data_dependence_relation (NULL, NULL, loop_nest);
+      VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
+      return false;
+    }
+
   FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
     for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
       if (DR_IS_WRITE (a) || DR_IS_WRITE (b) || compute_self_and_rr)
@@ -4164,6 +4178,8 @@  compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
         if (loop_nest)
    	  compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
       }
+
+  return true;
 }
 
 /* Stores the locations of memory references in STMT to REFERENCES.  Returns
@@ -4338,7 +4354,7 @@  find_data_references_in_bb (struct loop *loop, basic_block bb,
    TODO: This function should be made smarter so that it can handle address
    arithmetic as if they were array accesses, etc.  */
 
-tree
+static tree
 find_data_references_in_loop (struct loop *loop,
 			      VEC (data_reference_p, heap) **datarefs)
 {
@@ -4427,19 +4443,10 @@  compute_data_dependences_for_loop (struct loop *loop,
      dependences.  */
   if (!loop
       || !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, *loop_nest);
-      VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
-      res = false;
-    }
-  else
-    compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
-			     compute_self_and_read_read_dependences);
+      || find_data_references_in_loop (loop, datarefs) == chrec_dont_know
+      || !compute_all_dependences (*datarefs, dependence_relations, *loop_nest,
+				   compute_self_and_read_read_dependences))
+    res = false;
 
   if (dump_file && (dump_flags & TDF_STATS))
     {
@@ -4507,9 +4514,8 @@  compute_data_dependences_for_bb (basic_block bb,
   if (find_data_references_in_bb (NULL, bb, datarefs) == chrec_dont_know)
     return false;
 
-  compute_all_dependences (*datarefs, dependence_relations, NULL,
-                           compute_self_and_read_read_dependences);
-  return true;
+  return compute_all_dependences (*datarefs, dependence_relations, NULL,
+				  compute_self_and_read_read_dependences);
 }
 
 /* Entry point (for testing only).  Analyze all the data references
diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
index 0f12962..df639ca 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -394,8 +394,6 @@  extern bool compute_data_dependences_for_loop (struct loop *, bool,
 extern bool compute_data_dependences_for_bb (basic_block, bool,
                                              VEC (data_reference_p, heap) **,
                                              VEC (ddr_p, heap) **);
-extern tree find_data_references_in_loop (struct loop *,
-                                          VEC (data_reference_p, heap) **);
 extern void print_direction_vector (FILE *, lambda_vector, int);
 extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int);
 extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int);
@@ -426,7 +424,7 @@  extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
 extern struct data_dependence_relation *initialize_data_dependence_relation
      (struct data_reference *, struct data_reference *, VEC (loop_p, heap) *); 
 extern void compute_self_dependence (struct data_dependence_relation *);
-extern void compute_all_dependences (VEC (data_reference_p, heap) *,
+extern bool compute_all_dependences (VEC (data_reference_p, heap) *,
 				     VEC (ddr_p, heap) **, VEC (loop_p, heap) *,
 				     bool);
 extern tree find_data_references_in_bb (struct loop *, basic_block,