[lno] scev fixes
Dorit Naishlos
DORIT@il.ibm.com
Wed Mar 31 14:36:00 GMT 2004
Hi Zdenek,
I get a few errors trying to compile SPEC with lno (todays snapshot), using
-ftree-loop-optimize (none of the following errors occurs when this flag is
not used):
(1) compilation failure in eon (see details below)
(2) compilation seems to get stuck during compilation of sixtrack (?)
(3) miscompare in twolf
(4) miscompare in equake
I am compiling on powerpc-apple-darwin7.0.0. Could you please check which
of the above are reproducible on your platform? I will try to dig further
into those that aren't. I already know that you can't reproduce the problem
in twolf (3), so I'm trying to look into that one now.
thanks,
dorit
(1) the error compiling eon:
ggJitterSample2.cc: In constructor `ggJitterSample2::ggJitterSample2()':
ggJitterSample2.cc:52: error: SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set
for SSA_NAME: <D35747>_162
in statement:
<D35747>_116 = PHI <<D35747>_88(3), <D35747>_85(4), <D35747>_162(5)>;
PHI argument
<D35747>_162
for PHI node
<D35747>_116 = PHI <<D35747>_88(3), <D35747>_85(4), <D35747>_162(5)>;
ggJitterSample2.cc:52: error: SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set
for SSA_NAME: _ZTV15ggJitterSample2<D34612>_164
in statement:
_ZTV15ggJitterSample2<D34612>_124 = PHI
<_ZTV15ggJitterSample2<D34612>_135(3),
_ZTV15ggJitterSample2<D34612>_139(4),
_ZTV15ggJitterSample2<D34612>_164(5)>;
PHI argument
_ZTV15ggJitterSample2<D34612>_164
for PHI node
_ZTV15ggJitterSample2<D34612>_124 = PHI
<_ZTV15ggJitterSample2<D34612>_135(3),
_ZTV15ggJitterSample2<D34612>_139(4),
_ZTV15ggJitterSample2<D34612>_164(5)>;
ggJitterSample2.cc:52: error: SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set
for SSA_NAME: _ZTV9ggSample2<D34540>_163
in statement:
_ZTV9ggSample2<D34540>_130 = PHI <_ZTV9ggSample2<D34540>_136(3),
_ZTV9ggSample2<D34540>_138(4), _ZTV9ggSample2<D34540>_163(5)>;
PHI argument
_ZTV9ggSample2<D34540>_163
for PHI node
_ZTV9ggSample2<D34540>_130 = PHI <_ZTV9ggSample2<D34540>_136(3),
_ZTV9ggSample2<D34540>_138(4), _ZTV9ggSample2<D34540>_163(5)>;
ggJitterSample2.cc:52: internal compiler error: verify_ssa failed.
==================================
(2) compilation seems to hang at tree_loop_optimizer_init when compiling
the file daten.f from sixtrack:
(gdb) backtrace
#1 0x003d615c in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:195
#2 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
........
#36 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
#37 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
#38 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
#39 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
#40 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
#41 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
#42 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
#43 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
#44 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
#45 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
#46 0x003d61a0 in walk_dominator_tree (walk_data=0xbffff480, bb=0x4165c80)
at ../../gcc/gcc/domwalk.c:205
#47 0x003731c4 in rewrite_ssa_into_ssa (names_to_rename=0xb5d080) at
../../gcc/gcc/tree-into-ssa.c:1653
#48 0x003bbc4c in rewrite_into_loop_closed_ssa () at
../../gcc/gcc/tree-ssa-loop-manip.c:918
#49 0x00377eac in tree_loop_optimizer_init (dump=0x21eb180,
canonicalize_ssa=1099980784) at ../../gcc/gcc/tree-ssa-loop.c:64
#50 0x00377ee0 in tree_ssa_loop_opt () at ../../gcc/gcc/tree-ssa-loop.c:82
#51 0x001d8c10 in execute_pass_list (pass=0x5695ec) at
../../gcc/gcc/tree-optimize.c:417
#52 0x001d8c74 in execute_pass_list (pass=0x55ec70) at
../../gcc/gcc/tree-optimize.c:447
#53 0x001d8fac in tree_rest_of_compilation (fndecl=0x6f7e80,
nested_p=false) at ../../gcc/gcc/tree-optimize.c:540
#54 0x0001bcdc in c_expand_body_1 (fndecl=0x558e5c, nested_p=68574336) at
../../gcc/gcc/c-decl.c:6195
#55 0x001d0070 in cgraph_expand_function (node=0x6f7e80) at
../../gcc/gcc/cgraphunit.c:789
#56 0x001d1678 in cgraph_optimize () at ../../gcc/gcc/cgraphunit.c:1671
#57 0x00057248 in c_objc_common_finish_file () at
../../gcc/gcc/c-objc-common.c:243
#58 0x00096374 in toplev_main (argc=3221224546, argv=0x555c98) at
../../gcc/gcc/toplev.c:1641
#59 0x00001ab4 in _start (argc=25, argv=0xbffffaac, envp=0xbffffb14) at
/SourceCache/Csu/Csu-46/crt.c:267
#60 0x00001928 in start ()
Zdenek Dvorak
<rakdver@atrey.karlin.m To: gcc-patches@gcc.gnu.org
ff.cuni.cz> cc:
Sent by: Subject: [lno] scev fixes
gcc-patches-owner@gcc.g
nu.org
31/03/2004 00:05
Hello,
this patch fixes some further problems with scev I have detected when
comparing it with ivopts iv analysis. With these fixes scev performs
strictly better, so I will start using it in ivopts soon.
The problems fixed:
-- several problems with types
-- a few unhandled cases in folding
-- givs not being detected because of colision of marks on phis used
also by biv analysis
-- removed the system of inner/outer chrecs associated with ssa names
that did not really work well in more complicated cases. Instead
we now cache the evolutions of ssa names separately for each loop;
we do not cache outer chrecs at all for now (they are easy enough
to compute)
-- outer chrecs for loop invariants are computed even if we do not
know the number of iterations of the loop
+ some other minor cleanups.
Zdenek
Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.109
diff -c -3 -p -r1.1.2.109 ChangeLog.lno
*** ChangeLog.lno 30 Mar 2004 17:45:52 -0000 1.1.2.109
--- ChangeLog.lno 30 Mar 2004 20:53:34 -0000
***************
*** 1,3 ****
--- 1,32 ----
+ 2004-03-30 Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
+
+ * lambda-code.c (gcc_loop_to_lambda_loop): Changed due to
changes in
+ scev.
+ * tree-data-ref.c (analyze_array_indexes, analyze_array):
Ditto.
+ * tree-elim-check.c (try_eliminate_check): Ditto.
+ * tree-vectorizer.c (vect_analyze_scalar_cycles): Ditto.
+ * tree-chrec.c (chrec_fold_plus_1): Handle exponential +
peeled chrec
+ correctly. Use correct types.
+ (chrec_fold_negate): New.
+ (chrec_merge): Short-circuit the case when the merged values
are
+ identical.
+ (no_evolution_in_loop_p): Handle chrec_top correctly.
+ (chrec_convert): Handle polynomial and exponential chrecs
corectly.
+ (chrec_type): Use TREE_TYPE.
+ * tree-chrec.h (chrec_fold_negate): Declare.
+ * tree-phinodes.c (create_phi_node): Do not initialize
PHI_MARKED.
+ * tree-scalar-evolution.c: Handle evolutions analysed from
different
+ loops correctly. Do not use PHI_MARKED. Use correct types.
+ * tree-scalar-evolution.h (analyze_scalar_evolution,
+ instantiate_parameters): Declaration changed.
+ (struct scev_info_str): Moved to tree-scalar-evolution.c.
+ (MI_VAR, MI_INNER_LOOPS_CHREC, MI_OUTER_LOOPS_CHREC): Removed.
+ (new_scev_info_str): Moved to tree-scalar-evolution.c.
+ * tree-ssa-loop-manip.c (add_exit_phis_use): Just add exit
phis for
+ superloops of the loop containing the definition.
+ * tree.h (PHI_MARKED): Removed.
+ (tree_phi_node): Field 'marked' removed.
+
2004-03-30 Sebastian Pop <sebastian.pop@ensmp.fr>
* tree-chrec.c (chrec_contains_symbols): Factorize conditions,
Index: lambda-code.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-code.c,v
retrieving revision 1.1.2.2
diff -c -3 -p -r1.1.2.2 lambda-code.c
*** lambda-code.c 21 Mar 2004 03:20:07 -0000 1.1.2.2
--- lambda-code.c 30 Mar 2004 20:53:35 -0000
*************** gcc_loop_to_lambda_loop (struct loop *lo
*** 1099,1106 ****
}
access_fn = instantiate_parameters
! (loop_num (loop),
! analyze_scalar_evolution (loop_num (loop), PHI_RESULT (phi)));
if (!access_fn)
{
if (dump_file && (dump_flags & TDF_DETAILS))
--- 1099,1106 ----
}
access_fn = instantiate_parameters
! (loop,
! analyze_scalar_evolution (loop, PHI_RESULT (phi)));
if (!access_fn)
{
if (dump_file && (dump_flags & TDF_DETAILS))
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.c,v
retrieving revision 1.1.2.11
diff -c -3 -p -r1.1.2.11 tree-chrec.c
*** tree-chrec.c 30 Mar 2004 17:45:52 -0000 1.1.2.11
--- tree-chrec.c 30 Mar 2004 20:53:35 -0000
*************** chrec_fold_plus_1 (enum tree_code code,
*** 910,915 ****
--- 910,918 ----
case EXPONENTIAL_CHREC:
return chrec_fold_plus_expo_expo (code, type, op0, op1);
+ case PEELED_CHREC:
+ return build (code, type, op0, op1);
+
default:
return chrec_fold_plus_expo_cst (code, type, op0, op1);
}
*************** chrec_fold_plus_1 (enum tree_code code,
*** 989,996 ****
return build_polynomial_chrec
(CHREC_VARIABLE (op1),
chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
! chrec_fold_multiply (integer_type_node, CHREC_RIGHT
(op1),
!
integer_minus_one_node));
case EXPONENTIAL_CHREC:
return chrec_fold_plus_cst_expo (code, type, op0, op1);
--- 992,1000 ----
return build_polynomial_chrec
(CHREC_VARIABLE (op1),
chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
! chrec_fold_multiply (type, CHREC_RIGHT (op1),
! convert (type,
!
integer_minus_one_node)));
case EXPONENTIAL_CHREC:
return chrec_fold_plus_cst_expo (code, type, op0, op1);
*************** chrec_fold_minus (tree type,
*** 1066,1071 ****
--- 1070,1090 ----
return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
}
+ /* Fold the negation of a two chrec. */
+
+ tree
+ chrec_fold_negate (tree type, tree op0)
+ {
+ if (integer_zerop (op0)
+ || (TREE_CODE (op0) == INTERVAL_CHREC
+ && integer_zerop (CHREC_LOW (op0))
+ && integer_zerop (CHREC_UP (op0))))
+ return op0;
+
+ return chrec_fold_plus_1 (MINUS_EXPR, type,
+ convert (type, integer_zero_node),
+ op0);
+ }
/* Fold the multiplication of two chrecs. */
tree
*************** chrec_fold_multiply (tree type,
*** 1216,1223 ****
}
}
}
-
-
/* Operations. */
--- 1235,1240 ----
*************** chrec_merge (tree chrec1,
*** 1662,1668 ****
return chrec2;
if (chrec2 == chrec_not_analyzed_yet)
return chrec1;
!
switch (TREE_CODE (chrec1))
{
case INTEGER_CST:
--- 1679,1688 ----
return chrec2;
if (chrec2 == chrec_not_analyzed_yet)
return chrec1;
!
! if (operand_equal_p (chrec1, chrec2, 0))
! return chrec1;
!
switch (TREE_CODE (chrec1))
{
case INTEGER_CST:
*************** no_evolution_in_loop_p (tree chrec,
*** 1875,1881 ****
if (chrec == chrec_not_analyzed_yet)
return true;
!
scev = evolution_function_in_loop_num (chrec, loop_num);
return (TREE_CODE (scev) != POLYNOMIAL_CHREC
&& TREE_CODE (scev) != EXPONENTIAL_CHREC);
--- 1895,1903 ----
if (chrec == chrec_not_analyzed_yet)
return true;
! if (chrec == chrec_top)
! return false;
!
scev = evolution_function_in_loop_num (chrec, loop_num);
return (TREE_CODE (scev) != POLYNOMIAL_CHREC
&& TREE_CODE (scev) != EXPONENTIAL_CHREC);
*************** chrec_convert (tree type,
*** 2823,2831 ****
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
case EXPONENTIAL_CHREC:
! return chrec_replace_initial_condition
! (chrec, chrec_convert (type, initial_condition (chrec)));
case PEELED_CHREC:
return build_peeled_chrec
--- 2845,2862 ----
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
+ return build_polynomial_chrec (CHREC_VARIABLE (chrec),
+ chrec_convert (type,
+
CHREC_LEFT (chrec)),
+ chrec_convert (type,
+
CHREC_RIGHT (chrec)));
+
case EXPONENTIAL_CHREC:
! return build_exponential_chrec (CHREC_VARIABLE (chrec),
! chrec_convert (type,
!
CHREC_LEFT (chrec)),
! chrec_convert (type,
!
CHREC_RIGHT (chrec)));
case PEELED_CHREC:
return build_peeled_chrec
*************** chrec_type (tree chrec)
*** 2851,2870 ****
if (automatically_generated_chrec_p (chrec))
return NULL_TREE;
! switch (TREE_CODE (chrec))
! {
! case POLYNOMIAL_CHREC:
! case EXPONENTIAL_CHREC:
! return chrec_type (initial_condition (chrec));
!
! case PEELED_CHREC:
! return chrec_type (CHREC_LEFT (chrec));
!
! case INTERVAL_CHREC:
! return chrec_type (CHREC_LOW (chrec));
!
! default:
! return TREE_TYPE (chrec);
! }
}
--- 2882,2887 ----
if (automatically_generated_chrec_p (chrec))
return NULL_TREE;
! return TREE_TYPE (chrec);
}
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.h,v
retrieving revision 1.1.2.8
diff -c -3 -p -r1.1.2.8 tree-chrec.h
*** tree-chrec.h 30 Mar 2004 17:45:52 -0000 1.1.2.8
--- tree-chrec.h 30 Mar 2004 20:53:35 -0000
*************** static inline tree build_peeled_chrec (u
*** 78,83 ****
--- 78,84 ----
/* Chrec folding functions. */
extern tree chrec_fold_plus (tree, tree, tree);
extern tree chrec_fold_minus (tree, tree, tree);
+ extern tree chrec_fold_negate (tree, tree);
extern tree chrec_fold_multiply (tree, tree, tree);
extern tree chrec_convert (tree, tree);
extern tree chrec_type (tree);
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-data-ref.c,v
retrieving revision 1.1.2.13
diff -c -3 -p -r1.1.2.13 tree-data-ref.c
*** tree-data-ref.c 30 Mar 2004 17:45:52 -0000 1.1.2.13
--- tree-data-ref.c 30 Mar 2004 20:53:35 -0000
*************** Software Foundation, 59 Temple Place - S
*** 97,103 ****
#include "tree-pass.h"
#include "lambda.h"
! static tree analyze_array_indexes (unsigned, varray_type, tree);
static bool access_functions_are_affine_or_constant_p (struct
data_reference *);
static struct data_dependence_relation *
--- 97,103 ----
#include "tree-pass.h"
#include "lambda.h"
! static tree analyze_array_indexes (struct loop *, varray_type, tree);
static bool access_functions_are_affine_or_constant_p (struct
data_reference *);
static struct data_dependence_relation *
*************** access_functions_are_affine_or_constant_
*** 344,350 ****
"A[i]". The function returns the base name: "A". */
static tree
! analyze_array_indexes (unsigned loop_nb,
varray_type access_fns,
tree ref)
{
--- 344,350 ----
"A[i]". The function returns the base name: "A". */
static tree
! analyze_array_indexes (struct loop *loop,
varray_type access_fns,
tree ref)
{
*************** analyze_array_indexes (unsigned loop_nb,
*** 359,371 ****
the computation of access functions that are of no interest for
the optimizers. */
access_fn = instantiate_parameters
! (loop_nb, analyze_scalar_evolution (loop_nb, opnd1));
VARRAY_PUSH_TREE (access_fns, access_fn);
/* Recursively record other array access functions. */
if (TREE_CODE (opnd0) == ARRAY_REF)
! return analyze_array_indexes (loop_nb, access_fns, opnd0);
/* Return the base name of the data access. */
else
--- 359,371 ----
the computation of access functions that are of no interest for
the optimizers. */
access_fn = instantiate_parameters
! (loop, analyze_scalar_evolution (loop, opnd1));
VARRAY_PUSH_TREE (access_fns, access_fn);
/* Recursively record other array access functions. */
if (TREE_CODE (opnd0) == ARRAY_REF)
! return analyze_array_indexes (loop, access_fns, opnd0);
/* Return the base name of the data access. */
else
*************** analyze_array (tree stmt,
*** 396,402 ****
DR_REF (res) = ref;
VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
DR_BASE_NAME (res) = analyze_array_indexes
! (loop_num (loop_of_stmt (stmt)), DR_ACCESS_FNS (res), ref);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
--- 396,402 ----
DR_REF (res) = ref;
VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
DR_BASE_NAME (res) = analyze_array_indexes
! (loop_of_stmt (stmt), DR_ACCESS_FNS (res), ref);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
Index: tree-elim-check.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-elim-check.c,v
retrieving revision 1.1.2.4
diff -c -3 -p -r1.1.2.4 tree-elim-check.c
*** tree-elim-check.c 30 Mar 2004 17:45:52 -0000 1.1.2.4
--- tree-elim-check.c 30 Mar 2004 20:53:35 -0000
*************** try_eliminate_check (tree cond)
*** 207,215 ****
bool value;
tree test, opnd0, opnd1;
tree chrec0, chrec1;
! unsigned loop_nb = loop_num (loop_of_stmt (cond));
! tree nb_iters = number_of_iterations_in_loop (loop_of_stmt (cond));
!
if (automatically_generated_chrec_p (nb_iters))
return;
--- 207,215 ----
bool value;
tree test, opnd0, opnd1;
tree chrec0, chrec1;
! struct loop *loop = loop_of_stmt (cond);
! tree nb_iters = number_of_iterations_in_loop (loop);
!
if (automatically_generated_chrec_p (nb_iters))
return;
*************** try_eliminate_check (tree cond)
*** 227,242 ****
case SSA_NAME:
/* Matched "if (opnd0)" ie, "if (opnd0 != 0)". */
opnd0 = test;
! chrec0 = analyze_scalar_evolution (loop_nb, opnd0);
if (chrec_contains_undetermined (chrec0))
break;
! chrec0 = instantiate_parameters (loop_nb, chrec0);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (test = ");
print_generic_expr (dump_file, test, 0);
! fprintf (dump_file, ")\n (loop_nb = %d)\n", loop_nb);
fprintf (dump_file, " (nb_iters = ");
print_generic_expr (dump_file, nb_iters, 0);
fprintf (dump_file, ")\n (chrec0 = ");
--- 227,242 ----
case SSA_NAME:
/* Matched "if (opnd0)" ie, "if (opnd0 != 0)". */
opnd0 = test;
! chrec0 = analyze_scalar_evolution (loop, opnd0);
if (chrec_contains_undetermined (chrec0))
break;
! chrec0 = instantiate_parameters (loop, chrec0);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (test = ");
print_generic_expr (dump_file, test, 0);
! fprintf (dump_file, ")\n (loop_nb = %d)\n", loop->num);
fprintf (dump_file, " (nb_iters = ");
print_generic_expr (dump_file, nb_iters, 0);
fprintf (dump_file, ")\n (chrec0 = ");
*************** try_eliminate_check (tree cond)
*** 244,250 ****
fprintf (dump_file, ")\n");
}
! if (prove_truth_value (NE_EXPR, loop_nb, chrec0, integer_zero_node,
nb_iters, &value))
remove_redundant_check (cond, value);
break;
--- 244,250 ----
fprintf (dump_file, ")\n");
}
! if (prove_truth_value (NE_EXPR, loop->num, chrec0,
integer_zero_node,
nb_iters, &value))
remove_redundant_check (cond, value);
break;
*************** try_eliminate_check (tree cond)
*** 257,278 ****
case NE_EXPR:
opnd0 = TREE_OPERAND (test, 0);
opnd1 = TREE_OPERAND (test, 1);
! chrec0 = analyze_scalar_evolution (loop_nb, opnd0);
if (chrec_contains_undetermined (chrec0))
break;
! chrec1 = analyze_scalar_evolution (loop_nb, opnd1);
if (chrec_contains_undetermined (chrec1))
break;
! chrec0 = instantiate_parameters (loop_nb, chrec0);
! chrec1 = instantiate_parameters (loop_nb, chrec1);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (test = ");
print_generic_expr (dump_file, test, 0);
! fprintf (dump_file, ")\n (loop_nb = %d)\n", loop_nb);
fprintf (dump_file, " (nb_iters = ");
print_generic_expr (dump_file, nb_iters, 0);
fprintf (dump_file, ")\n (chrec0 = ");
--- 257,278 ----
case NE_EXPR:
opnd0 = TREE_OPERAND (test, 0);
opnd1 = TREE_OPERAND (test, 1);
! chrec0 = analyze_scalar_evolution (loop, opnd0);
if (chrec_contains_undetermined (chrec0))
break;
! chrec1 = analyze_scalar_evolution (loop, opnd1);
if (chrec_contains_undetermined (chrec1))
break;
! chrec0 = instantiate_parameters (loop, chrec0);
! chrec1 = instantiate_parameters (loop, chrec1);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (test = ");
print_generic_expr (dump_file, test, 0);
! fprintf (dump_file, ")\n (loop_nb = %d)\n", loop->num);
fprintf (dump_file, " (nb_iters = ");
print_generic_expr (dump_file, nb_iters, 0);
fprintf (dump_file, ")\n (chrec0 = ");
*************** try_eliminate_check (tree cond)
*** 282,288 ****
fprintf (dump_file, ")\n");
}
! if (prove_truth_value (TREE_CODE (test), loop_nb, chrec0, chrec1,
nb_iters, &value))
remove_redundant_check (cond, value);
break;
--- 282,288 ----
fprintf (dump_file, ")\n");
}
! if (prove_truth_value (TREE_CODE (test), loop->num, chrec0, chrec1,
nb_iters, &value))
remove_redundant_check (cond, value);
break;
Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-phinodes.c,v
retrieving revision 1.1.2.8.2.2
diff -c -3 -p -r1.1.2.8.2.2 tree-phinodes.c
*** tree-phinodes.c 21 Feb 2004 23:10:02 -0000
1.1.2.8.2.2
--- tree-phinodes.c 30 Mar 2004 20:53:35 -0000
*************** create_phi_node (tree var, basic_block b
*** 297,303 ****
/* This is a new phi node, so note that is has not yet been
rewritten. */
PHI_REWRITTEN (phi) = 0;
- PHI_MARKED (phi) = 0;
/* Add the new PHI node to the list of PHI nodes for block BB. */
TREE_CHAIN (phi) = phi_nodes (bb);
--- 297,302 ----
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.26
diff -c -3 -p -r1.1.2.26 tree-scalar-evolution.c
*** tree-scalar-evolution.c 30 Mar 2004 17:45:52 -0000
1.1.2.26
--- tree-scalar-evolution.c 30 Mar 2004 20:53:35 -0000
*************** Software Foundation, 59 Temple Place - S
*** 267,286 ****
static bool loop_phi_node_p (tree);
!
! static void set_scalar_evolution (tree, tree);
! static void set_scalar_evolution_outer_value (tree, tree);
!
! static bool follow_ssa_edge_in_rhs (unsigned, tree, tree, tree *);
! static bool follow_ssa_edge_in_condition_phi (unsigned, tree, tree, tree
*);
! static bool follow_ssa_edge_inner_loop_phi (unsigned, tree, tree, tree
*);
! static bool follow_ssa_edge (unsigned, tree, tree, tree *);
! static tree analyze_evolution_in_loop (tree, tree);
! static tree analyze_initial_condition (tree);
! static tree interpret_loop_phi (unsigned, tree);
! static tree interpret_condition_phi (unsigned, tree);
! static tree interpret_rhs_modify_expr (unsigned, tree);
!
/* The following trees are unique elements. Thus the comparison of
another element to these elements should be done on the pointer to
--- 267,291 ----
static bool loop_phi_node_p (tree);
! static bool follow_ssa_edge_in_rhs (struct loop *loop, tree, tree, tree
*);
! static bool follow_ssa_edge_in_condition_phi (struct loop *loop, tree,
tree, tree *);
! static bool follow_ssa_edge_inner_loop_phi (struct loop *loop, tree,
tree, tree *);
! static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
! static tree analyze_evolution_in_loop (tree, tree);
! static tree analyze_initial_condition (tree);
! static tree interpret_loop_phi (struct loop *loop, tree);
! static tree interpret_condition_phi (struct loop *loop, tree);
! static tree interpret_rhs_modify_expr (struct loop *loop, tree, tree);
!
! /* The cached information about a ssa name VAR, claiming that inside
LOOP,
! the value of VAR can be expressed as CHREC. */
!
! struct scev_info_str
! {
! tree var;
! struct loop *loop;
! tree chrec;
! };
/* The following trees are unique elements. Thus the comparison of
another element to these elements should be done on the pointer to
*************** tree chrec_top;
*** 298,307 ****
tree chrec_bot;
static struct loops *current_loops;
! static varray_type *scalar_evolution_info;
! static varray_type *already_instantiated;
! static varray_type scalar_evolution_info_st;
! static varray_type already_instantiated_st;
/* Statistics counters. */
static unsigned stats_nb_chrecs = 0;
--- 303,310 ----
tree chrec_bot;
static struct loops *current_loops;
! static varray_type scalar_evolution_info;
! static varray_type already_instantiated;
/* Statistics counters. */
static unsigned stats_nb_chrecs = 0;
*************** static unsigned stats_nb_undetermined =
*** 318,391 ****
bool dd_info_available;
! /* Loop related functions. */
!
! static inline bool stmt_is_in_loop (tree, unsigned);
!
! /* Determines whether STMT is in loop LOOP_NB. */
!
! static inline bool
! stmt_is_in_loop (tree stmt, unsigned loop_nb)
{
! return flow_bb_inside_loop_p (loop_from_num (current_loops, loop_nb),
! bb_for_stmt (stmt));
! }
!
! /* Determines whether STMT is not contained by the loop LOOP_NB. */
!
! static inline bool
! stmt_is_not_in_loop (tree stmt, unsigned loop_nb)
! {
! return !stmt_is_in_loop (stmt, loop_nb);
! }
!
! /* Determines whether loop A is contained in loop B. */
!
! static bool
! loop_is_included_in (unsigned a, unsigned b)
! {
! if (a == b)
! return true;
! return flow_loop_nested_p (loop_from_num (current_loops, b),
! loop_from_num (current_loops,
a));
! }
!
! /* Determines whether loop A is strictly contained in loop B. */
!
! static bool
! loop_is_strictly_included_in (unsigned a, unsigned b)
! {
! if (a == b)
! return false;
! return flow_loop_nested_p (loop_from_num (current_loops, b),
! loop_from_num (current_loops,
a));
}
! /* Get the index corresponding to VAR in the current loop nest. If
! it's the first time we ask for this VAR, then conservatively insert
! CHREC_TOP for this VAR and return its index. */
! static struct scev_info_str *
! find_var_scev_info (tree var)
{
unsigned int i;
struct scev_info_str *res;
! for (i = 0; i < VARRAY_ACTIVE_SIZE (*scalar_evolution_info); i++)
{
! res = VARRAY_GENERIC_PTR (*scalar_evolution_info, i);
! if (MI_VAR (res) == var)
! return res;
}
/* The variable is not in the table, create a new entry for it. */
! res = new_scev_info_str (var);
! VARRAY_PUSH_GENERIC_PTR (*scalar_evolution_info, res);
! return res;
}
--- 321,363 ----
bool dd_info_available;
+ /* Constructs a new SCEV_INFO_STR structure. */
! static inline struct scev_info_str *
! new_scev_info_str (struct loop *loop, tree var)
{
! struct scev_info_str *res;
! res = ggc_alloc (sizeof (struct scev_info_str));
! res->var = var;
! res->loop = loop;
! res->chrec = chrec_not_analyzed_yet;
! return res;
}
! /* 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_analysed_yet for this VAR and return its index. */
! static tree *
! find_var_scev_info (struct loop *loop, tree var)
{
unsigned int i;
struct scev_info_str *res;
! for (i = 0; i < VARRAY_ACTIVE_SIZE (scalar_evolution_info); i++)
{
! res = VARRAY_GENERIC_PTR (scalar_evolution_info, i);
! if (res->var == var && res->loop == loop)
! return &res->chrec;
}
/* The variable is not in the table, create a new entry for it. */
! res = new_scev_info_str (loop, var);
! VARRAY_PUSH_GENERIC_PTR (scalar_evolution_info, res);
! return &res->chrec;
}
*************** loop_phi_node_p (tree phi)
*** 401,507 ****
/* The implementation of this function is based on the following
property: "all the loop-phi-nodes of a loop are contained in the
loop's header basic block". */
! tree it;
!
! for (it = phi_nodes (loop_header (loop_of_stmt (phi)));
! it != NULL_TREE;
! it = TREE_CHAIN (it))
! if (it == phi)
! {
! int i;
! bool found_initial_condition = false;
! bool found_update = false;
!
! /* This is a loop-phi-node only if one of its edges is an
! initial condition and one other edge points to the body of
! the loop, or in other words, an updated definition. */
! for (i = 0; i < PHI_NUM_ARGS (phi); i++)
! {
! tree upper_chain;
! tree branch = PHI_ARG_DEF (phi, i);
!
! switch (TREE_CODE (branch))
! {
! case SSA_NAME:
! upper_chain = SSA_NAME_DEF_STMT (branch);
!
! /* When the phi node has a NOP_EXPR or a NULL_TREE
! argument, or if it is not defined in a loop
! contained in the loop where the phi is defined,
! then this argument is the initial condition.
*/
! if (upper_chain == NULL_TREE
! || TREE_CODE (upper_chain) == NOP_EXPR
! || !loop_is_included_in
! (loop_num (loop_of_stmt (upper_chain)),
! loop_num (loop_of_stmt (phi))))
! {
! if (found_update)
! return true;
! else
! found_initial_condition = true;
! }
!
! /* Otherwise, the branch is oriented to the loop's
! body. */
! else
! {
! if (found_initial_condition)
! return true;
! else
! found_update = true;
! }
! break;
!
! default:
! if (found_update)
! return true;
! else
! found_initial_condition = true;
! break;
! }
! }
! }
!
! return false;
}
! /* Select the evolution function in the current LOOP_NB and in the
outer containing loops. */
static tree
! select_outer_and_current_evolutions (unsigned loop_nb,
! tree chrec)
{
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
! if (loop_is_included_in (loop_nb, CHREC_VARIABLE (chrec)))
return build_polynomial_chrec
(CHREC_VARIABLE (chrec),
! select_outer_and_current_evolutions (loop_nb, CHREC_LEFT
(chrec)),
! select_outer_and_current_evolutions (loop_nb, CHREC_RIGHT
(chrec)));
else
! return select_outer_and_current_evolutions
! (loop_nb, CHREC_LEFT (chrec));
!
case EXPONENTIAL_CHREC:
! if (loop_is_included_in (loop_nb, CHREC_VARIABLE (chrec)))
return build_exponential_chrec
(CHREC_VARIABLE (chrec),
! select_outer_and_current_evolutions (loop_nb, CHREC_LEFT
(chrec)),
! select_outer_and_current_evolutions (loop_nb, CHREC_RIGHT
(chrec)));
else
! return select_outer_and_current_evolutions
! (loop_nb, CHREC_LEFT (chrec));
default:
return chrec;
}
}
! /* Compute the overall effect of a loop on a variable.
1. compute the number of iterations in the loop,
2. compute the value of the variable after crossing the loop.
--- 373,420 ----
/* The implementation of this function is based on the following
property: "all the loop-phi-nodes of a loop are contained in the
loop's header basic block". */
!
! return loop_of_stmt (phi)->header == bb_for_stmt (phi);
}
! /* Select the evolution function in the current LOOP and in the
outer containing loops. */
static tree
! select_outer_and_current_evolutions (struct loop *loop, tree chrec)
{
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
! if (flow_loop_nested_p (loop_from_num (current_loops,
!
CHREC_VARIABLE (chrec)),
! loop))
return build_polynomial_chrec
(CHREC_VARIABLE (chrec),
! select_outer_and_current_evolutions (loop, CHREC_LEFT
(chrec)),
! select_outer_and_current_evolutions (loop, CHREC_RIGHT
(chrec)));
else
! return select_outer_and_current_evolutions (loop, CHREC_LEFT
(chrec));
!
case EXPONENTIAL_CHREC:
! if (flow_loop_nested_p (loop_from_num (current_loops,
!
CHREC_VARIABLE (chrec)),
! loop))
return build_exponential_chrec
(CHREC_VARIABLE (chrec),
! select_outer_and_current_evolutions (loop, CHREC_LEFT
(chrec)),
! select_outer_and_current_evolutions (loop, CHREC_RIGHT
(chrec)));
else
! return select_outer_and_current_evolutions (loop, CHREC_LEFT
(chrec));
default:
return chrec;
}
}
! /* Compute the overall effect of a LOOP on a variable.
1. compute the number of iterations in the loop,
2. compute the value of the variable after crossing the loop.
*************** select_outer_and_current_evolutions (uns
*** 519,536 ****
*/
static tree
! compute_overall_effect_of_inner_loop (tree version)
{
tree res;
! tree nb_iter;
! struct loop *loop = loop_of_stmt (SSA_NAME_DEF_STMT (version));
! unsigned loop_nb;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(compute_overall_effect_of_inner_loop \n");
!
nb_iter = number_of_iterations_in_loop (loop);
!
/* When the number of iterations is not known, set the evolution to
chrec_top. As an example, consider the following loop:
--- 432,452 ----
*/
static tree
! compute_overall_effect_of_inner_loop (struct loop *loop, tree version)
{
tree res;
! tree nb_iter, evolution_fn;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(compute_overall_effect_of_inner_loop \n");
!
! evolution_fn = analyze_scalar_evolution (loop, version);
nb_iter = number_of_iterations_in_loop (loop);
!
! /* If the variable is an invariant, there is nothing to do. */
! if (no_evolution_in_loop_p (evolution_fn, loop->num))
! res = evolution_fn;
!
/* When the number of iterations is not known, set the evolution to
chrec_top. As an example, consider the following loop:
*************** compute_overall_effect_of_inner_loop (tr
*** 550,603 ****
| i = i + 1
| i = i + chrec_top
| endloop
! */
! if (nb_iter == chrec_top)
res = chrec_top;
else
{
! /* An example: given the evolution
! "{{22, +, 4}_1, +, [1,3]}_2",
!
! and the fact that the loop 2 runs exactly 6 times, the
! overall effect is obtained by evaluating:
!
! "({{22, +, 4}_1, +, [1,3]}_2 - initial_conditions) (2, 6)"
! "{{0, +, 4}_1, +, [1,3]}_2 (2, 6)"
! "[6,18]".
!
! That means that the effect of the inner loop 2 in the outer
! loop 1 is that of adding an integer between 6 and 18 every
! time the loop 1 is executed. Consequently, the evolution
! function is: "{{22, +, [10,22]}_1, +, [1,3]}_2". */
! tree evolution_fn, overall_effect;
!
! /* Since the exit condition is on the end of the loop (after the
! loop headers copy), we have to adjust the number of
! iterations to "nb_iter - 1". */
! nb_iter = chrec_fold_minus
! (chrec_type (nb_iter), nb_iter, integer_one_node);
!
! loop_nb = loop_num (loop);
! evolution_fn = analyze_scalar_evolution (loop_nb, version);
! overall_effect = chrec_apply
! (loop_nb,
! update_initial_condition_to_origin
! (evolution_function_in_loop_num (evolution_fn, loop_nb)),
! nb_iter);
! res = chrec_fold_plus
! (chrec_type (evolution_fn), evolution_fn, overall_effect);
!
! /* Select only the evolution in the parent loop, since we're not
! interested in having the details of the evolution in the
! inner loops, when looking at the evolution in the outer
! loop. */
! res = select_outer_and_current_evolutions
! (loop_num (outer_loop (loop)), res);
}
- set_scalar_evolution_outer_value (version, res);
-
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
return res;
--- 466,490 ----
| i = i + 1
| i = i + chrec_top
| endloop
! */
!
! else if (nb_iter == chrec_top)
res = chrec_top;
else
{
! /* Number of iterations is off by one (the ssa name we analyze must
be
! defined before the exit). */
! nb_iter = chrec_fold_minus (chrec_type (nb_iter),
! nb_iter,
! convert (chrec_type
(nb_iter),
!
integer_one_node));
!
! /* evolution_fn is the evolution function in LOOP. Get its value
in the
! nb_iter-th iteration. */
! res = chrec_apply (loop->num, evolution_fn, nb_iter);
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
return res;
*************** compute_overall_effect_of_inner_loop (tr
*** 607,691 ****
/* The following section constitutes the interface with the chrecs. */
! /* Determine whether the CHREC is positive. If the expression cannot
! be statically analyzed, return false, otherwise set the answer into
VALUE. */
bool
chrec_is_positive (tree chrec, bool *value)
{
bool value0, value1;
switch (TREE_CODE (chrec))
{
case INTERVAL_CHREC:
! return chrec_is_positive (CHREC_LOW (chrec), value);
!
case POLYNOMIAL_CHREC:
case EXPONENTIAL_CHREC:
if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
|| !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
return false;
!
! if (value0 == true && value1 == true)
! {
! *value = true;
! return true;
! }
! else if (value0 == false && value1 == false)
{
! *value = false;
return true;
}
! else
! {
! /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
! and the proof consists in showing that the sign never
! changes during the execution of the loop, from 0 to
! loop_nb_iterations (). */
! if (evolution_function_is_affine_p (chrec))
! {
! bool value2;
! tree end_value;
! tree nb_iter;
!
! nb_iter = number_of_iterations_in_loop
! (loop_from_num (current_loops, CHREC_VARIABLE
(chrec)));
!
! nb_iter = chrec_fold_minus
! (chrec_type (nb_iter), nb_iter, build_int_2 (2,
0));
!
! if (chrec_contains_undetermined (nb_iter))
! return false;
!
! end_value = chrec_apply
! (CHREC_VARIABLE (chrec), chrec, nb_iter);
!
! if (!chrec_is_positive (end_value, &value2))
! return false;
! if (value0 == true && value2 == true)
! {
! *value = true;
! return true;
! }
! else if (value0 == false && value2 == false)
! {
! *value = false;
! return true;
! }
! else
! return false;
! }
!
! return false;
! }
case INTEGER_CST:
*value = (tree_int_cst_sgn (chrec) == 1);
return true;
- case PLUS_EXPR:
default:
return false;
}
--- 494,568 ----
/* The following section constitutes the interface with the chrecs. */
! /* Determine whether the CHREC is always positive/negative. If the
expression
! cannot be statically analyzed, return false, otherwise set the answer
into
VALUE. */
bool
chrec_is_positive (tree chrec, bool *value)
{
bool value0, value1;
+ bool value2;
+ tree end_value;
+ tree nb_iter;
switch (TREE_CODE (chrec))
{
case INTERVAL_CHREC:
! if (!chrec_is_positive (CHREC_LOW (chrec), &value0)
! || !chrec_is_positive (CHREC_UP (chrec), &value1))
! return false;
!
! *value = value0;
! return value0 == value1;
!
case POLYNOMIAL_CHREC:
case EXPONENTIAL_CHREC:
if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
|| !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
return false;
!
! /* FIXME -- overflows. */
! if (value0 == value1)
{
! *value = value0;
return true;
}
!
! /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
! and the proof consists in showing that the sign never
! changes during the execution of the loop, from 0 to
! loop_nb_iterations (). */
! if (!evolution_function_is_affine_p (chrec))
! return false;
!
! nb_iter = number_of_iterations_in_loop
! (loop_from_num (current_loops, CHREC_VARIABLE (chrec)));
! nb_iter = chrec_fold_minus
! (chrec_type (nb_iter), nb_iter,
! convert (chrec_type (nb_iter), integer_one_node));
!
! #if 0
! /* TODO -- If the test is after the exit, we may decrease the
number of
! iterations by one. */
! if (after_exit)
! nb_iter = chrec_fold_minus
! (chrec_type (nb_iter), nb_iter,
! convert (chrec_type (nb_iter),
integer_one_node));
! #endif
!
! end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
! if (!chrec_is_positive (end_value, &value2))
! return false;
!
! *value = value0;
! return value0 == value1;
case INTEGER_CST:
*value = (tree_int_cst_sgn (chrec) == 1);
return true;
default:
return false;
}
*************** set_scev_keep_symbolic (tree def,
*** 719,731 ****
}
}
! /* Associate CHREC to SCALAR. */
static void
! set_scalar_evolution (tree scalar,
! tree chrec)
{
! struct scev_info_str *scalar_info = find_var_scev_info (scalar);
chrec = set_scev_keep_symbolic (scalar, chrec);
if (dump_file && (dump_flags & TDF_DETAILS))
--- 596,607 ----
}
}
! /* Associate CHREC to SCALAR in LOOP. */
static void
! set_scalar_evolution (struct loop *loop, tree scalar, tree chrec)
{
! tree *scalar_info = find_var_scev_info (loop, scalar);
chrec = set_scev_keep_symbolic (scalar, chrec);
if (dump_file && (dump_flags & TDF_DETAILS))
*************** set_scalar_evolution (tree scalar,
*** 738,786 ****
fprintf (dump_file, "))\n");
}
! MI_INNER_LOOPS_CHREC (scalar_info) = chrec;
}
! /* Associate the value CHREC, that is exposed to the statements after
! the loop, to SCALAR. */
!
! static void
! set_scalar_evolution_outer_value (tree scalar,
! tree chrec)
! {
! struct scev_info_str *scalar_info = find_var_scev_info (scalar);
! chrec = set_scev_keep_symbolic (scalar, chrec);
!
! if (dump_file && (dump_flags & TDF_DETAILS))
! {
! fprintf (dump_file, "(set_scalar_evolution_outer_value \n");
! fprintf (dump_file, " (scalar = ");
! print_generic_expr (dump_file, scalar, 0);
! fprintf (dump_file, ")\n (scalar_evolution = ");
! print_generic_expr (dump_file, chrec, 0);
! fprintf (dump_file, "))\n");
! }
!
! MI_OUTER_LOOPS_CHREC (scalar_info) = chrec;
! }
!
! /* Retrieve the chrec associated to SCALAR in the loop LOOP_NB. LOOP_NB
! determines the returned value, following the loop inclusion: if
! LOOP_NB is contained in loop_of_stmt (scalar), then the inner value is
! returned, otherwise it's the value that is viewed by a statement
! after the loop. */
static tree
! get_scalar_evolution (unsigned loop_nb,
! tree scalar)
{
! struct scev_info_str *scalar_info;
! tree res = NULL_TREE;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(get_scalar_evolution \n");
! fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
fprintf (dump_file, " (scalar = ");
print_generic_expr (dump_file, scalar, 0);
fprintf (dump_file, ")\n");
--- 614,633 ----
fprintf (dump_file, "))\n");
}
! *scalar_info = chrec;
}
! /* Retrieve the chrec associated to SCALAR in the LOOP. */
static tree
! get_scalar_evolution (struct loop *loop, tree scalar)
{
! tree res;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(get_scalar_evolution \n");
! fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
fprintf (dump_file, " (scalar = ");
print_generic_expr (dump_file, scalar, 0);
fprintf (dump_file, ")\n");
*************** get_scalar_evolution (unsigned loop_nb,
*** 789,813 ****
switch (TREE_CODE (scalar))
{
case SSA_NAME:
! scalar_info = find_var_scev_info (scalar);
!
! if (MI_INNER_LOOPS_CHREC (scalar_info) == chrec_not_analyzed_yet)
! res = chrec_not_analyzed_yet;
!
! else if (MI_INNER_LOOPS_CHREC (scalar_info) == chrec_top)
! res = chrec_top;
!
! else if (loop_is_included_in
! (loop_nb, loop_num (loop_of_stmt (SSA_NAME_DEF_STMT
(scalar)))))
! res = MI_INNER_LOOPS_CHREC (scalar_info);
!
! else
! {
! res = MI_OUTER_LOOPS_CHREC (scalar_info);
!
! if (res == chrec_not_analyzed_yet)
! res = compute_overall_effect_of_inner_loop (scalar);
! }
break;
case VAR_DECL:
--- 636,642 ----
switch (TREE_CODE (scalar))
{
case SSA_NAME:
! res = *find_var_scev_info (loop, scalar);
break;
case VAR_DECL:
*************** add_expr_to_loop_evolution (unsigned loo
*** 984,994 ****
add_expr_to_loop_evolution (loop_num,
CHREC_LEFT
(chrec_before),
code, to_add),
- /* testsuite/.../ssa-chrec-38.c
- Do not modify the CHREC_RIGHT part: this part is a fixed
part
- completely determined by the evolution of other scalar
variables.
- The same comment is included in the
no_evolution_in_loop_p
- function. */
CHREC_RIGHT (chrec_before));
case EXPONENTIAL_CHREC:
--- 813,818 ----
*************** add_expr_to_loop_evolution (unsigned loo
*** 1006,1015 ****
add_expr_to_loop_evolution (loop_num,
CHREC_LEFT
(chrec_before),
code, to_add),
- /* Do not modify the CHREC_RIGHT part: this part is a fixed
part
- completely determined by the evolution of other scalar
variables.
- The same comment is included in the
no_evolution_in_loop_p
- function. */
CHREC_RIGHT (chrec_before));
default:
--- 830,835 ----
*************** add_to_evolution (unsigned loop_nb,
*** 1253,1259 ****
{
if (code == MINUS_EXPR)
to_add = chrec_fold_multiply
! (chrec_type (to_add), to_add, integer_minus_one_node);
/* testsuite/.../ssa-chrec-39.c. */
res = build_polynomial_evolution_in_loop
--- 1073,1080 ----
{
if (code == MINUS_EXPR)
to_add = chrec_fold_multiply
! (chrec_type (to_add), to_add,
! convert (chrec_type (to_add), integer_minus_one_node));
/* testsuite/.../ssa-chrec-39.c. */
res = build_polynomial_evolution_in_loop
*************** draw_tree_cfg (void)
*** 2234,2240 ****
/* Follow the ssa edge into the right hand side of an assignment. */
static bool
! follow_ssa_edge_in_rhs (unsigned loop_nb,
tree rhs,
tree halting_phi,
tree *evolution_of_loop)
--- 2055,2061 ----
/* Follow the ssa edge into the right hand side of an assignment. */
static bool
! follow_ssa_edge_in_rhs (struct loop *loop,
tree rhs,
tree halting_phi,
tree *evolution_of_loop)
*************** follow_ssa_edge_in_rhs (unsigned loop_nb
*** 2260,2266 ****
case SSA_NAME:
/* This assignment is under the form: "a_1 = b_2". */
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs), halting_phi,
evolution_of_loop);
break;
case PLUS_EXPR:
--- 2081,2087 ----
case SSA_NAME:
/* This assignment is under the form: "a_1 = b_2". */
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs), halting_phi,
evolution_of_loop);
break;
case PLUS_EXPR:
*************** follow_ssa_edge_in_rhs (unsigned loop_nb
*** 2275,2298 ****
/* Match an assignment under the form:
"a = b + c". */
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop_nb,
chrec_convert (type_rhs, *evolution_of_loop),
PLUS_EXPR, rhs1);
else
{
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs1),
halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop_nb,
chrec_convert (type_rhs,
*evolution_of_loop),
PLUS_EXPR, rhs0);
}
--- 2096,2119 ----
/* Match an assignment under the form:
"a = b + c". */
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop->num,
chrec_convert (type_rhs, *evolution_of_loop),
PLUS_EXPR, rhs1);
else
{
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop->num,
chrec_convert (type_rhs,
*evolution_of_loop),
PLUS_EXPR, rhs0);
}
*************** follow_ssa_edge_in_rhs (unsigned loop_nb
*** 2303,2313 ****
/* Match an assignment under the form:
"a = b + ...". */
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop_nb, chrec_convert (type_rhs,
*evolution_of_loop),
PLUS_EXPR, rhs1);
}
}
--- 2124,2134 ----
/* Match an assignment under the form:
"a = b + ...". */
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop->num, chrec_convert (type_rhs,
*evolution_of_loop),
PLUS_EXPR, rhs1);
}
}
*************** follow_ssa_edge_in_rhs (unsigned loop_nb
*** 2317,2327 ****
/* Match an assignment under the form:
"a = ... + c". */
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop_nb, chrec_convert (type_rhs, *evolution_of_loop),
PLUS_EXPR, rhs0);
}
--- 2138,2148 ----
/* Match an assignment under the form:
"a = ... + c". */
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop->num, chrec_convert (type_rhs,
*evolution_of_loop),
PLUS_EXPR, rhs0);
}
*************** follow_ssa_edge_in_rhs (unsigned loop_nb
*** 2344,2369 ****
/* Match an assignment under the form:
"a = b - c". */
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop_nb, chrec_convert (type_rhs,
*evolution_of_loop),
MINUS_EXPR, rhs1);
else
{
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs1),
halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop_nb,
chrec_fold_multiply (type_rhs,
*evolution_of_loop,
!
integer_minus_one_node),
PLUS_EXPR, rhs0);
}
}
--- 2165,2191 ----
/* Match an assignment under the form:
"a = b - c". */
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop->num, chrec_convert (type_rhs,
*evolution_of_loop),
MINUS_EXPR, rhs1);
else
{
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop->num,
chrec_fold_multiply (type_rhs,
*evolution_of_loop,
! convert
(type_rhs,
!
integer_minus_one_node)),
PLUS_EXPR, rhs0);
}
}
*************** follow_ssa_edge_in_rhs (unsigned loop_nb
*** 2373,2383 ****
/* Match an assignment under the form:
"a = b - ...". */
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop_nb, chrec_convert (type_rhs,
*evolution_of_loop),
MINUS_EXPR, rhs1);
}
}
--- 2195,2205 ----
/* Match an assignment under the form:
"a = b - ...". */
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop->num, chrec_convert (type_rhs,
*evolution_of_loop),
MINUS_EXPR, rhs1);
}
}
*************** follow_ssa_edge_in_rhs (unsigned loop_nb
*** 2387,2400 ****
/* Match an assignment under the form:
"a = ... - c". */
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop_nb,
chrec_fold_multiply (type_rhs,
*evolution_of_loop,
!
integer_minus_one_node),
PLUS_EXPR, rhs0);
}
--- 2209,2222 ----
/* Match an assignment under the form:
"a = ... - c". */
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = add_to_evolution
! (loop->num,
chrec_fold_multiply (type_rhs,
*evolution_of_loop,
! convert (type_rhs,
integer_minus_one_node)),
PLUS_EXPR, rhs0);
}
*************** follow_ssa_edge_in_rhs (unsigned loop_nb
*** 2417,2438 ****
/* Match an assignment under the form:
"a = b * c". */
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
! (loop_nb, *evolution_of_loop, rhs1);
else
{
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs1),
halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
! (loop_nb, *evolution_of_loop, rhs0);
}
}
--- 2239,2260 ----
/* Match an assignment under the form:
"a = b * c". */
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
! (loop->num, *evolution_of_loop, rhs1);
else
{
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
! (loop->num, *evolution_of_loop, rhs0);
}
}
*************** follow_ssa_edge_in_rhs (unsigned loop_nb
*** 2441,2451 ****
/* Match an assignment under the form:
"a = b * ...". */
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
! (loop_nb, *evolution_of_loop, rhs1);
}
}
--- 2263,2273 ----
/* Match an assignment under the form:
"a = b * ...". */
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
! (loop->num, *evolution_of_loop, rhs1);
}
}
*************** follow_ssa_edge_in_rhs (unsigned loop_nb
*** 2454,2464 ****
/* Match an assignment under the form:
"a = ... * c". */
res = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
! (loop_nb, *evolution_of_loop, rhs0);
}
else
--- 2276,2286 ----
/* Match an assignment under the form:
"a = ... * c". */
res = follow_ssa_edge
! (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
evolution_of_loop);
if (res)
*evolution_of_loop = multiply_evolution
! (loop->num, *evolution_of_loop, rhs0);
}
else
*************** follow_ssa_edge_in_rhs (unsigned loop_nb
*** 2477,2563 ****
return res;
}
/* Helper function for one branch of the condition-phi-node. */
static inline bool
follow_ssa_edge_in_condition_phi_branch (int i,
! unsigned
loop_nb,
tree
condition_phi,
tree
halting_phi,
tree
*evolution_of_branch,
tree
init_cond)
{
- bool found_path_to_halting_phi = false;
tree branch = PHI_ARG_DEF (condition_phi, i);
!
! switch (TREE_CODE (branch))
{
- case INTEGER_CST:
- /* This case occurs when one of the condition branches sets
- the variable to a constant: ie. a phi-node like
- "a_2 = PHI <a_7(5), 2(6)>;".
- The testsuite/.../ssa-chrec-17.c exercises this code.
-
- FIXME: This case have to be refined correctly:
- in some cases it is possible to say something better than
- chrec_top, for example using a wrap-around notation. */
- *evolution_of_branch = chrec_top;
- found_path_to_halting_phi = false;
- break;
-
- case SSA_NAME:
*evolution_of_branch = init_cond;
! found_path_to_halting_phi = follow_ssa_edge
! (loop_nb, SSA_NAME_DEF_STMT (branch), halting_phi,
! evolution_of_branch);
! break;
!
! default:
! *evolution_of_branch = chrec_top;
! found_path_to_halting_phi = false;
! break;
}
!
! return found_path_to_halting_phi;
}
/* This function merges the branches of a condition-phi-node in a
loop. */
static bool
! follow_ssa_edge_in_condition_phi (unsigned loop_nb,
tree condition_phi,
tree halting_phi,
tree *evolution_of_loop)
{
- bool res = false;
int i;
tree evolution_of_branch;
! tree init_cond = initial_condition (*evolution_of_loop);
!
! /* Disabled for the moment. */
! return false;
!
! res = follow_ssa_edge_in_condition_phi_branch
! (0, loop_nb, condition_phi, halting_phi, &evolution_of_branch,
init_cond);
!
! /* We pass in the evolution_of_loop the initial condition of the
! variable in the loop, from the analyze_evolution_in_loop. */
! *evolution_of_loop = chrec_replace_initial_condition
! (evolution_of_branch, *evolution_of_loop);
!
for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
{
! bool found_path_to_halting_phi =
follow_ssa_edge_in_condition_phi_branch
! (i, loop_nb, condition_phi, halting_phi, &evolution_of_branch,
! init_cond);
!
! res = res || found_path_to_halting_phi;
! *evolution_of_loop = chrec_merge
! (*evolution_of_loop, evolution_of_branch);
}
! return res;
}
/* Follow an SSA edge in an inner loop. It computes the overall
--- 2299,2389 ----
return res;
}
+ /* Checks whether the I-th argument of a PHI comes from a backedge. */
+
+ static bool
+ backedge_phi_arg_p (tree phi, int i)
+ {
+ edge e = PHI_ARG_EDGE (phi, i);
+
+ /* We would in fact like to test EDGE_DFS_BACK here, but we do not care
+ about updating it anywhere, and this should work as well most of the
+ time. */
+ if (e->flags & EDGE_IRREDUCIBLE_LOOP)
+ return true;
+
+ return false;
+ }
+
/* Helper function for one branch of the condition-phi-node. */
static inline bool
follow_ssa_edge_in_condition_phi_branch (int i,
! struct loop
*loop,
tree
condition_phi,
tree
halting_phi,
tree
*evolution_of_branch,
tree
init_cond)
{
tree branch = PHI_ARG_DEF (condition_phi, i);
! *evolution_of_branch = chrec_top;
!
! /* Do not follow back edges (they must belong to an irreducible loop,
which
! we really do not want to worry about). */
! if (backedge_phi_arg_p (condition_phi, i))
! return false;
!
! if (TREE_CODE (branch) == SSA_NAME)
{
*evolution_of_branch = init_cond;
! return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch),
halting_phi,
! evolution_of_branch);
}
!
! /* This case occurs when one of the condition branches sets
! the variable to a constant: ie. a phi-node like
! "a_2 = PHI <a_7(5), 2(6)>;".
! The testsuite/.../ssa-chrec-17.c exercises this code.
!
! FIXME: This case have to be refined correctly:
! in some cases it is possible to say something better than
! chrec_top, for example using a wrap-around notation. */
! return false;
}
/* This function merges the branches of a condition-phi-node in a
loop. */
static bool
! follow_ssa_edge_in_condition_phi (struct loop *loop,
tree condition_phi,
tree halting_phi,
tree *evolution_of_loop)
{
int i;
+ tree init = *evolution_of_loop;
tree evolution_of_branch;
!
! if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
!
halting_phi,
!
&evolution_of_branch,
!
init))
! return false;
! *evolution_of_loop = evolution_of_branch;
!
for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
{
! if (!follow_ssa_edge_in_condition_phi_branch (i, loop,
condition_phi,
!
halting_phi,
!
&evolution_of_branch,
!
init))
! return false;
!
! *evolution_of_loop = chrec_merge (*evolution_of_loop,
!
evolution_of_branch);
}
! return true;
}
/* Follow an SSA edge in an inner loop. It computes the overall
*************** follow_ssa_edge_in_condition_phi (unsign
*** 2566,2655 ****
considered as a single statement. */
static bool
! follow_ssa_edge_inner_loop_phi (unsigned outer_loop_nb,
tree loop_phi_node,
tree halting_phi,
tree *evolution_of_loop)
{
! tree overall_effect = get_scalar_evolution
! (outer_loop_nb, PHI_RESULT (loop_phi_node));
!
! if (overall_effect == chrec_not_analyzed_yet)
! overall_effect = compute_overall_effect_of_inner_loop
! (PHI_RESULT (loop_phi_node));
!
! return follow_ssa_edge_in_rhs
! (outer_loop_nb, overall_effect, halting_phi, evolution_of_loop);
}
/* Follow an SSA edge from a loop-phi-node to itself, constructing a
path that is analyzed on the return walk. */
static bool
! follow_ssa_edge (unsigned loop_nb,
tree def,
tree halting_phi,
tree *evolution_of_loop)
{
! unsigned def_loop_nb;
! if (def == NULL_TREE
! || TREE_CODE (def) == NOP_EXPR)
return false;
! def_loop_nb = loop_num (loop_of_stmt (def));
switch (TREE_CODE (def))
{
case PHI_NODE:
! if (loop_phi_node_p (def))
{
! /* When the analyzed phi is the halting_phi, the
! depth-first search is over: we have found a path from
! the halting_phi to itself in the loop. */
! if (def == halting_phi)
! return true;
! /* Otherwise, the evolution of the HALTING_PHI depends
! on the evolution of another loop-phi-node, ie. the
! evolution function is a higher degree polynomial. */
! else if (def_loop_nb == loop_nb)
! return false;
! /* Inner loop. */
! else if (loop_is_strictly_included_in (def_loop_nb,
loop_nb))
! return follow_ssa_edge_inner_loop_phi
! (loop_nb, def, halting_phi, evolution_of_loop);
! else
! /* Outer loop. */
! return false;
! }
!
! /* DEF is a condition-phi-node. Follow the branches, and
! record their evolutions. Finally, merge the collected
! information and set the approximation to the main
! variable. */
! else
! {
! if (PHI_MARKED (def))
! {
! *evolution_of_loop = chrec_top;
! return false;
! }
! else
! {
! bool res;
! PHI_MARKED (def) = 1;
! res = follow_ssa_edge_in_condition_phi
! (loop_nb, def, halting_phi, evolution_of_loop);
! PHI_MARKED (def) = 0;
! return res;
! }
! }
!
case MODIFY_EXPR:
! return follow_ssa_edge_in_rhs (loop_nb,
TREE_OPERAND (def,
1),
halting_phi,
evolution_of_loop);
--- 2392,2461 ----
considered as a single statement. */
static bool
! follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
tree loop_phi_node,
tree halting_phi,
tree *evolution_of_loop)
{
! struct loop *loop = loop_of_stmt (loop_phi_node);
! tree ev = compute_overall_effect_of_inner_loop (loop,
!
PHI_RESULT (loop_phi_node));
!
! return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi,
! evolution_of_loop);
}
/* Follow an SSA edge from a loop-phi-node to itself, constructing a
path that is analyzed on the return walk. */
static bool
! follow_ssa_edge (struct loop *loop,
tree def,
tree halting_phi,
tree *evolution_of_loop)
{
! struct loop *def_loop;
! if (TREE_CODE (def) == NOP_EXPR)
return false;
! def_loop = loop_of_stmt (def);
switch (TREE_CODE (def))
{
case PHI_NODE:
! if (!loop_phi_node_p (def))
{
! /* DEF is a condition-phi-node. Follow the branches, and
! record their evolutions. Finally, merge the collected
! information and set the approximation to the main
! variable. */
! return follow_ssa_edge_in_condition_phi
! (loop, def, halting_phi, evolution_of_loop);
! }
!
! /* When the analyzed phi is the halting_phi, the
! depth-first search is over: we have found a path from
! the halting_phi to itself in the loop. */
! if (def == halting_phi)
! return true;
! /* Otherwise, the evolution of the HALTING_PHI depends
! on the evolution of another loop-phi-node, ie. the
! evolution function is a higher degree polynomial. */
! if (def_loop == loop)
! return false;
! /* Inner loop. */
! if (flow_loop_nested_p (loop, def_loop))
! return follow_ssa_edge_inner_loop_phi
! (loop, def, halting_phi, evolution_of_loop);
! /* Outer loop. */
! return false;
!
case MODIFY_EXPR:
! return follow_ssa_edge_in_rhs (loop,
TREE_OPERAND (def,
1),
halting_phi,
evolution_of_loop);
*************** analyze_evolution_in_loop (tree loop_phi
*** 2672,2679 ****
int i;
tree evolution_function = chrec_not_analyzed_yet;
struct loop *loop = loop_of_stmt (loop_phi_node);
! unsigned loop_nb = loop_num (loop);
! basic_block def_bb;
if (dump_file && (dump_flags & TDF_DETAILS))
{
--- 2478,2484 ----
int i;
tree evolution_function = chrec_not_analyzed_yet;
struct loop *loop = loop_of_stmt (loop_phi_node);
! basic_block bb;
if (dump_file && (dump_flags & TDF_DETAILS))
{
*************** analyze_evolution_in_loop (tree loop_phi
*** 2688,2712 ****
tree arg = PHI_ARG_DEF (loop_phi_node, i);
tree ssa_chain, ev_fn;
bool res;
-
- /* The arguments that are not SSA_NAMEs don't come from the
- loop's body. */
- if (TREE_CODE (arg) != SSA_NAME)
- continue;
- ssa_chain = SSA_NAME_DEF_STMT (arg);
- if (!ssa_chain)
- continue;
- def_bb = bb_for_stmt (ssa_chain);
-
/* Select the edges that enter the loop body. */
! if (!def_bb
! || !flow_bb_inside_loop_p (loop, def_bb))
continue;
! /* Pass in the initial condition to the follow edge function. */
! ev_fn = init_cond;
! res = follow_ssa_edge (loop_nb, ssa_chain, loop_phi_node, &ev_fn);
/* When it is impossible to go back on the same
loop_phi_node by following the ssa edges, the
--- 2493,2514 ----
tree arg = PHI_ARG_DEF (loop_phi_node, i);
tree ssa_chain, ev_fn;
bool res;
/* Select the edges that enter the loop body. */
! bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
! if (!flow_bb_inside_loop_p (loop, bb))
continue;
+
+ if (TREE_CODE (arg) == SSA_NAME)
+ {
+ ssa_chain = SSA_NAME_DEF_STMT (arg);
! /* Pass in the initial condition to the follow edge
function. */
! ev_fn = init_cond;
! res = follow_ssa_edge (loop, ssa_chain, loop_phi_node,
&ev_fn);
! }
! else
! res = false;
/* When it is impossible to go back on the same
loop_phi_node by following the ssa edges, the
*************** analyze_evolution_in_loop (tree loop_phi
*** 2720,2734 ****
create an infinite recurrence. Solution: don't
try to simplify the peeled chrec at this time,
but wait until having more information. */
! tree arg_chrec = arg;
! ev_fn = build_peeled_chrec (loop_nb, init_cond, arg_chrec);
/* Try to simplify the peeled chrec. */
ev_fn = simplify_peeled_chrec (ev_fn);
}
! /* When there are multiple edges that enter the loop,
! merge their evolutions. */
evolution_function = chrec_merge (evolution_function, ev_fn);
}
--- 2522,2535 ----
create an infinite recurrence. Solution: don't
try to simplify the peeled chrec at this time,
but wait until having more information. */
! ev_fn = build_peeled_chrec (loop->num, init_cond, arg);
/* Try to simplify the peeled chrec. */
ev_fn = simplify_peeled_chrec (ev_fn);
}
! /* When there are multiple back edges of the loop (which in fact
never
! happens currently, but nevertheless), merge their evolutions.
*/
evolution_function = chrec_merge (evolution_function, ev_fn);
}
*************** analyze_initial_condition (tree loop_phi
*** 2754,2759 ****
--- 2555,2561 ----
{
int i;
tree init_cond = chrec_not_analyzed_yet;
+ struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
if (dump_file && (dump_flags & TDF_DETAILS))
{
*************** analyze_initial_condition (tree loop_phi
*** 2766,2820 ****
for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
{
tree branch = PHI_ARG_DEF (loop_phi_node, i);
! switch (TREE_CODE (branch))
{
! case SSA_NAME:
! {
! tree ssa_chain = SSA_NAME_DEF_STMT (branch);
!
! if (ssa_chain == NULL_TREE)
! init_cond = chrec_top;
!
! else if (TREE_CODE (ssa_chain) == NOP_EXPR)
! init_cond = branch;
!
! else if (loop_depth (loop_of_stmt (ssa_chain))
! < loop_depth (loop_of_stmt (loop_phi_node)))
! {
! /* When there are several branches to the outside
of
! the loop, pointing to the initial conditions,
and
! one of the initial conditions has a symbolic
value
! (that's the current one: branch) the result of
! chrec_merge is chrec_top. */
! if (init_cond != chrec_not_analyzed_yet)
! init_cond = chrec_top;
!
! /* When SSA_CHAIN is a definition outside the
current
! loop nest, KEEP_IT_SYMBOLIC. */
! else
! init_cond = branch;
! }
! /* When the branch is oriented to the loop's body, it does
! not contribute to the initial condition. */
! break;
! }
!
! default:
! /* In the default case fall all the scalars propagated in
! the loop-phi-node by the CCP. */
! if (init_cond == chrec_not_analyzed_yet)
! init_cond = branch;
!
! else
! /* It is possible that the previous upper branch was a
! constant. Try to merge with the previous information.
*/
! init_cond = chrec_merge (init_cond, branch);
!
! break;
}
}
!
if (init_cond == chrec_not_analyzed_yet)
init_cond = chrec_top;
--- 2568,2596 ----
for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
{
tree branch = PHI_ARG_DEF (loop_phi_node, i);
+ basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
! /* When the branch is oriented to the loop's body, it does
! not contribute to the initial condition. */
! if (flow_bb_inside_loop_p (loop, bb))
! continue;
!
! if (init_cond == chrec_not_analyzed_yet)
{
! init_cond = branch;
! continue;
}
+
+ if (TREE_CODE (branch) == SSA_NAME)
+ {
+ init_cond = chrec_top;
+ break;
+ }
+
+ init_cond = chrec_merge (init_cond, branch);
}
!
! /* Ooops -- a loop without an entry??? */
if (init_cond == chrec_not_analyzed_yet)
init_cond = chrec_top;
*************** analyze_initial_condition (tree loop_phi
*** 2828,2862 ****
return init_cond;
}
! /* Analyze the scalar evolution for the loop-phi-node DEF. LOOP_NB
! determines the returned value, following the loop inclusion: if
! LOOP_NB is contained in loop_of_stmt (def), then the inner value is
! returned, otherwise it's the value that is viewed by a statement
! after the loop. */
static tree
! interpret_loop_phi (unsigned loop_nb,
! tree loop_phi)
{
! tree res = get_scalar_evolution (loop_nb, PHI_RESULT (loop_phi));
! if (res == chrec_not_analyzed_yet)
{
! unsigned loop_phi_nb = loop_num (loop_of_stmt (loop_phi));
! tree init_cond = analyze_initial_condition (loop_phi);
! res = analyze_evolution_in_loop (loop_phi, init_cond);
! set_scalar_evolution (PHI_RESULT (loop_phi), res);
!
! if (loop_is_strictly_included_in (loop_phi_nb, loop_nb))
! {
! /* As in testsuite/.../ssa-chrec-{03, 06}.c we end on the
! loop-phi-node of an inner loop. */
! res = compute_overall_effect_of_inner_loop
! (PHI_RESULT (loop_phi));
! res = interpret_rhs_modify_expr (loop_nb, res);
! }
}
!
return res;
}
--- 2604,2639 ----
return init_cond;
}
! /* Analyze the scalar evolution for the loop-phi-node DEF. */
static tree
! interpret_loop_phi (struct loop *loop, tree loop_phi)
{
! tree res = get_scalar_evolution (loop, PHI_RESULT (loop_phi));
! struct loop *phi_loop = loop_of_stmt (loop_phi);
! tree init_cond;
! if (res != chrec_not_analyzed_yet)
! return res;
!
! if (phi_loop != loop)
{
! struct loop *subloop;
!
! /* Dive one level deeper. */
! subloop = superloop_at_depth (phi_loop, loop->depth + 1);
!
! /* And interpret the subloop. */
! res = compute_overall_effect_of_inner_loop (subloop,
!
PHI_RESULT (loop_phi));
! return res;
}
!
! /* Otherwise really interpret the loop phi. */
! init_cond = analyze_initial_condition (loop_phi);
! res = analyze_evolution_in_loop (loop_phi, init_cond);
! set_scalar_evolution (loop, PHI_RESULT (loop_phi), res);
!
return res;
}
*************** interpret_loop_phi (unsigned loop_nb,
*** 2865,2885 ****
analyzed. */
static tree
! interpret_condition_phi (unsigned loop_nb,
! tree condition_phi)
{
int i;
tree res = chrec_not_analyzed_yet;
for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
{
! tree branch_chrec = analyze_scalar_evolution
! (loop_nb, PHI_ARG_DEF (condition_phi, i));
res = chrec_merge (res, branch_chrec);
}
! set_scalar_evolution (PHI_RESULT (condition_phi), res);
return res;
}
--- 2642,2669 ----
analyzed. */
static tree
! interpret_condition_phi (struct loop *loop, tree condition_phi)
{
int i;
tree res = chrec_not_analyzed_yet;
for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
{
! tree branch_chrec;
!
! if (backedge_phi_arg_p (condition_phi, i))
! {
! res = chrec_top;
! break;
! }
!
! branch_chrec = analyze_scalar_evolution
! (loop, PHI_ARG_DEF (condition_phi, i));
res = chrec_merge (res, branch_chrec);
}
! set_scalar_evolution (loop, PHI_RESULT (condition_phi), res);
return res;
}
*************** interpret_condition_phi (unsigned loop_n
*** 2891,2952 ****
analyze the effect of an inner loop: see interpret_loop_phi. */
static tree
! interpret_rhs_modify_expr (unsigned loop_nb,
! tree opnd1)
{
tree res, opnd10, opnd11, chrec10, chrec11;
! tree type = TREE_TYPE (opnd1);
switch (TREE_CODE (opnd1))
{
case PLUS_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
opnd11 = TREE_OPERAND (opnd1, 1);
! chrec10 = analyze_scalar_evolution (loop_nb, opnd10);
! chrec11 = analyze_scalar_evolution (loop_nb, opnd11);
res = chrec_fold_plus (type, chrec10, chrec11);
break;
case MINUS_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
opnd11 = TREE_OPERAND (opnd1, 1);
! chrec10 = analyze_scalar_evolution (loop_nb, opnd10);
! chrec11 = analyze_scalar_evolution (loop_nb, opnd11);
res = chrec_fold_minus (type, chrec10, chrec11);
break;
!
case MULT_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
opnd11 = TREE_OPERAND (opnd1, 1);
! chrec10 = analyze_scalar_evolution (loop_nb, opnd10);
! chrec11 = analyze_scalar_evolution (loop_nb, opnd11);
res = chrec_fold_multiply (type, chrec10, chrec11);
break;
case SSA_NAME:
! res = chrec_convert
! (type, analyze_scalar_evolution (loop_nb, opnd1));
break;
case NOP_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
! if (opnd10 && TREE_CODE (opnd10) == SSA_NAME)
! /* Don't convert NOP_EXPRs: see ssa-chrec-65.c. The variables
! in the exit condition are casted before the test. Keep the
! cast expression in the chrec.
!
! T.0_17 = (int)i_15;
! T.1_18 = (int)j_16;
! if (T.0_17 < T.1_18) goto <L6>; else goto <L2>;
! */
! /* res = build1 (NOP_EXPR, type,
! analyze_scalar_evolution (loop_nb, opnd10));
! */
! res = analyze_scalar_evolution (loop_nb, opnd10);
!
! else
! res = chrec_top;
!
break;
default:
--- 2675,2736 ----
analyze the effect of an inner loop: see interpret_loop_phi. */
static tree
! interpret_rhs_modify_expr (struct loop *loop,
! tree opnd1, tree type)
{
tree res, opnd10, opnd11, chrec10, chrec11;
!
! if (is_gimple_min_invariant (opnd1))
! return chrec_convert (type, opnd1);
switch (TREE_CODE (opnd1))
{
case PLUS_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
opnd11 = TREE_OPERAND (opnd1, 1);
! chrec10 = analyze_scalar_evolution (loop, opnd10);
! chrec11 = analyze_scalar_evolution (loop, opnd11);
! chrec10 = chrec_convert (type, chrec10);
! chrec11 = chrec_convert (type, chrec11);
res = chrec_fold_plus (type, chrec10, chrec11);
break;
case MINUS_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
opnd11 = TREE_OPERAND (opnd1, 1);
! chrec10 = analyze_scalar_evolution (loop, opnd10);
! chrec11 = analyze_scalar_evolution (loop, opnd11);
! chrec10 = chrec_convert (type, chrec10);
! chrec11 = chrec_convert (type, chrec11);
res = chrec_fold_minus (type, chrec10, chrec11);
break;
!
! case NEGATE_EXPR:
! opnd10 = TREE_OPERAND (opnd1, 0);
! chrec10 = analyze_scalar_evolution (loop, opnd10);
! chrec10 = chrec_convert (type, chrec10);
! res = chrec_fold_negate (type, chrec10);
! break;
!
case MULT_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
opnd11 = TREE_OPERAND (opnd1, 1);
! chrec10 = analyze_scalar_evolution (loop, opnd10);
! chrec11 = analyze_scalar_evolution (loop, opnd11);
! chrec10 = chrec_convert (type, chrec10);
! chrec11 = chrec_convert (type, chrec11);
res = chrec_fold_multiply (type, chrec10, chrec11);
break;
case SSA_NAME:
! res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1));
break;
case NOP_EXPR:
+ case CONVERT_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
! chrec10 = analyze_scalar_evolution (loop, opnd10);
! res = chrec_convert (type, chrec10);
break;
default:
*************** interpret_rhs_modify_expr (unsigned loop
*** 2982,3066 ****
*/
tree
! analyze_scalar_evolution (unsigned loop_nb,
! tree version)
{
! tree res, def;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(analyze_scalar_evolution \n");
! fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
fprintf (dump_file, " (scalar = ");
print_generic_expr (dump_file, version, 0);
fprintf (dump_file, ")\n");
}
! switch (TREE_CODE (version))
{
! case PLUS_EXPR:
! case MINUS_EXPR:
! case MULT_EXPR:
! /* When analyzing non-GIMPLE code. */
! res = interpret_rhs_modify_expr (loop_nb, version);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (res = ");
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, ")\n");
}
! break;
!
! default:
! res = get_scalar_evolution (loop_nb, version);
! if (res == chrec_not_analyzed_yet)
! {
! def = SSA_NAME_DEF_STMT (version);
! if (def == NULL_TREE)
! res = chrec_top;
! else
! {
! switch (TREE_CODE (def))
! {
! case MODIFY_EXPR:
! res = interpret_rhs_modify_expr
! (loop_nb, TREE_OPERAND (def, 1));
!
! /* Following the LOOP_NB from where we're
looking at
! this definition, we have to set the inner or
outer
! visible value. Examples: ssa-chrec-{01, 06}.
*/
! if (loop_is_included_in (loop_nb, loop_num
(loop_of_stmt (def))))
! set_scalar_evolution (version, res);
! else
! set_scalar_evolution_outer_value (version,
res);
!
! break;
! case PHI_NODE:
! if (PHI_MARKED (def))
! res = chrec_top;
! else
! {
! PHI_MARKED (def) = 1;
! if (loop_phi_node_p (def))
! res = interpret_loop_phi (loop_nb,
def);
! else
! res = interpret_condition_phi
(loop_nb, def);
! PHI_MARKED (def) = 0;
! }
! break;
! default:
! res = chrec_top;
! if (TREE_CODE (def) != NOP_EXPR)
! set_scalar_evolution (version, res);
! break;
! }
! }
! }
break;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
--- 2766,2839 ----
*/
tree
! analyze_scalar_evolution (struct loop *loop, tree version)
{
! tree res, def, type = TREE_TYPE (version);
! basic_block bb;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(analyze_scalar_evolution \n");
! fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
fprintf (dump_file, " (scalar = ");
print_generic_expr (dump_file, version, 0);
fprintf (dump_file, ")\n");
}
! res = get_scalar_evolution (loop, version);
!
! if (TREE_CODE (version) != SSA_NAME)
{
! if (res != chrec_top)
! {
! /* Keep the symbolic form. */
! goto end;
! }
!
! /* Try analyzing the expression. */
! res = interpret_rhs_modify_expr (loop, version, type);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (res = ");
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, ")\n");
}
!
! goto end;
! }
! if (res != chrec_not_analyzed_yet)
! goto end;
!
! def = SSA_NAME_DEF_STMT (version);
! bb = bb_for_stmt (def);
! if (!bb
! || !flow_bb_inside_loop_p (loop, bb))
! {
! res = version;
! goto end;
! }
!
! switch (TREE_CODE (def))
! {
! case MODIFY_EXPR:
! res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1),
type);
! break;
! case PHI_NODE:
! if (loop_phi_node_p (def))
! res = interpret_loop_phi (loop, def);
! else
! res = interpret_condition_phi (loop, def);
! break;
! default:
! res = chrec_top;
break;
}
+
+ end:
+ set_scalar_evolution (loop, version, res);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
*************** analyze_scalar_evolution (unsigned loop_
*** 3069,3079 ****
}
/* Analyze all the parameters of the chrec that were left under a
! symbolic form. LOOP_NB is the loop in which symbolic names have to
be analyzed and instantiated. */
tree
! instantiate_parameters (unsigned loop_nb,
tree chrec)
{
tree res, op0, op1, op2;
--- 2842,2852 ----
}
/* 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. */
tree
! instantiate_parameters (struct loop *loop,
tree chrec)
{
tree res, op0, op1, op2;
*************** instantiate_parameters (unsigned loop_nb
*** 3086,3092 ****
|| TREE_CODE (chrec) == VAR_DECL
|| TREE_CODE (chrec) == PARM_DECL)
{
! if (tree_is_in_varray_tree_p (chrec, *already_instantiated))
/* Don't instantiate the SSA_NAME if it is in a mixer
structure. This is used for avoiding the instantiation of
recursively defined functions, such as:
--- 2859,2865 ----
|| TREE_CODE (chrec) == VAR_DECL
|| TREE_CODE (chrec) == PARM_DECL)
{
! if (tree_is_in_varray_tree_p (chrec, already_instantiated))
/* Don't instantiate the SSA_NAME if it is in a mixer
structure. This is used for avoiding the instantiation of
recursively defined functions, such as:
*************** instantiate_parameters (unsigned loop_nb
*** 3101,3107 ****
else
{
! res = analyze_scalar_evolution (loop_nb, chrec);
/* If the analysis yields a parametric chrec, instantiate
the result again. Enqueue the SSA_NAME such that it will
--- 2874,2880 ----
else
{
! res = analyze_scalar_evolution (loop, chrec);
/* If the analysis yields a parametric chrec, instantiate
the result again. Enqueue the SSA_NAME such that it will
*************** instantiate_parameters (unsigned loop_nb
*** 3109,3163 ****
instantiation in mixers. */
if (chrec_contains_symbols (res))
{
! VARRAY_PUSH_TREE (*already_instantiated, chrec);
! res = instantiate_parameters (loop_nb, res);
! VARRAY_POP (*already_instantiated);
}
}
}
-
else
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
! op0 = instantiate_parameters (loop_nb, CHREC_LEFT (chrec));
! op1 = instantiate_parameters (loop_nb, CHREC_RIGHT (chrec));
res = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0,
op1);
break;
case EXPONENTIAL_CHREC:
! op0 = instantiate_parameters (loop_nb, CHREC_LEFT (chrec));
! op1 = instantiate_parameters (loop_nb, CHREC_RIGHT (chrec));
res = build_exponential_chrec (CHREC_VARIABLE (chrec), op0,
op1);
break;
case PEELED_CHREC:
! op0 = instantiate_parameters (loop_nb, CHREC_LEFT (chrec));
! op1 = instantiate_parameters (loop_nb, CHREC_RIGHT (chrec));
res = build_peeled_chrec (CHREC_VARIABLE (chrec), op0, op1);
break;
case INTERVAL_CHREC:
! op0 = instantiate_parameters (loop_nb, CHREC_LOW (chrec));
! op1 = instantiate_parameters (loop_nb, CHREC_UP (chrec));
res = build_interval_chrec (op0, op1);
break;
case PLUS_EXPR:
! op0 = instantiate_parameters (loop_nb, TREE_OPERAND (chrec,
0));
! op1 = instantiate_parameters (loop_nb, TREE_OPERAND (chrec,
1));
res = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
break;
case MINUS_EXPR:
! op0 = instantiate_parameters (loop_nb, TREE_OPERAND (chrec,
0));
! op1 = instantiate_parameters (loop_nb, TREE_OPERAND (chrec,
1));
res = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
break;
case MULT_EXPR:
! op0 = instantiate_parameters (loop_nb, TREE_OPERAND (chrec,
0));
! op1 = instantiate_parameters (loop_nb, TREE_OPERAND (chrec,
1));
res = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
break;
--- 2882,2935 ----
instantiation in mixers. */
if (chrec_contains_symbols (res))
{
! VARRAY_PUSH_TREE (already_instantiated, chrec);
! res = instantiate_parameters (loop, res);
! VARRAY_POP (already_instantiated);
}
}
}
else
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
! op0 = instantiate_parameters (loop, CHREC_LEFT (chrec));
! op1 = instantiate_parameters (loop, CHREC_RIGHT (chrec));
res = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0,
op1);
break;
case EXPONENTIAL_CHREC:
! op0 = instantiate_parameters (loop, CHREC_LEFT (chrec));
! op1 = instantiate_parameters (loop, CHREC_RIGHT (chrec));
res = build_exponential_chrec (CHREC_VARIABLE (chrec), op0,
op1);
break;
case PEELED_CHREC:
! op0 = instantiate_parameters (loop, CHREC_LEFT (chrec));
! op1 = instantiate_parameters (loop, CHREC_RIGHT (chrec));
res = build_peeled_chrec (CHREC_VARIABLE (chrec), op0, op1);
break;
case INTERVAL_CHREC:
! op0 = instantiate_parameters (loop, CHREC_LOW (chrec));
! op1 = instantiate_parameters (loop, CHREC_UP (chrec));
res = build_interval_chrec (op0, op1);
break;
case PLUS_EXPR:
! op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0));
! op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1));
res = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
break;
case MINUS_EXPR:
! op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0));
! op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1));
res = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
break;
case MULT_EXPR:
! op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0));
! op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1));
res = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
break;
*************** instantiate_parameters (unsigned loop_nb
*** 3173,3179 ****
instantiate_parameters (loop_nb,
TREE_OPERAND (chrec, 0)));
*/
! res = instantiate_parameters (loop_nb, TREE_OPERAND (chrec,
0));
break;
default:
--- 2945,2951 ----
instantiate_parameters (loop_nb,
TREE_OPERAND (chrec, 0)));
*/
! res = instantiate_parameters (loop, TREE_OPERAND (chrec, 0));
break;
default:
*************** instantiate_parameters (unsigned loop_nb
*** 3181,3205 ****
{
case 3:
op0 = instantiate_parameters
! (loop_nb, TREE_OPERAND (chrec, 0));
op1 = instantiate_parameters
! (loop_nb, TREE_OPERAND (chrec, 1));
op2 = instantiate_parameters
! (loop_nb, TREE_OPERAND (chrec, 2));
res = build (TREE_CODE (chrec), TREE_TYPE (chrec), op0,
op1, op2);
break;
case 2:
op0 = instantiate_parameters
! (loop_nb, TREE_OPERAND (chrec, 0));
op1 = instantiate_parameters
! (loop_nb, TREE_OPERAND (chrec, 1));
res = build (TREE_CODE (chrec), TREE_TYPE (chrec), op0,
op1);
break;
case 1:
res = instantiate_parameters
! (loop_nb, TREE_OPERAND (chrec, 0));
if (!automatically_generated_chrec_p (res))
res = build1 (TREE_CODE (chrec), TREE_TYPE (chrec),
res);
break;
--- 2953,2977 ----
{
case 3:
op0 = instantiate_parameters
! (loop, TREE_OPERAND (chrec, 0));
op1 = instantiate_parameters
! (loop, TREE_OPERAND (chrec, 1));
op2 = instantiate_parameters
! (loop, TREE_OPERAND (chrec, 2));
res = build (TREE_CODE (chrec), TREE_TYPE (chrec), op0,
op1, op2);
break;
case 2:
op0 = instantiate_parameters
! (loop, TREE_OPERAND (chrec, 0));
op1 = instantiate_parameters
! (loop, TREE_OPERAND (chrec, 1));
res = build (TREE_CODE (chrec), TREE_TYPE (chrec), op0,
op1);
break;
case 1:
res = instantiate_parameters
! (loop, TREE_OPERAND (chrec, 0));
if (!automatically_generated_chrec_p (res))
res = build1 (TREE_CODE (chrec), TREE_TYPE (chrec),
res);
break;
*************** instantiate_parameters (unsigned loop_nb
*** 3237,3243 ****
tree
number_of_iterations_in_loop (struct loop *loop)
{
- int loop_nb = loop_num (loop);
tree res;
tree cond, test, opnd0, opnd1;
tree chrec0, chrec1;
--- 3009,3014 ----
*************** number_of_iterations_in_loop (struct loo
*** 3265,3271 ****
{
case SSA_NAME:
/* "while (opnd0 != 0)". */
! chrec0 = analyze_scalar_evolution (loop_nb, test);
chrec1 = integer_zero_node;
if (chrec0 == chrec_top)
--- 3036,3042 ----
{
case SSA_NAME:
/* "while (opnd0 != 0)". */
! chrec0 = analyze_scalar_evolution (loop, test);
chrec1 = integer_zero_node;
if (chrec0 == chrec_top)
*************** number_of_iterations_in_loop (struct loo
*** 3274,3280 ****
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
fprintf (dump_file, " (loop_while_expr_is_true: ");
print_generic_expr (dump_file, test, 0);
fprintf (dump_file, ")\n (chrec0 = ");
--- 3045,3051 ----
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
fprintf (dump_file, " (loop_while_expr_is_true: ");
print_generic_expr (dump_file, test, 0);
fprintf (dump_file, ")\n (chrec0 = ");
*************** number_of_iterations_in_loop (struct loo
*** 3287,3295 ****
else
return set_nb_iterations_in_loop
! (loop, first_iteration_non_satisfying (NE_EXPR, loop_nb,
chrec0, chrec1));
!
case LT_EXPR:
case LE_EXPR:
case GT_EXPR:
--- 3058,3066 ----
else
return set_nb_iterations_in_loop
! (loop, first_iteration_non_satisfying (NE_EXPR, loop->num,
chrec0, chrec1));
!
case LT_EXPR:
case LE_EXPR:
case GT_EXPR:
*************** number_of_iterations_in_loop (struct loo
*** 3298,3308 ****
case NE_EXPR:
opnd0 = TREE_OPERAND (test, 0);
opnd1 = TREE_OPERAND (test, 1);
! chrec0 = analyze_scalar_evolution (loop_nb, opnd0);
! chrec1 = analyze_scalar_evolution (loop_nb, opnd1);
! chrec0 = instantiate_parameters (loop_nb, chrec0);
! chrec1 = instantiate_parameters (loop_nb, chrec1);
if (chrec0 == chrec_top)
/* KEEP_IT_SYMBOLIC. */
--- 3069,3079 ----
case NE_EXPR:
opnd0 = TREE_OPERAND (test, 0);
opnd1 = TREE_OPERAND (test, 1);
! chrec0 = analyze_scalar_evolution (loop, opnd0);
! chrec1 = analyze_scalar_evolution (loop, opnd1);
! chrec0 = instantiate_parameters (loop, chrec0);
! chrec1 = instantiate_parameters (loop, chrec1);
if (chrec0 == chrec_top)
/* KEEP_IT_SYMBOLIC. */
*************** number_of_iterations_in_loop (struct loo
*** 3314,3320 ****
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
fprintf (dump_file, " (loop_while_expr_is_true: ");
print_generic_expr (dump_file, test, 0);
fprintf (dump_file, ")\n (chrec0 = ");
--- 3085,3091 ----
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
fprintf (dump_file, " (loop_while_expr_is_true: ");
print_generic_expr (dump_file, test, 0);
fprintf (dump_file, ")\n (chrec0 = ");
*************** number_of_iterations_in_loop (struct loo
*** 3329,3337 ****
return cannot_analyze_loop_nb_iterations_yet ();
return set_nb_iterations_in_loop
! (loop, first_iteration_non_satisfying (TREE_CODE (test),
loop_nb,
chrec0,
chrec1));
-
default:
return set_nb_iterations_in_loop (loop, chrec_top);
}
--- 3100,3107 ----
return cannot_analyze_loop_nb_iterations_yet ();
return set_nb_iterations_in_loop
! (loop, first_iteration_non_satisfying (TREE_CODE (test),
loop->num,
chrec0,
chrec1));
default:
return set_nb_iterations_in_loop (loop, chrec_top);
}
*************** dump_chrecs_stats (FILE *file)
*** 3467,3473 ****
stats_nb_undetermined);
fprintf (file, "-----------------------------------------\n");
fprintf (file, "%d\tchrecs in the scev database\n",
! VARRAY_ACTIVE_SIZE (*scalar_evolution_info));
fprintf (file, "-----------------------------------------\n");
fprintf (file, ")\n\n");
}
--- 3237,3243 ----
stats_nb_undetermined);
fprintf (file, "-----------------------------------------\n");
fprintf (file, "%d\tchrecs in the scev database\n",
! VARRAY_ACTIVE_SIZE (scalar_evolution_info));
fprintf (file, "-----------------------------------------\n");
fprintf (file, ")\n\n");
}
*************** analyze_scalar_evolution_for_all_loop_ph
*** 3492,3512 ****
for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
{
struct loop *loop;
- unsigned loop_nb;
basic_block bb;
tree phi, chrec;
loop = loop_of_stmt (VARRAY_TREE (exit_conditions, i));
- loop_nb = loop_num (loop);
bb = loop_header (loop);
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
! if (TREE_CODE (phi) == PHI_NODE
! && NUM_VDEFS (STMT_VDEF_OPS (phi)) == 0)
{
chrec = instantiate_parameters
! (loop_nb,
! analyze_scalar_evolution (loop_nb, PHI_RESULT (phi)));
if (dump_file && (dump_flags & TDF_STATS))
gather_chrec_stats (dump_file, chrec);
--- 3262,3279 ----
for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
{
struct loop *loop;
basic_block bb;
tree phi, chrec;
loop = loop_of_stmt (VARRAY_TREE (exit_conditions, i));
bb = loop_header (loop);
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
! if (is_gimple_reg (PHI_RESULT (phi)))
{
chrec = instantiate_parameters
! (loop,
! analyze_scalar_evolution (loop, PHI_RESULT (phi)));
if (dump_file && (dump_flags & TDF_STATS))
gather_chrec_stats (dump_file, chrec);
*************** gather_stats_on_scev_database (void)
*** 3529,3539 ****
reset_chrecs_counters ();
! for (i = 0; i < VARRAY_ACTIVE_SIZE (*scalar_evolution_info); i++)
{
struct scev_info_str *elt =
! VARRAY_GENERIC_PTR (*scalar_evolution_info, i);
! gather_chrec_stats (dump_file, MI_INNER_LOOPS_CHREC (elt));
}
dump_chrecs_stats (dump_file);
--- 3296,3306 ----
reset_chrecs_counters ();
! for (i = 0; i < VARRAY_ACTIVE_SIZE (scalar_evolution_info); i++)
{
struct scev_info_str *elt =
! VARRAY_GENERIC_PTR (scalar_evolution_info, i);
! gather_chrec_stats (dump_file, elt->chrec);
}
dump_chrecs_stats (dump_file);
*************** scev_initialize (struct loops *loops)
*** 3575,3588 ****
{
current_loops = loops;
! scalar_evolution_info_st = NULL;
! already_instantiated_st = NULL;
! VARRAY_GENERIC_PTR_INIT (scalar_evolution_info_st, 100,
"scalar_evolution_info");
! VARRAY_TREE_INIT (already_instantiated_st, 3,
"already_instantiated");
- scalar_evolution_info = &scalar_evolution_info_st;
- already_instantiated = &already_instantiated_st;
initialize_scalar_evolutions_analyzer ();
}
--- 3342,3351 ----
{
current_loops = loops;
! VARRAY_GENERIC_PTR_INIT (scalar_evolution_info, 100,
"scalar_evolution_info");
! VARRAY_TREE_INIT (already_instantiated, 3,
"already_instantiated");
initialize_scalar_evolutions_analyzer ();
}
*************** scev_initialize (struct loops *loops)
*** 3592,3598 ****
static void
scev_init (void)
{
! current_loops = tree_loop_optimizer_init (NULL, true);
if (!current_loops)
return;
scev_initialize (current_loops);
--- 3355,3361 ----
static void
scev_init (void)
{
! current_loops = tree_loop_optimizer_init (NULL, flag_tree_loop != 0);
if (!current_loops)
return;
scev_initialize (current_loops);
*************** scev_elim_checks (void)
*** 3640,3646 ****
static void
scev_linear_transform (void)
{
! linear_transform_loops (current_loops, *scalar_evolution_info);
}
/* Runs the canonical iv creation pass. */
--- 3403,3409 ----
static void
scev_linear_transform (void)
{
! linear_transform_loops (current_loops, scalar_evolution_info);
}
/* Runs the canonical iv creation pass. */
*************** scev_vectorize (void)
*** 3658,3664 ****
{
bitmap_clear (vars_to_rename);
! vectorize_loops (current_loops, *scalar_evolution_info);
}
/* Finalize the scalar evolution analysis. */
--- 3421,3427 ----
{
bitmap_clear (vars_to_rename);
! vectorize_loops (current_loops, scalar_evolution_info);
}
/* Finalize the scalar evolution analysis. */
*************** scev_vectorize (void)
*** 3666,3673 ****
void
scev_finalize (void)
{
! VARRAY_CLEAR (*scalar_evolution_info);
! VARRAY_CLEAR (*already_instantiated);
current_loops = NULL;
}
--- 3429,3436 ----
void
scev_finalize (void)
{
! scalar_evolution_info = NULL;
! already_instantiated = NULL;
current_loops = NULL;
}
Index: tree-scalar-evolution.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.h,v
retrieving revision 1.1.2.8
diff -c -3 -p -r1.1.2.8 tree-scalar-evolution.h
*** tree-scalar-evolution.h 30 Mar 2004 17:45:52 -0000
1.1.2.8
--- tree-scalar-evolution.h 30 Mar 2004 20:53:35 -0000
*************** extern tree get_loop_exit_condition (str
*** 29,63 ****
extern void scev_initialize (struct loops *loops);
extern void scev_finalize (void);
! extern tree analyze_scalar_evolution (unsigned, tree);
! extern tree instantiate_parameters (unsigned, tree);
extern void eliminate_redundant_checks (void);
extern void gather_stats_on_scev_database (void);
-
- struct scev_info_str {
- tree var;
- tree inner_loops_chrec;
- tree outer_loops_chrec;
- };
-
- #define MI_VAR(MI) MI->var
- #define MI_INNER_LOOPS_CHREC(MI) MI->inner_loops_chrec
- #define MI_OUTER_LOOPS_CHREC(MI) MI->outer_loops_chrec
-
- /* Constructs a new SCEV_INFO_STR structure. */
-
- static inline struct scev_info_str *
- new_scev_info_str (tree var)
- {
- struct scev_info_str *res;
-
- res = ggc_alloc (sizeof (struct scev_info_str));
- MI_VAR (res) = var;
- MI_INNER_LOOPS_CHREC (res) = chrec_not_analyzed_yet;
- MI_OUTER_LOOPS_CHREC (res) = chrec_not_analyzed_yet;
-
- return res;
- }
#endif /* GCC_TREE_SCALAR_EVOLUTION_H */
--- 29,38 ----
extern void scev_initialize (struct loops *loops);
extern void scev_finalize (void);
! extern tree analyze_scalar_evolution (struct loop *, tree);
! extern tree instantiate_parameters (struct loop *, tree);
extern void eliminate_redundant_checks (void);
extern void gather_stats_on_scev_database (void);
#endif /* GCC_TREE_SCALAR_EVOLUTION_H */
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-manip.c,v
retrieving revision 1.1.2.8
diff -c -3 -p -r1.1.2.8 tree-ssa-loop-manip.c
*** tree-ssa-loop-manip.c 30 Mar 2004 01:39:54 -0000
1.1.2.8
--- tree-ssa-loop-manip.c 30 Mar 2004 20:53:35 -0000
*************** add_exit_phis_use (basic_block bb, tree
*** 729,736 ****
unsigned n_exits, basic_block *exits)
{
tree def;
! basic_block def_bb;
unsigned i;
if (TREE_CODE (use) != SSA_NAME)
return;
--- 729,738 ----
unsigned n_exits, basic_block *exits)
{
tree def;
! basic_block def_bb, ign_bb;
unsigned i;
+ edge e;
+ struct loop *src_loop;
if (TREE_CODE (use) != SSA_NAME)
return;
*************** add_exit_phis_use (basic_block bb, tree
*** 745,762 ****
return;
bitmap_set_bit (names_to_rename, SSA_NAME_VERSION (use));
- /* We must add phi nodes for all loop exits (not just those involved),
- since ssa rewriting creates new phi nodes in loop headers. ???
Perhaps
- it would be sufficient to do this for superloops of the
- def_bb->loop_father? */
-
/* Do not insert a new phi if there already is one defining the use.
*/
! if (TREE_CODE (def) != PHI_NODE)
! def_bb = NULL;
for (i = 0; i < n_exits; i++)
! if (exits[i] != def_bb)
add_exit_phis_edge (exits[i], use);
}
/* Add exit phis for the names used in STMT in BB. Mark the ssa names in
--- 747,777 ----
return;
bitmap_set_bit (names_to_rename, SSA_NAME_VERSION (use));
/* Do not insert a new phi if there already is one defining the use.
*/
! ign_bb = (TREE_CODE (def) == PHI_NODE) ? def_bb : NULL;
for (i = 0; i < n_exits; i++)
! {
! if (exits[i] == ign_bb)
! continue;
!
! /* We must add phi nodes for all loop exits of the superloops of
! def_bb->loop_father. */
!
! for (e = exits[i]->pred; e; e = e->pred_next)
! {
! src_loop = find_common_loop (e->src->loop_father,
!
def_bb->loop_father);
!
! if (!flow_bb_inside_loop_p (src_loop, e->dest))
! break;
! }
!
! if (!e)
! continue;
!
add_exit_phis_edge (exits[i], use);
+ }
}
/* Add exit phis for the names used in STMT in BB. Mark the ssa names in
Index: tree-vectorizer.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-vectorizer.c,v
retrieving revision 1.1.2.24
diff -c -3 -p -r1.1.2.24 tree-vectorizer.c
*** tree-vectorizer.c 23 Mar 2004 08:12:35 -0000 1.1.2.24
--- tree-vectorizer.c 30 Mar 2004 20:53:35 -0000
*************** vect_analyze_scalar_cycles (loop_vec_inf
*** 2185,2192 ****
fprintf (dump_file, "analyze cycles: call monev analyzer!\n");
access_fn = instantiate_parameters
! (loop_num (loop),
! analyze_scalar_evolution (loop_num (loop), PHI_RESULT
(phi)));
if (!access_fn)
{
--- 2185,2192 ----
fprintf (dump_file, "analyze cycles: call monev analyzer!\n");
access_fn = instantiate_parameters
! (loop,
! analyze_scalar_evolution (loop, PHI_RESULT (phi)));
if (!access_fn)
{
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.154.2.9
diff -c -3 -p -r1.342.2.154.2.9 tree.h
*** tree.h 21 Mar 2004 03:20:23 -0000 1.342.2.154.2.9
--- tree.h 30 Mar 2004 20:53:36 -0000
*************** struct tree_ssa_name GTY(())
*** 1077,1083 ****
/* Nonzero if the PHI node was rewritten by a previous pass through the
SSA renamer. */
#define PHI_REWRITTEN(NODE) PHI_NODE_CHECK (NODE)->phi.rewritten
- #define PHI_MARKED(NODE) PHI_NODE_CHECK (NODE)->phi.marked
#define PHI_NUM_ARGS(NODE) PHI_NODE_CHECK (NODE)->phi.num_args
#define PHI_ARG_CAPACITY(NODE) PHI_NODE_CHECK
(NODE)->phi.capacity
#define PHI_ARG_ELT(NODE, I) PHI_NODE_ELT_CHECK (NODE, I)
--- 1077,1082 ----
*************** struct tree_phi_node GTY(())
*** 1103,1112 ****
SSA renamer. */
unsigned int rewritten:1;
- /* Nonzero if the PHI node has already been walked by the scalar
- evolution analyzer. */
- unsigned int marked:1;
-
struct phi_arg_d GTY ((length ("((tree)&%h)->phi.capacity"))) a[1];
};
--- 1102,1107 ----
More information about the Gcc-patches
mailing list