On 25.01.2012 18:21, Richard Guenther wrote:
2012/1/25 Andrey Belevantsev<a...@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 <a...@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.
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,
