This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Fix PR37375 [graphite] Parameter detection and scev only take a surrounding loop as border
- From: "Sebastian Pop" <sebpop at gmail dot com>
- To: "GCC Patches" <gcc-patches at gcc dot gnu dot org>
- Date: Tue, 9 Sep 2008 13:21:03 -0500
- Subject: [patch] Fix PR37375 [graphite] Parameter detection and scev only take a surrounding loop as border
Hi,
As proposed on the bug report,
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37375
here is the patch that fixes this scev instantiation problem. The patch
has been bootstrapped and tested on amd64-linux. I will commit
this patch to trunk.
Sebastian Pop
--
AMD - GNU Tools
2008-09-05 Sebastian Pop <sebastian.pop@amd.com>
PR tree-optimization/37375
* tree-scalar-evolution.c (scev_info_str): Add field instantiated_below.
(new_scev_info_str, eq_scev_info, find_var_scev_info,
set_scalar_evolution, get_scalar_evolution, get_instantiated_value,
set_instantiated_value): Pass instantiated_below.
(analyze_scalar_evolution_1, analyze_scalar_evolution): Update calls to
above functions.
(instantiate_scev_1, instantiate_scev): Pass a basic block above which the
definitions are not instantiated.
* tree-scalar-evolution.h (instantiate_scev): Update declaration.
(block_before_loop): New.
* tree-data-ref.c (dr_analyze_indices): Update uses of instantiate_scev.
* graphite.c (block_before_scop): New.
(loop_affine_expr, stmt_simple_for_scop_p, harmful_stmt_in_bb): Pass a
basic block, not a loop for determining the parameters.
(scopdet_edge_info, build_scops_1): Do not pass outermost loop in the
scop.
(idx_record_params, find_params_in_bb, find_scop_parameters,
build_loop_iteration_domains, add_conditions_to_domain): Update calls
to instantiate_scev.
* Makefile.in (cfgloopmanip.o): Add missing dependency on TREE_FLOW_H.
Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c (revision 140041)
+++ tree-scalar-evolution.c (working copy)
@@ -175,8 +175,8 @@ along with GCC; see the file COPYING3.
value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
{0, +, 1}_1. To obtain the evolution function in loop_3 and
instantiate the scalar variables up to loop_1, one has to use:
- instantiate_scev (loop_1, loop_3, "j + k"). The result of this
- call is {{0, +, 1}_1, +, 1}_2.
+ instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
+ The result of this call is {{0, +, 1}_1, +, 1}_2.
Example 3: Higher degree polynomials.
@@ -278,11 +278,13 @@ along with GCC; see the file COPYING3.
static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
-/* The cached information about a ssa name VAR, claiming that inside LOOP,
- the value of VAR can be expressed as CHREC. */
+/* The cached information about an SSA name VAR, claiming that below
+ basic block INSTANTIATED_BELOW, the value of VAR can be expressed
+ as CHREC. */
struct scev_info_str GTY(())
{
+ basic_block instantiated_below;
tree var;
tree chrec;
};
@@ -306,22 +308,21 @@ tree chrec_dont_know;
happen, then it qualifies it with chrec_known. */
tree chrec_known;
-static bitmap already_instantiated;
-
static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
-/* Constructs a new SCEV_INFO_STR structure. */
+/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
static inline struct scev_info_str *
-new_scev_info_str (tree var)
+new_scev_info_str (basic_block instantiated_below, tree var)
{
struct scev_info_str *res;
res = GGC_NEW (struct scev_info_str);
res->var = var;
res->chrec = chrec_not_analyzed_yet;
-
+ res->instantiated_below = instantiated_below;
+
return res;
}
@@ -341,7 +342,8 @@ eq_scev_info (const void *e1, const void
const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
- return elt1->var == elt2->var;
+ return (elt1->var == elt2->var
+ && elt1->instantiated_below == elt2->instantiated_below);
}
/* Deletes database element E. */
@@ -352,22 +354,22 @@ del_scev_info (void *e)
ggc_free (e);
}
-/* Get the index corresponding to VAR in the current LOOP. If
- it's the first time we ask for this VAR, then we return
- chrec_not_analyzed_yet for this VAR and return its index. */
+/* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
+ A first query on VAR returns chrec_not_analyzed_yet. */
static tree *
-find_var_scev_info (tree var)
+find_var_scev_info (basic_block instantiated_below, tree var)
{
struct scev_info_str *res;
struct scev_info_str tmp;
PTR *slot;
tmp.var = var;
+ tmp.instantiated_below = instantiated_below;
slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
if (!*slot)
- *slot = new_scev_info_str (var);
+ *slot = new_scev_info_str (instantiated_below, var);
res = (struct scev_info_str *) *slot;
return &res->chrec;
@@ -570,20 +572,22 @@ chrec_is_positive (tree chrec, bool *val
/* Associate CHREC to SCALAR. */
static void
-set_scalar_evolution (tree scalar, tree chrec)
+set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
{
tree *scalar_info;
if (TREE_CODE (scalar) != SSA_NAME)
return;
- scalar_info = find_var_scev_info (scalar);
+ scalar_info = find_var_scev_info (instantiated_below, scalar);
if (dump_file)
{
if (dump_flags & TDF_DETAILS)
{
fprintf (dump_file, "(set_scalar_evolution \n");
+ fprintf (dump_file, " instantiated_below = %d \n",
+ instantiated_below->index);
fprintf (dump_file, " (scalar = ");
print_generic_expr (dump_file, scalar, 0);
fprintf (dump_file, ")\n (scalar_evolution = ");
@@ -597,10 +601,11 @@ set_scalar_evolution (tree scalar, tree
*scalar_info = chrec;
}
-/* Retrieve the chrec associated to SCALAR in the LOOP. */
+/* Retrieve the chrec associated to SCALAR instantiated below
+ INSTANTIATED_BELOW block. */
static tree
-get_scalar_evolution (tree scalar)
+get_scalar_evolution (basic_block instantiated_below, tree scalar)
{
tree res;
@@ -620,7 +625,7 @@ get_scalar_evolution (tree scalar)
switch (TREE_CODE (scalar))
{
case SSA_NAME:
- res = *find_var_scev_info (scalar);
+ res = *find_var_scev_info (instantiated_below, scalar);
break;
case REAL_CST:
@@ -1845,7 +1850,7 @@ analyze_scalar_evolution_1 (struct loop
res = var;
if (loop == def_loop)
- set_scalar_evolution (var, res);
+ set_scalar_evolution (block_before_loop (loop), var, res);
return res;
}
@@ -1879,7 +1884,8 @@ analyze_scalar_evolution (struct loop *l
fprintf (dump_file, ")\n");
}
- res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
+ res = get_scalar_evolution (block_before_loop (loop), var);
+ res = analyze_scalar_evolution_1 (loop, var, res);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
@@ -1926,14 +1932,17 @@ analyze_scalar_evolution_in_loop (struct
}
}
-/* Returns instantiated value for VERSION in CACHE. */
+/* Returns from CACHE the value for VERSION instantiated below
+ INSTANTIATED_BELOW block. */
static tree
-get_instantiated_value (htab_t cache, tree version)
+get_instantiated_value (htab_t cache, basic_block instantiated_below,
+ tree version)
{
struct scev_info_str *info, pattern;
pattern.var = version;
+ pattern.instantiated_below = instantiated_below;
info = (struct scev_info_str *) htab_find (cache, &pattern);
if (info)
@@ -1942,10 +1951,12 @@ get_instantiated_value (htab_t cache, tr
return NULL_TREE;
}
-/* Sets instantiated value for VERSION to VAL in CACHE. */
+/* Sets in CACHE the value of VERSION instantiated below basic block
+ INSTANTIATED_BELOW to VAL. */
static void
-set_instantiated_value (htab_t cache, tree version, tree val)
+set_instantiated_value (htab_t cache, basic_block instantiated_below,
+ tree version, tree val)
{
struct scev_info_str *info, pattern;
PTR *slot;
@@ -1954,7 +1965,7 @@ set_instantiated_value (htab_t cache, tr
slot = htab_find_slot (cache, &pattern, INSERT);
if (!*slot)
- *slot = new_scev_info_str (version);
+ *slot = new_scev_info_str (instantiated_below, version);
info = (struct scev_info_str *) *slot;
info->chrec = val;
}
@@ -1989,7 +2000,7 @@ loop_closed_phi_def (tree var)
return NULL_TREE;
}
-/* Analyze all the parameters of the chrec, between INSTANTIATION_LOOP
+/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
and EVOLUTION_LOOP, that were left under a symbolic form.
CHREC is the scalar evolution to instantiate.
@@ -2004,7 +2015,7 @@ loop_closed_phi_def (tree var)
instantiated, and to stop if it exceeds some limit. */
static tree
-instantiate_scev_1 (struct loop *instantiation_loop,
+instantiate_scev_1 (basic_block instantiate_below,
struct loop *evolution_loop, tree chrec,
bool fold_conversions, htab_t cache, int size_expr)
{
@@ -2030,7 +2041,7 @@ instantiate_scev_1 (struct loop *instant
evolutions in outer loops), nothing to do. */
if (!def_bb
|| loop_depth (def_bb->loop_father) == 0
- || !flow_bb_inside_loop_p (instantiation_loop, def_bb))
+ || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
return chrec;
/* We cache the value of instantiated variable to avoid exponential
@@ -2042,31 +2053,17 @@ instantiate_scev_1 (struct loop *instant
| a_2 -> {0, +, 1, +, a_2}_1 */
- res = get_instantiated_value (cache, chrec);
+ res = get_instantiated_value (cache, instantiate_below, chrec);
if (res)
return res;
- /* Store the convenient value for chrec in the structure. If it
- is defined outside of the loop, we may just leave it in symbolic
- form, otherwise we need to admit that we do not know its behavior
- inside the loop. */
- res = !flow_bb_inside_loop_p (instantiation_loop, def_bb)
- ? chrec : chrec_dont_know;
- set_instantiated_value (cache, chrec, res);
-
- /* To make things even more complicated, instantiate_scev_1
- calls analyze_scalar_evolution that may call # of iterations
- analysis that may in turn call instantiate_scev_1 again.
- To prevent the infinite recursion, keep also the bitmap of
- ssa names that are being instantiated globally. */
- if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
- return res;
+ res = chrec_dont_know;
+ set_instantiated_value (cache, instantiate_below, chrec, res);
def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
/* If the analysis yields a parametric chrec, instantiate the
result again. */
- bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
res = analyze_scalar_evolution (def_loop, chrec);
/* Don't instantiate loop-closed-ssa phi nodes. */
@@ -2085,23 +2082,21 @@ instantiate_scev_1 (struct loop *instant
}
else if (res != chrec_dont_know)
- res = instantiate_scev_1 (instantiation_loop, evolution_loop, res,
+ res = instantiate_scev_1 (instantiate_below, evolution_loop, res,
fold_conversions, cache, size_expr);
- bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
-
/* Store the correct value to the cache. */
- set_instantiated_value (cache, chrec, res);
+ set_instantiated_value (cache, instantiate_below, chrec, res);
return res;
case POLYNOMIAL_CHREC:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
CHREC_LEFT (chrec), fold_conversions, cache,
size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
CHREC_RIGHT (chrec), fold_conversions, cache,
size_expr);
if (op1 == chrec_dont_know)
@@ -2117,13 +2112,13 @@ instantiate_scev_1 (struct loop *instant
case POINTER_PLUS_EXPR:
case PLUS_EXPR:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0), fold_conversions, cache,
size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 1), fold_conversions, cache,
size_expr);
if (op1 == chrec_dont_know)
@@ -2139,13 +2134,13 @@ instantiate_scev_1 (struct loop *instant
return chrec;
case MINUS_EXPR:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0), fold_conversions, cache,
size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 1),
fold_conversions, cache, size_expr);
if (op1 == chrec_dont_know)
@@ -2161,13 +2156,13 @@ instantiate_scev_1 (struct loop *instant
return chrec;
case MULT_EXPR:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0),
fold_conversions, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 1),
fold_conversions, cache, size_expr);
if (op1 == chrec_dont_know)
@@ -2183,7 +2178,7 @@ instantiate_scev_1 (struct loop *instant
return chrec;
CASE_CONVERT:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0),
fold_conversions, cache, size_expr);
if (op0 == chrec_dont_know)
@@ -2221,19 +2216,19 @@ instantiate_scev_1 (struct loop *instant
switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
{
case 3:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0),
fold_conversions, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 1),
fold_conversions, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
- op2 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op2 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 2),
fold_conversions, cache, size_expr);
if (op2 == chrec_dont_know)
@@ -2248,13 +2243,13 @@ instantiate_scev_1 (struct loop *instant
TREE_TYPE (chrec), op0, op1, op2);
case 2:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0),
fold_conversions, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 1),
fold_conversions, cache, size_expr);
if (op1 == chrec_dont_know)
@@ -2266,7 +2261,7 @@ instantiate_scev_1 (struct loop *instant
return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
case 1:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0),
fold_conversions, cache, size_expr);
if (op0 == chrec_dont_know)
@@ -2287,12 +2282,13 @@ instantiate_scev_1 (struct loop *instant
}
/* Analyze all the parameters of the chrec that were left under a
- symbolic form. INSTANTIATION_LOOP is the loop in which symbolic
- names have to be instantiated, and EVOLUTION_LOOP is the loop in
- which the evolution of scalars have to be analyzed. */
+ symbolic form. INSTANTIATE_BELOW is the basic block that stops the
+ recursive instantiation of parameters: a parameter is a variable
+ that is defined in a basic block that dominates INSTANTIATE_BELOW or
+ a function parameter. */
tree
-instantiate_scev (struct loop *instantiation_loop, struct loop *evolution_loop,
+instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
tree chrec)
{
tree res;
@@ -2301,14 +2297,14 @@ instantiate_scev (struct loop *instantia
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(instantiate_scev \n");
- fprintf (dump_file, " (instantiation_loop = %d)\n", instantiation_loop->num);
+ fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
fprintf (dump_file, " (chrec = ");
print_generic_expr (dump_file, chrec, 0);
fprintf (dump_file, ")\n");
}
- res = instantiate_scev_1 (instantiation_loop, evolution_loop, chrec, false,
+ res = instantiate_scev_1 (instantiate_below, evolution_loop, chrec, false,
cache, 0);
if (dump_file && (dump_flags & TDF_DETAILS))
@@ -2332,7 +2328,8 @@ tree
resolve_mixers (struct loop *loop, tree chrec)
{
htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
- tree ret = instantiate_scev_1 (loop, loop, chrec, true, cache, 0);
+ tree ret = instantiate_scev_1 (block_before_loop (loop), loop, chrec, true,
+ cache, 0);
htab_delete (cache);
return ret;
}
@@ -2677,7 +2674,6 @@ scev_initialize (void)
del_scev_info,
ggc_calloc,
ggc_free);
- already_instantiated = BITMAP_ALLOC (NULL);
initialize_scalar_evolutions_analyzer ();
@@ -2791,7 +2787,6 @@ scev_finalize (void)
if (!scalar_evolution_info)
return;
htab_delete (scalar_evolution_info);
- BITMAP_FREE (already_instantiated);
scalar_evolution_info = NULL;
}
Index: tree-scalar-evolution.h
===================================================================
--- tree-scalar-evolution.h (revision 140041)
+++ tree-scalar-evolution.h (working copy)
@@ -29,7 +29,7 @@ extern void scev_initialize (void);
extern void scev_reset (void);
extern void scev_finalize (void);
extern tree analyze_scalar_evolution (struct loop *, tree);
-extern tree instantiate_scev (struct loop *, struct loop *, tree);
+extern tree instantiate_scev (basic_block, struct loop *, tree);
extern tree resolve_mixers (struct loop *, tree);
extern void gather_stats_on_scev_database (void);
extern void scev_analysis (void);
@@ -37,6 +37,13 @@ unsigned int scev_const_prop (void);
extern bool simple_iv (struct loop *, gimple, tree, affine_iv *, bool);
+static inline basic_block
+block_before_loop (loop_p loop)
+{
+ edge preheader = loop_preheader_edge (loop);
+ return (preheader ? preheader->src : ENTRY_BLOCK_PTR);
+}
+
/* Analyze all the parameters of the chrec that were left under a
symbolic form. LOOP is the loop in which symbolic names have to
be analyzed and instantiated. */
@@ -44,7 +51,7 @@ extern bool simple_iv (struct loop *, gi
static inline tree
instantiate_parameters (struct loop *loop, tree chrec)
{
- return instantiate_scev (loop, loop, chrec);
+ return instantiate_scev (block_before_loop (loop), loop, chrec);
}
/* Returns the loop of the polynomial chrec CHREC. */
Index: tree-data-ref.c
===================================================================
--- tree-data-ref.c (revision 140041)
+++ tree-data-ref.c (working copy)
@@ -747,6 +747,7 @@ dr_analyze_indices (struct data_referenc
VEC (tree, heap) *access_fns = NULL;
tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
tree base, off, access_fn;
+ basic_block before_loop = block_before_loop (nest);
while (handled_component_p (aref))
{
@@ -754,7 +755,7 @@ dr_analyze_indices (struct data_referenc
{
op = TREE_OPERAND (aref, 1);
access_fn = analyze_scalar_evolution (loop, op);
- access_fn = instantiate_scev (nest, loop, access_fn);
+ access_fn = instantiate_scev (before_loop, loop, access_fn);
VEC_safe_push (tree, heap, access_fns, access_fn);
TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
@@ -767,7 +768,7 @@ dr_analyze_indices (struct data_referenc
{
op = TREE_OPERAND (aref, 0);
access_fn = analyze_scalar_evolution (loop, op);
- access_fn = instantiate_scev (nest, loop, access_fn);
+ access_fn = instantiate_scev (before_loop, loop, access_fn);
base = initial_condition (access_fn);
split_constant_offset (base, &base, &off);
access_fn = chrec_replace_initial_condition (access_fn,
Index: graphite.c
===================================================================
--- graphite.c (revision 140041)
+++ graphite.c (working copy)
@@ -717,16 +717,24 @@ outermost_loop_in_scop (scop_p scop, bas
return nest;
}
+/* Returns the block preceding the entry of SCOP. */
+
+static basic_block
+block_before_scop (scop_p scop)
+{
+ return SESE_ENTRY (SCOP_REGION (scop))->src;
+}
+
/* Return true when EXPR is an affine function in LOOP with parameters
- instantiated relative to outermost_loop. */
+ instantiated relative to SCOP_ENTRY. */
static bool
-loop_affine_expr (struct loop *outermost_loop, struct loop *loop, tree expr)
+loop_affine_expr (basic_block scop_entry, struct loop *loop, tree expr)
{
- int n = outermost_loop->num;
+ int n = scop_entry->loop_father->num;
tree scev = analyze_scalar_evolution (loop, expr);
- scev = instantiate_scev (outermost_loop, loop, scev);
+ scev = instantiate_scev (scop_entry, loop, scev);
return (evolution_function_is_invariant_p (scev, n)
|| evolution_function_is_affine_multivariate_p (scev, n));
@@ -751,11 +759,11 @@ is_simple_operand (loop_p loop, gimple s
}
/* Return true only when STMT is simple enough for being handled by
- Graphite. This depends on OUTERMOST_LOOP, as the parametetrs are
- initialized relative to this loop. */
+ Graphite. This depends on SCOP_ENTRY, as the parametetrs are
+ initialized relative to this basic block. */
static bool
-stmt_simple_for_scop_p (struct loop *outermost_loop, gimple stmt)
+stmt_simple_for_scop_p (basic_block scop_entry, gimple stmt)
{
basic_block bb = gimple_bb (stmt);
struct loop *loop = bb->loop_father;
@@ -791,11 +799,11 @@ stmt_simple_for_scop_p (struct loop *out
|| code == GE_EXPR))
return false;
- if (!outermost_loop)
+ if (!scop_entry)
return false;
FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
- if (!loop_affine_expr (outermost_loop, loop, op))
+ if (!loop_affine_expr (scop_entry, loop, op))
return false;
return true;
@@ -850,18 +858,17 @@ stmt_simple_for_scop_p (struct loop *out
}
/* Returns the statement of BB that contains a harmful operation: that
- can be a function call with side effects, data dependences that
- cannot be computed in OUTERMOST_LOOP, the induction variables are
- not linear with respect to OUTERMOST_LOOP, etc. The current open
+ can be a function call with side effects, the induction variables
+ are not linear with respect to SCOP_ENTRY, etc. The current open
scop should end before this statement. */
static gimple
-harmful_stmt_in_bb (struct loop *outermost_loop, basic_block bb)
+harmful_stmt_in_bb (basic_block scop_entry, basic_block bb)
{
gimple_stmt_iterator gsi;
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- if (!stmt_simple_for_scop_p (outermost_loop, gsi_stmt (gsi)))
+ if (!stmt_simple_for_scop_p (scop_entry, gsi_stmt (gsi)))
return gsi_stmt (gsi);
return NULL;
@@ -1048,20 +1055,28 @@ struct scopdet_info
};
static struct scopdet_info build_scops_1 (edge, VEC (scop_p, heap) **,
- loop_p, loop_p);
+ loop_p);
/* Checks, if a bb can be added to a SCoP. */
static struct scopdet_info
-scopdet_edge_info (edge ee, loop_p outermost_loop,
+scopdet_edge_info (edge ee,
VEC (scop_p, heap) **scops, gbb_type type, gimple *stmt)
{
basic_block bb = ee->dest;
struct loop *loop = bb->loop_father;
struct scopdet_info result;
+ basic_block scop_entry;
- *stmt = harmful_stmt_in_bb (outermost_loop, bb);
+ if (VEC_length (scop_p, *scops) != 0)
+ scop_entry = block_before_scop (VEC_last (scop_p, *scops));
+ else if (loop->header)
+ scop_entry = loop->header;
+ else
+ scop_entry = ENTRY_BLOCK_PTR;
+
+ *stmt = harmful_stmt_in_bb (scop_entry, bb);
result.difficult = (*stmt != NULL);
result.last = NULL;
@@ -1084,7 +1099,7 @@ scopdet_edge_info (edge ee, loop_p outer
VEC (scop_p, heap) *tmp_scops = VEC_alloc (scop_p, heap, 3);
struct scopdet_info sinfo;
- sinfo = build_scops_1 (ee, &tmp_scops, loop, outermost_loop);
+ sinfo = build_scops_1 (ee, &tmp_scops, loop);
result.last = single_exit (bb->loop_father);
@@ -1117,20 +1132,18 @@ scopdet_edge_info (edge ee, loop_p outer
case GBB_LOOP_MULT_EXIT_HEADER:
{
/* XXX: Handle loop nests with the same header. */
- /* XXX: Handle iterative optimization of outermost_loop. */
/* XXX: For now we just do not join loops with multiple exits. If the
exits lead to the same bb it may be possible to join the loop. */
VEC (scop_p, heap) *tmp_scops = VEC_alloc (scop_p, heap, 3);
VEC (edge, heap) *exits = get_loop_exit_edges (loop);
edge e;
int i;
- build_scops_1 (ee, &tmp_scops, loop, outermost_loop);
+ build_scops_1 (ee, &tmp_scops, loop);
for (i = 0; VEC_iterate (edge, exits, i, e); i++)
if (dominated_by_p (CDI_DOMINATORS, e->dest, e->src)
&& e->dest->loop_father == loop_outer (loop))
- build_scops_1 (e, &tmp_scops, e->dest->loop_father,
- outermost_loop);
+ build_scops_1 (e, &tmp_scops, e->dest->loop_father);
result.next = NULL;
result.last = NULL;
@@ -1199,7 +1212,7 @@ scopdet_edge_info (edge ee, loop_p outer
continue;
}
- sinfo = build_scops_1 (e, &tmp_scops, loop, outermost_loop);
+ sinfo = build_scops_1 (e, &tmp_scops, loop);
result.exits |= sinfo.exits;
result.last = sinfo.last;
@@ -1261,10 +1274,9 @@ scopdet_edge_info (edge ee, loop_p outer
e = split_block (dom_bb, NULL);
if (loop_depth (loop) > loop_depth (dom_bb->loop_father))
- sinfo = build_scops_1 (e, &tmp_scops, loop_outer (loop),
- outermost_loop);
+ sinfo = build_scops_1 (e, &tmp_scops, loop_outer (loop));
else
- sinfo = build_scops_1 (e, &tmp_scops, loop, outermost_loop);
+ sinfo = build_scops_1 (e, &tmp_scops, loop);
result.exits |= sinfo.exits;
@@ -1335,8 +1347,7 @@ end_scop (scop_p scop, edge exit, bool s
/* Creates the SCoPs and writes entry and exit points for every SCoP. */
static struct scopdet_info
-build_scops_1 (edge start, VEC (scop_p, heap) **scops, loop_p loop,
- loop_p outermost_loop)
+build_scops_1 (edge start, VEC (scop_p, heap) **scops, loop_p loop)
{
edge current = start;
@@ -1357,7 +1368,7 @@ build_scops_1 (edge start, VEC (scop_p,
and can only be added if all bbs in deeper layers are simple. */
while (current != NULL)
{
- sinfo = scopdet_edge_info (current, outermost_loop, scops,
+ sinfo = scopdet_edge_info (current, scops,
get_bb_type (current->dest, loop), &stmt);
if (!in_scop && !(sinfo.exits || sinfo.difficult))
@@ -1433,7 +1444,7 @@ static void
build_scops (void)
{
struct loop *loop = current_loops->tree_root;
- build_scops_1 (single_succ_edge (ENTRY_BLOCK_PTR), ¤t_scops, loop, loop);
+ build_scops_1 (single_succ_edge (ENTRY_BLOCK_PTR), ¤t_scops, loop);
}
/* Gather the basic blocks belonging to the SCOP. */
@@ -1895,19 +1906,15 @@ idx_record_params (tree base, tree *idx,
tree scev;
scop_p scop = data->scop;
struct loop *loop = data->loop;
+ Value one;
scev = analyze_scalar_evolution (loop, *idx);
- scev = instantiate_scev (outermost_loop_in_scop (scop, loop->header),
- loop, scev);
-
- {
- Value one;
+ scev = instantiate_scev (block_before_scop (scop), loop, scev);
- value_init (one);
- value_set_si (one, 1);
- scan_tree_for_params (scop, scev, NULL, 0, one, false);
- value_clear (one);
- }
+ value_init (one);
+ value_set_si (one, 1);
+ scan_tree_for_params (scop, scev, NULL, 0, one, false);
+ value_clear (one);
}
return true;
@@ -1957,11 +1964,11 @@ find_params_in_bb (scop_p scop, basic_bl
lhs = gimple_cond_lhs (stmt);
lhs = analyze_scalar_evolution (loop, lhs);
- lhs = instantiate_scev (nest, loop, lhs);
+ lhs = instantiate_scev (block_before_scop (scop), loop, lhs);
rhs = gimple_cond_rhs (stmt);
rhs = analyze_scalar_evolution (loop, rhs);
- rhs = instantiate_scev (nest, loop, rhs);
+ rhs = instantiate_scev (block_before_scop (scop), loop, rhs);
value_init (one);
scan_tree_for_params (scop, lhs, NULL, 0, one, false);
@@ -2081,8 +2088,7 @@ find_scop_parameters (scop_p scop)
continue;
nb_iters = analyze_scalar_evolution (loop, nb_iters);
- nb_iters = instantiate_scev (outermost_loop_in_scop (scop, loop->header),
- loop, nb_iters);
+ nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
scan_tree_for_params (scop, nb_iters, NULL, 0, one, false);
}
@@ -2209,10 +2215,10 @@ build_loop_iteration_domains (scop_p sco
row++;
value_set_si (cstr->p[row][0], 1);
value_set_si (cstr->p[row][loop_col], -1);
+
nb_iters = analyze_scalar_evolution (loop, nb_iters);
- nb_iters =
- instantiate_scev (outermost_loop_in_scop (scop, loop->header),
- loop, nb_iters);
+ nb_iters = instantiate_scev (block_before_scop (scop), loop, nb_iters);
+
value_init (one);
value_set_si (one, 1);
scan_tree_for_params (scop, nb_iters, cstr, row, one, false);
@@ -2333,15 +2339,15 @@ add_conditions_to_domain (graphite_bb_p
tree left;
tree right;
loop_p loop = GBB_BB (gb)->loop_father;
- loop_p outermost = outermost_loop_in_scop (scop, GBB_BB (gb));
left = gimple_cond_lhs (stmt);
right = gimple_cond_rhs (stmt);
left = analyze_scalar_evolution (loop, left);
right = analyze_scalar_evolution (loop, right);
- left = instantiate_scev (outermost, loop, left);
- right = instantiate_scev (outermost, loop, right);
+
+ left = instantiate_scev (block_before_scop (scop), loop, left);
+ right = instantiate_scev (block_before_scop (scop), loop, right);
code = gimple_cond_code (stmt);
@@ -3974,13 +3980,13 @@ gbb_can_be_ignored (graphite_bb_p gb)
XXX: Just a heuristic, that needs further investigation. */
case GIMPLE_ASSIGN:
{
- tree var = gimple_assign_lhs (stmt);
+ tree var = gimple_assign_lhs (stmt);
var = analyze_scalar_evolution (loop, var);
- var = instantiate_scev (outermost_loop_in_scop (scop,
- GBB_BB (gb)),
- loop, var);
+ var = instantiate_scev (block_before_scop (scop), loop, var);
+
if (TREE_CODE (var) == SCEV_NOT_KNOWN)
return false;
+
break;
}
/* Otherwise not ignoreable. */
Index: Makefile.in
===================================================================
--- Makefile.in (revision 140041)
+++ Makefile.in (working copy)
@@ -2814,7 +2814,7 @@ loop-invariant.o : loop-invariant.c $(CO
$(HASHTAB_H) except.h
cfgloopmanip.o : cfgloopmanip.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
$(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(CFGLAYOUT_H) output.h \
- coretypes.h $(TM_H) cfghooks.h $(OBSTACK_H)
+ coretypes.h $(TM_H) cfghooks.h $(OBSTACK_H) $(TREE_FLOW_H)
loop-init.o : loop-init.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(GGC_H) \
$(BASIC_BLOCK_H) hard-reg-set.h $(CFGLOOP_H) $(CFGLAYOUT_H) \
coretypes.h $(TM_H) $(OBSTACK_H) tree-pass.h $(TIMEVAR_H) $(FLAGS_H) $(DF_H)