This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] Lno branch merge -- scalar evolutions analyzer
On Fri, Jul 02, 2004 at 03:54:40PM -0700, Mark Mitchell wrote:
> >
> >PS: It seems like my original mail has been lost... Here is a smaller
> >mail and the link to the patch on a web-server:
> >
> > http://www.cri.ensmp.fr/~pop/gcc/scev.diff
> >
> >
> For me, that shows up without line breaks in Mozilla running on
> GNU/Linux. Would you mind fixing that in some way?
>
I will try to send the patch again, sorry for the inconvenients.
Sebastian
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1315
diff -d -u -p -r1.1315 Makefile.in
--- Makefile.in 30 Jun 2004 21:11:25 -0000 1.1315
+++ Makefile.in 30 Jun 2004 23:13:58 -0000
@@ -727,6 +727,7 @@ TREE_SSA_LIVE_H = tree-ssa-live.h $(PART
PRETTY_PRINT_H = pretty-print.h input.h $(OBSTACK_H)
DIAGNOSTIC_H = diagnostic.h diagnostic.def $(PRETTY_PRINT_H)
C_PRETTY_PRINT_H = $(PRETTY_PRINT_H) $(C_COMMON_H) $(TREE_H)
+SCEV_H = tree-scalar-evolution.h $(GGC_H) tree-chrec.h
#
# Now figure out from those variables how to compile and link.
@@ -885,7 +886,7 @@ C_OBJS = c-parse.o c-lang.o stub-objc.o
# Language-independent object files.
OBJS-common = \
- tree-chrec.o \
+ tree-chrec.o tree-scalar-evolution.o tree-ssa-loop-niter.o \
tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o \
tree-alias-type.o gimplify.o tree-pretty-print.o tree-into-ssa.o \
tree-outof-ssa.o tree-alias-common.o tree-ssa-ccp.o tree-vn.o \
@@ -1683,6 +1684,10 @@ tree-ssa-alias.o : tree-ssa-alias.c $(TR
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) tree-inline.h $(FLAGS_H) \
function.h $(TIMEVAR_H) tree-alias-common.h convert.h $(TM_H) coretypes.h \
langhooks.h $(TREE_DUMP_H) tree-pass.h params.h
+tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \
+ $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h $(PARAMS_H) tree-inline.h \
+ output.h diagnostic.h $(TM_H) coretypes.h $(TREE_DUMP_H) flags.h \
+ tree-pass.h $(SCEV_H)
tree-optimize.o : tree-optimize.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) \
$(GGC_H) output.h diagnostic.h errors.h $(FLAGS_H) tree-alias-common.h \
@@ -1707,8 +1712,12 @@ tree-browser.o : tree-browser.c tree-bro
$(TM_H) coretypes.h
tree-chrec.o: tree-chrec.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
errors.h $(GGC_H) $(TREE_H) tree-chrec.h tree-pass.h
+tree-scalar-evolution.o: tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \
+ coretypes.h $(TM_H) errors.h $(GGC_H) $(TREE_H) $(RTL_H) \
+ $(BASIC_BLOCK_H) diagnostic.h $(TREE_FLOW_H) $(TREE_DUMP_H) \
+ $(TIMEVAR_H) cfgloop.h $(SCEV_H) tree-pass.h flags.h
tree-gimple.o : tree-gimple.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(EXPR_H) \
- $(RTL_H) $(TREE_GIMPLE_H) $(TM_H) coretypes.h bitmap.h $(GGC_H)
+ $(RTL_H) $(TREE_GIMPLE_H) $(TM_H) coretypes.h bitmap.h $(GGC_H)
tree-mudflap.o : $(CONFIG_H) errors.h $(SYSTEM_H) $(TREE_H) tree-inline.h \
$(C_TREE_H) $(C_COMMON_H) $(TREE_GIMPLE_H) diagnostic.h $(HASHTAB_H) \
output.h varray.h langhooks.h tree-mudflap.h $(TM_H) coretypes.h \
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.200
diff -d -u -p -r1.200 basic-block.h
--- basic-block.h 30 Jun 2004 18:04:57 -0000 1.200
+++ basic-block.h 30 Jun 2004 23:13:58 -0000
@@ -178,6 +178,22 @@ typedef struct edge_def *edge;
#define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH)
+/* Returns the block at the beginning of the edge. */
+
+static inline struct basic_block_def *
+edge_source (edge e)
+{
+ return e->src;
+}
+
+/* Returns the block at the end of the edge. */
+
+static inline struct basic_block_def *
+edge_destination (edge e)
+{
+ return e->dest;
+}
+
/* Counter summary from the last set of coverage counts read by
profile.c. */
extern const struct gcov_ctr_summary *profile_info;
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.32
diff -d -u -p -r1.32 cfgloop.c
--- cfgloop.c 13 May 2004 06:39:32 -0000 1.32
+++ cfgloop.c 30 Jun 2004 23:13:58 -0000
@@ -101,6 +101,20 @@ flow_loop_nested_p (const struct loop *o
&& loop->pred[outer->depth] == outer;
}
+/* Returns superloop of LOOP at given DEPTH. */
+
+struct loop *
+superloop_at_depth (struct loop *loop, unsigned depth)
+{
+ if (depth > (unsigned) loop->depth)
+ abort ();
+
+ if (depth == (unsigned) loop->depth)
+ return loop;
+
+ return loop->pred[depth];
+}
+
/* Dump the loop information specified by LOOP to the stream FILE
using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.20
diff -d -u -p -r1.20 cfgloop.h
--- cfgloop.h 20 Jun 2004 21:31:28 -0000 1.20
+++ cfgloop.h 30 Jun 2004 23:13:58 -0000
@@ -175,6 +175,16 @@ struct loop
/* The number of LABEL_REFs on exit_labels for this loop and all
loops nested inside it. */
int exit_count;
+
+ /* The probable number of times the loop is executed at runtime.
+ This is an INTEGER_CST or an expression containing symbolic
+ names. Don't access this field directly:
+ number_of_iterations_in_loop computes and caches the computed
+ information in this field. */
+ tree nb_iterations;
+
+ /* Upper bound on number of iterations of a loop. */
+ struct nb_iter_bound *bounds;
};
/* Flags for state of loop structure. */
@@ -224,6 +234,10 @@ struct loops
int state;
};
+/* The loop tree currently optimized. */
+
+extern struct loops *current_loops;
+
/* Flags for loop discovery. */
#define LOOP_TREE 1 /* Build loop hierarchy tree. */
@@ -252,7 +266,8 @@ extern void flow_loop_tree_node_remove (
extern bool flow_loop_outside_edge_p (const struct loop *, edge);
extern bool flow_loop_nested_p (const struct loop *, const struct loop *);
extern bool flow_bb_inside_loop_p (const struct loop *, const basic_block);
-extern struct loop * find_common_loop (struct loop *, struct loop *);
+extern struct loop *find_common_loop (struct loop *, struct loop *);
+extern struct loop *superloop_at_depth (struct loop *, unsigned);
extern int num_loop_insns (struct loop *);
extern int average_num_loop_insns (struct loop *);
extern unsigned get_loop_level (const struct loop *);
@@ -434,4 +449,95 @@ extern void unroll_and_peel_loops (struc
extern void doloop_optimize_loops (struct loops *);
extern void move_loop_invariants (struct loops *);
+/* Returns the loop at position NUM from the loops array. */
+
+static inline struct loop *
+loop_from_num (struct loops *loops,
+ unsigned num)
+{
+ return loops->parray[num];
+}
+
+/* Returns the outer loop. */
+
+static inline struct loop *
+outer_loop (struct loop *loop)
+{
+ return loop->outer;
+}
+
+/* Returns the inner loop. */
+
+static inline struct loop *
+inner_loop (struct loop *loop)
+{
+ return loop->inner;
+}
+
+/* Returns the next loop. */
+
+static inline struct loop *
+next_loop (struct loop *loop)
+{
+ return loop->next;
+}
+
+/* Returns the number of a loop. */
+
+static inline unsigned
+loop_num (struct loop *loop)
+{
+ return loop->num;
+}
+
+/* Returns the depth of a loop. */
+
+static inline unsigned
+loop_depth (struct loop *loop)
+{
+ return loop->depth;
+}
+
+/* Returns the header basic block of the loop. */
+
+static inline basic_block
+loop_header (struct loop *loop)
+{
+ return loop->header;
+}
+
+/* Returns the number of iterations in the loop. Use
+ number_of_iterations_in_loop () instead of accessing directly this
+ field. */
+
+static inline tree
+loop_nb_iterations (struct loop *loop)
+{
+ return loop->nb_iterations;
+}
+
+/* Returns the number of exit edges of the loop. */
+
+static inline unsigned
+loop_num_exits (struct loop *loop)
+{
+ return loop->num_exits;
+}
+
+/* Returns the exit edges of the loop. */
+
+static inline edge *
+loop_exit_edges (struct loop *loop)
+{
+ return loop->exit_edges;
+}
+
+/* Returns the n-th exit edge of the loop. */
+
+static inline edge
+loop_exit_edge (struct loop *loop, unsigned n)
+{
+ return loop->exit_edges[n];
+}
+
#endif /* GCC_CFGLOOP_H */
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v
retrieving revision 2.1
diff -d -u -p -r2.1 tree-chrec.c
--- tree-chrec.c 30 Jun 2004 15:37:42 -0000 2.1
+++ tree-chrec.c 30 Jun 2004 23:13:58 -0000
@@ -37,47 +37,6 @@ Software Foundation, 59 Temple Place - S
#include "tree-pass.h"
-/* This part will be removed once the merging is finished. */
-
-
-
-/* The following trees are unique elements. Thus the comparison of
- another element to these elements should be done on the pointer to
- these trees, and not on their value. */
-
-/* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
-tree chrec_not_analyzed_yet;
-
-/* Reserved to the cases where the analyzer has detected an
- undecidable property at compile time. */
-tree chrec_dont_know;
-
-/* When the analyzer has detected that a property will never
- happen, then it qualifies it with chrec_known. */
-tree chrec_known;
-
-/* Empty hook. Will be replaced by the main function from
- tree-scalar-evolution.c. */
-
-tree
-count_ev_in_wider_type (tree foo ATTRIBUTE_UNUSED,
- tree bar ATTRIBUTE_UNUSED)
-{
- return NULL_TREE;
-}
-
-/* Empty hook. Will be replaced by the main function from
- tree-scalar-evolution.c. */
-
-bool
-chrec_contains_symbols_defined_in_loop (tree chrec ATTRIBUTE_UNUSED,
- unsigned loop_nb ATTRIBUTE_UNUSED)
-{
- return true;
-}
-
-
-
/* Extended folder for chrecs. */
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.13
diff -d -u -p -r2.13 tree-flow-inline.h
--- tree-flow-inline.h 30 Jun 2004 18:21:53 -0000 2.13
+++ tree-flow-inline.h 30 Jun 2004 23:13:58 -0000
@@ -724,6 +724,18 @@ bsi_stmt_ptr (block_stmt_iterator i)
return tsi_stmt_ptr (i.tsi);
}
+/* Return the loop of the statement STMT. */
+
+static inline struct loop *
+loop_of_stmt (tree stmt)
+{
+ basic_block bb = bb_for_stmt (stmt);
+ if (!bb)
+ return NULL;
+
+ return bb->loop_father;
+}
+
/* Return true if VAR may be aliased. */
static inline bool
may_be_aliased (tree var)
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.17
diff -d -u -p -r2.17 tree-flow.h
--- tree-flow.h 30 Jun 2004 21:28:59 -0000 2.17
+++ tree-flow.h 30 Jun 2004 23:13:58 -0000
@@ -595,6 +595,27 @@ extern void propagate_value (use_operand
extern void propagate_tree_value (tree *, tree);
extern void replace_exp (use_operand_p, tree);
+/* Description of number of iterations of a loop. */
+struct tree_niter_desc
+{
+ tree assumptions; /* Assumptions for the number of iterations be valid. */
+ tree may_be_zero; /* Condition under that the loop exits in the first
+ iteration. */
+ tree niter; /* Number of iterations. */
+ tree additional_info; /* Additional conditions taken into account when
+ deriving the information above. */
+};
+
+extern void number_of_iterations_cond (tree, tree, tree, enum tree_code, tree,
+ tree, struct tree_niter_desc *);
+extern bool number_of_iterations_exit (struct loop *, edge,
+ struct tree_niter_desc *niter);
+extern tree loop_niter_by_eval (struct loop *, edge);
+extern tree find_loop_niter_by_eval (struct loop *, edge *);
+extern void estimate_numbers_of_iterations (struct loops *);
+extern tree can_count_iv_in_wider_type (struct loop *, tree, tree, tree, tree);
+extern void free_numbers_of_iterations_estimates (struct loops *);
+
/* In tree-flow-inline.h */
static inline int phi_arg_from_edge (tree, edge);
static inline bool may_propagate_copy (tree, tree);
@@ -612,6 +633,8 @@ extern void add_stmt_to_eh_region (tree,
extern bool remove_stmt_from_eh_region (tree);
extern bool maybe_clean_eh_stmt (tree);
+extern tree can_count_iv_in_wider_type (struct loop *, tree, tree, tree, tree);
+
/* In tree-ssa-pre.c */
void add_to_value (tree, tree);
void debug_value_expressions (tree);
Index: tree-scalar-evolution.c
===================================================================
RCS file: tree-scalar-evolution.c
diff -N tree-scalar-evolution.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tree-scalar-evolution.c 30 Jun 2004 23:13:58 -0000
@@ -0,0 +1,2547 @@
+/* Scalar evolution detector.
+ Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+ Contributed by Sebastian Pop <s.pop@laposte.net>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
+
+/*
+ Description:
+
+ This pass analyzes the evolution of scalar variables in loop
+ structures. The algorithm is based on the SSA representation,
+ and on the loop hierarchy tree. This algorithm is not based on
+ the notion of versions of a variable, as it was the case for the
+ previous implementations of the scalar evolution algorithm, but
+ it assumes that each defined name is unique.
+
+ A short sketch of the algorithm is:
+
+ Given a scalar variable to be analyzed, follow the SSA edge to
+ its definition:
+
+ - When the definition is a MODIFY_EXPR: if the right hand side
+ (RHS) of the definition cannot be statically analyzed, the answer
+ of the analyzer is: "don't know".
+ Otherwise, for all the variables that are not yet analyzed in the
+ RHS, try to determine their evolution, and finally try to
+ evaluate the operation of the RHS that gives the evolution
+ function of the analyzed variable.
+
+ - When the definition is a condition-phi-node: determine the
+ evolution function for all the branches of the phi node, and
+ finally merge these evolutions (see chrec_merge).
+
+ - When the definition is a loop-phi-node: determine its initial
+ condition, that is the SSA edge defined in an outer loop, and
+ keep it symbolic. Then determine the SSA edges that are defined
+ in the body of the loop. Follow the inner edges until ending on
+ another loop-phi-node of the same analyzed loop. If the reached
+ loop-phi-node is not the starting loop-phi-node, then we keep
+ this definition under a symbolic form. If the reached
+ loop-phi-node is the same as the starting one, then we compute a
+ symbolic stride on the return path. The result is then the
+ symbolic chrec {initial_condition, +, symbolic_stride}_loop.
+
+ Examples:
+
+ Example 1: Illustration of the basic algorithm.
+
+ | a = 3
+ | loop_1
+ | b = phi (a, c)
+ | c = b + 1
+ | if (c > 10) exit_loop
+ | endloop
+
+ Suppose that we want to know the number of iterations of the
+ loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
+ ask the scalar evolution analyzer two questions: what's the
+ scalar evolution (scev) of "c", and what's the scev of "10". For
+ "10" the answer is "10" since it is a scalar constant. For the
+ scalar variable "c", it follows the SSA edge to its definition,
+ "c = b + 1", and then asks again what's the scev of "b".
+ Following the SSA edge, we end on a loop-phi-node "b = phi (a,
+ c)", where the initial condition is "a", and the inner loop edge
+ is "c". The initial condition is kept under a symbolic form (it
+ may be the case that the copy constant propagation has done its
+ work and we end with the constant "3" as one of the edges of the
+ loop-phi-node). The update edge is followed to the end of the
+ loop, and until reaching again the starting loop-phi-node: b -> c
+ -> b. At this point we have drawn a path from "b" to "b" from
+ which we compute the stride in the loop: in this example it is
+ "+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
+ that the scev for "b" is known, it is possible to compute the
+ scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
+ determine the number of iterations in the loop_1, we have to
+ instantiate_parameters ({a + 1, +, 1}_1), that gives after some
+ more analysis the scev {4, +, 1}_1, or in other words, this is
+ the function "f (x) = x + 4", where x is the iteration count of
+ the loop_1. Now we have to solve the inequality "x + 4 > 10",
+ and take the smallest iteration number for which the loop is
+ exited: x = 7. This loop runs from x = 0 to x = 7, and in total
+ there are 8 iterations. In terms of loop normalization, we have
+ created a variable that is implicitly defined, "x" or just "_1",
+ and all the other analyzed scalars of the loop are defined in
+ function of this variable:
+
+ a -> 3
+ b -> {3, +, 1}_1
+ c -> {4, +, 1}_1
+
+ or in terms of a C program:
+
+ | a = 3
+ | for (x = 0; x <= 7; x++)
+ | {
+ | b = x + 3
+ | c = x + 4
+ | }
+
+ Example 2: Illustration of the algorithm on nested loops.
+
+ | loop_1
+ | a = phi (1, b)
+ | c = a + 2
+ | loop_2 10 times
+ | b = phi (c, d)
+ | d = b + 3
+ | endloop
+ | endloop
+
+ For analyzing the scalar evolution of "a", the algorithm follows
+ the SSA edge into the loop's body: "a -> b". "b" is an inner
+ loop-phi-node, and its analysis as in Example 1, gives:
+
+ b -> {c, +, 3}_2
+ d -> {c + 3, +, 3}_2
+
+ Following the SSA edge for the initial condition, we end on "c = a
+ + 2", and then on the starting loop-phi-node "a". From this point,
+ the loop stride is computed: back on "c = a + 2" we get a "+2" in
+ the loop_1, then on the loop-phi-node "b" we compute the overall
+ effect of the inner loop that is "b = c + 30", and we get a "+30"
+ in the loop_1. That means that the overall stride in loop_1 is
+ equal to "+32", and the result is:
+
+ a -> {1, +, 32}_1
+ c -> {3, +, 32}_1
+
+ Example 3: Higher degree polynomials.
+
+ | loop_1
+ | a = phi (2, b)
+ | c = phi (5, d)
+ | b = a + 1
+ | d = c + a
+ | endloop
+
+ a -> {2, +, 1}_1
+ b -> {3, +, 1}_1
+ c -> {5, +, a}_1
+ d -> {5 + a, +, a}_1
+
+ instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
+ instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
+
+ Example 4: Lucas, Fibonacci, or mixers in general.
+
+ | loop_1
+ | a = phi (1, b)
+ | c = phi (3, d)
+ | b = c
+ | d = c + a
+ | endloop
+
+ a -> (1, c)_1
+ c -> {3, +, a}_1
+
+ The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
+ following semantics: during the first iteration of the loop_1, the
+ variable contains the value 1, and then it contains the value "c".
+ Note that this syntax is close to the syntax of the loop-phi-node:
+ "a -> (1, c)_1" vs. "a = phi (1, c)".
+
+ The symbolic chrec representation contains all the semantics of the
+ original code. What is more difficult is to use this information.
+
+ Example 5: Flip-flops, or exchangers.
+
+ | loop_1
+ | a = phi (1, b)
+ | c = phi (3, d)
+ | b = c
+ | d = a
+ | endloop
+
+ a -> (1, c)_1
+ c -> (3, a)_1
+
+ Based on these symbolic chrecs, it is possible to refine this
+ information into the more precise PERIODIC_CHRECs:
+
+ a -> |1, 3|_1
+ c -> |3, 1|_1
+
+ This transformation is not yet implemented.
+
+ Further readings:
+
+ You can find a more detailed description of the algorithm in:
+ http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
+ http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
+ this is a preliminary report and some of the details of the
+ algorithm have changed. I'm working on a research report that
+ updates the description of the algorithms to reflect the design
+ choices used in this implementation.
+
+ A set of slides show a high level overview of the algorithm and run
+ an example through the scalar evolution analyzer:
+ http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
+
+ The slides that I have presented at the GCC Summit'04 are available
+ at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "errors.h"
+#include "ggc.h"
+#include "tree.h"
+
+/* These RTL headers are needed for basic-block.h. */
+#include "rtl.h"
+#include "basic-block.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "timevar.h"
+#include "cfgloop.h"
+#include "tree-chrec.h"
+#include "tree-scalar-evolution.h"
+#include "tree-pass.h"
+#include "flags.h"
+
+static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
+static tree resolve_mixers (struct loop *, 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;
+ tree chrec;
+};
+
+/* Counters for the scev database. */
+static unsigned nb_set_scev = 0;
+static unsigned nb_get_scev = 0;
+
+/* The following trees are unique elements. Thus the comparison of
+ another element to these elements should be done on the pointer to
+ these trees, and not on their value. */
+
+/* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
+tree chrec_not_analyzed_yet;
+
+/* Reserved to the cases where the analyzer has detected an
+ undecidable property at compile time. */
+tree chrec_dont_know;
+
+/* When the analyzer has detected that a property will never
+ happen, then it qualifies it with chrec_known. */
+tree chrec_known;
+
+static bitmap already_instantiated;
+
+static htab_t scalar_evolution_info;
+
+
+/* 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 = xmalloc (sizeof (struct scev_info_str));
+ res->var = var;
+ res->chrec = chrec_not_analyzed_yet;
+
+ return res;
+}
+
+/* Computes a hash function for database element ELT. */
+
+static hashval_t
+hash_scev_info (const void *elt)
+{
+ return SSA_NAME_VERSION (((struct scev_info_str *) elt)->var);
+}
+
+/* Compares database elements E1 and E2. */
+
+static int
+eq_scev_info (const void *e1, const void *e2)
+{
+ const struct scev_info_str *elt1 = e1;
+ const struct scev_info_str *elt2 = e2;
+
+ return elt1->var == elt2->var;
+}
+
+/* Deletes database element E. */
+
+static void
+del_scev_info (void *e)
+{
+ free (e);
+}
+
+/* Get the index corresponding to VAR in the current LOOP. If
+ it's the first time we ask for this VAR, then we return
+ chrec_not_analysed_yet for this VAR and return its index. */
+
+static tree *
+find_var_scev_info (tree var)
+{
+ struct scev_info_str *res;
+ struct scev_info_str tmp;
+ PTR *slot;
+
+ tmp.var = var;
+ slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
+
+ if (!*slot)
+ *slot = new_scev_info_str (var);
+ res = *slot;
+
+ return &res->chrec;
+}
+
+/* Tries to express CHREC in wider type TYPE. */
+
+tree
+count_ev_in_wider_type (tree type, tree chrec)
+{
+ tree base, step;
+ struct loop *loop;
+
+ if (!evolution_function_is_affine_p (chrec))
+ return fold_convert (type, chrec);
+
+ base = CHREC_LEFT (chrec);
+ step = CHREC_RIGHT (chrec);
+ loop = loop_from_num (current_loops, CHREC_VARIABLE (chrec));
+
+ /* TODO -- if we knew the statement at that the conversion occurs,
+ we could pass it to can_count_iv_in_wider_type and get a better
+ result. */
+ step = can_count_iv_in_wider_type (loop, type, base, step, NULL_TREE);
+ if (!step)
+ return fold_convert (type, chrec);
+ base = chrec_convert (type, base);
+
+ return build_polynomial_chrec (CHREC_VARIABLE (chrec),
+ base, step);
+}
+
+/* Determines whether the chrec contains symbolic names defined in
+ LOOP_NB. */
+
+bool
+chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb)
+{
+ if (chrec == NULL_TREE)
+ return false;
+
+ if (TREE_INVARIANT (chrec))
+ return false;
+
+ if (TREE_CODE (chrec) == VAR_DECL
+ || TREE_CODE (chrec) == PARM_DECL
+ || TREE_CODE (chrec) == FUNCTION_DECL
+ || TREE_CODE (chrec) == LABEL_DECL
+ || TREE_CODE (chrec) == RESULT_DECL
+ || TREE_CODE (chrec) == FIELD_DECL)
+ return true;
+
+ if (TREE_CODE (chrec) == SSA_NAME)
+ {
+ tree def = SSA_NAME_DEF_STMT (chrec);
+ struct loop *def_loop = loop_of_stmt (def);
+ struct loop *loop = loop_from_num (current_loops, loop_nb);
+
+ if (def_loop == NULL)
+ return false;
+
+ if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
+ return true;
+
+ return false;
+ }
+
+ switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
+ {
+ case 3:
+ if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2),
+ loop_nb))
+ return true;
+
+ case 2:
+ if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1),
+ loop_nb))
+ return true;
+
+ case 1:
+ if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0),
+ loop_nb))
+ return true;
+
+ default:
+ return false;
+ }
+}
+
+
+
+/* This section contains the interface to the SSA IR. */
+
+/* This function determines whether PHI is a loop-phi-node. Otherwise
+ it is a condition-phi-node. */
+
+static bool
+loop_phi_node_p (tree phi)
+{
+ /* 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);
+}
+
+/* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
+ In general, in the case of multivariate evolutions we want to get
+ the evolution in different loops. LOOP specifies the level for
+ which to get the evolution.
+
+ Example:
+
+ | for (j = 0; j < 100; j++)
+ | {
+ | for (k = 0; k < 100; k++)
+ | {
+ | i = k + j; - Here the value of i is a function of j, k.
+ | }
+ | ... = i - Here the value of i is a function of j.
+ | }
+ | ... = i - Here the value of i is a scalar.
+
+ Example:
+
+ | i_0 = ...
+ | loop_1 10 times
+ | i_1 = phi (i_0, i_2)
+ | i_2 = i_1 + 2
+ | endloop
+
+ This loop has the same effect as:
+ LOOP_1 has the same effect as:
+
+ | i_1 = i_0 + 20
+
+ The overall effect of the loop, "i_0 + 20" in the previous example,
+ is obtained by passing in the parameters: LOOP = 1,
+ EVOLUTION_FN = {i_0, +, 2}_1.
+*/
+
+static tree
+compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
+{
+ bool val = false;
+
+ if (evolution_fn == chrec_dont_know)
+ return chrec_dont_know;
+
+ else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
+ {
+ if (CHREC_VARIABLE (evolution_fn) >= loop_num (loop))
+ {
+ struct loop *inner_loop =
+ loop_from_num (current_loops, CHREC_VARIABLE (evolution_fn));
+ tree nb_iter = number_of_iterations_in_loop (inner_loop);
+
+ if (nb_iter == chrec_dont_know)
+ return chrec_dont_know;
+ else
+ {
+ tree res;
+
+ /* 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,
+ fold_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 (inner_loop->num, evolution_fn, nb_iter);
+
+ /* Continue the computation until ending on a parent of LOOP. */
+ return compute_overall_effect_of_inner_loop (loop, res);
+ }
+ }
+ else
+ return evolution_fn;
+ }
+
+ /* If the evolution function is an invariant, there is nothing to do. */
+ else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
+ return evolution_fn;
+
+ else
+ return chrec_dont_know;
+}
+
+
+
+/* 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 POLYNOMIAL_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)));
+
+ if (chrec_contains_undetermined (nb_iter))
+ return false;
+
+ nb_iter = chrec_fold_minus
+ (chrec_type (nb_iter), nb_iter,
+ fold_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,
+ fold_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;
+ }
+}
+
+/* Associate CHREC to SCALAR. */
+
+static void
+set_scalar_evolution (tree scalar, tree chrec)
+{
+ tree *scalar_info;
+
+ if (TREE_CODE (scalar) != SSA_NAME)
+ return;
+
+ scalar_info = find_var_scev_info (scalar);
+
+ if (dump_file)
+ {
+ if (dump_flags & TDF_DETAILS)
+ {
+ fprintf (dump_file, "(set_scalar_evolution \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");
+ }
+ if (dump_flags & TDF_STATS)
+ nb_set_scev++;
+ }
+
+ *scalar_info = chrec;
+}
+
+/* Retrieve the chrec associated to SCALAR in the LOOP. */
+
+static tree
+get_scalar_evolution (tree scalar)
+{
+ tree res;
+
+ if (dump_file)
+ {
+ if (dump_flags & TDF_DETAILS)
+ {
+ fprintf (dump_file, "(get_scalar_evolution \n");
+ fprintf (dump_file, " (scalar = ");
+ print_generic_expr (dump_file, scalar, 0);
+ fprintf (dump_file, ")\n");
+ }
+ if (dump_flags & TDF_STATS)
+ nb_get_scev++;
+ }
+
+ switch (TREE_CODE (scalar))
+ {
+ case SSA_NAME:
+ res = *find_var_scev_info (scalar);
+ break;
+
+ case REAL_CST:
+ case INTEGER_CST:
+ res = scalar;
+ break;
+
+ default:
+ res = chrec_not_analyzed_yet;
+ break;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (scalar_evolution = ");
+ print_generic_expr (dump_file, res, 0);
+ fprintf (dump_file, "))\n");
+ }
+
+ return res;
+}
+
+/* When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
+ evolution the expression TO_ADD, otherwise construct an evolution
+ part for this loop. */
+
+static tree
+add_to_evolution_1 (unsigned loop_nb,
+ tree chrec_before,
+ tree to_add)
+{
+ switch (TREE_CODE (chrec_before))
+ {
+ case POLYNOMIAL_CHREC:
+ if (CHREC_VARIABLE (chrec_before) <= loop_nb)
+ {
+ unsigned var;
+ tree left, right;
+ tree type = chrec_type (chrec_before);
+
+ /* When there is no evolution part in this loop, build it. */
+ if (CHREC_VARIABLE (chrec_before) < loop_nb)
+ {
+ var = loop_nb;
+ left = chrec_before;
+ right = fold_convert (type, integer_zero_node);
+ }
+ else
+ {
+ var = CHREC_VARIABLE (chrec_before);
+ left = CHREC_LEFT (chrec_before);
+ right = CHREC_RIGHT (chrec_before);
+ }
+
+ return build_polynomial_chrec
+ (var, left, chrec_fold_plus (type, right, to_add));
+ }
+ else
+ /* Search the evolution in LOOP_NB. */
+ return build_polynomial_chrec
+ (CHREC_VARIABLE (chrec_before),
+ add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add),
+ CHREC_RIGHT (chrec_before));
+
+ default:
+ /* These nodes do not depend on a loop. */
+ if (chrec_before == chrec_dont_know)
+ return chrec_dont_know;
+ return build_polynomial_chrec (loop_nb, chrec_before, to_add);
+ }
+}
+
+/* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
+ of LOOP_NB.
+
+ Description (provided for completeness, for those who read code in
+ a plane, and for my poor 62 bytes brain that would have forgotten
+ all this in the next two or three months):
+
+ The algorithm of translation of programs from the SSA representation
+ into the chrecs syntax is based on a pattern matching. After having
+ reconstructed the overall tree expression for a loop, there are only
+ two cases that can arise:
+
+ 1. a = loop-phi (init, a + expr)
+ 2. a = loop-phi (init, expr)
+
+ where EXPR is either a scalar constant with respect to the analyzed
+ loop (this is a degree 0 polynomial), or an expression containing
+ other loop-phi definitions (these are higher degree polynomials).
+
+ Examples:
+
+ 1.
+ | init = ...
+ | loop_1
+ | a = phi (init, a + 5)
+ | endloop
+
+ 2.
+ | inita = ...
+ | initb = ...
+ | loop_1
+ | a = phi (inita, 2 * b + 3)
+ | b = phi (initb, b + 1)
+ | endloop
+
+ For the first case, the semantics of the SSA representation is:
+
+ | a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
+
+ that is, there is a loop index "x" that determines the scalar value
+ of the variable during the loop execution. During the first
+ iteration, the value is that of the initial condition INIT, while
+ during the subsequent iterations, it is the sum of the initial
+ condition with the sum of all the values of EXPR from the initial
+ iteration to the before last considered iteration.
+
+ For the second case, the semantics of the SSA program is:
+
+ | a (x) = init, if x = 0;
+ | expr (x - 1), otherwise.
+
+ The second case corresponds to the PEELED_CHREC, whose syntax is
+ close to the syntax of a loop-phi-node:
+
+ | phi (init, expr) vs. (init, expr)_x
+
+ The proof of the translation algorithm for the first case is a
+ proof by structural induction based on the degree of EXPR.
+
+ Degree 0:
+ When EXPR is a constant with respect to the analyzed loop, or in
+ other words when EXPR is a polynomial of degree 0, the evolution of
+ the variable A in the loop is an affine function with an initial
+ condition INIT, and a step EXPR. In order to show this, we start
+ from the semantics of the SSA representation:
+
+ f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
+
+ and since "expr (j)" is a constant with respect to "j",
+
+ f (x) = init + x * expr
+
+ Finally, based on the semantics of the pure sum chrecs, by
+ identification we get the corresponding chrecs syntax:
+
+ f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
+ f (x) -> {init, +, expr}_x
+
+ Higher degree:
+ Suppose that EXPR is a polynomial of degree N with respect to the
+ analyzed loop_x for which we have already determined that it is
+ written under the chrecs syntax:
+
+ | expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
+
+ We start from the semantics of the SSA program:
+
+ | f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
+ |
+ | f (x) = init + \sum_{j = 0}^{x - 1}
+ | (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
+ |
+ | f (x) = init + \sum_{j = 0}^{x - 1}
+ | \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
+ |
+ | f (x) = init + \sum_{k = 0}^{n - 1}
+ | (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
+ |
+ | f (x) = init + \sum_{k = 0}^{n - 1}
+ | (b_k * \binom{x}{k + 1})
+ |
+ | f (x) = init + b_0 * \binom{x}{1} + ...
+ | + b_{n-1} * \binom{x}{n}
+ |
+ | f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
+ | + b_{n-1} * \binom{x}{n}
+ |
+
+ And finally from the definition of the chrecs syntax, we identify:
+ | f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
+
+ This shows the mechanism that stands behind the add_to_evolution
+ function. An important point is that the use of symbolic
+ parameters avoids the need of an analysis schedule.
+
+ Example:
+
+ | inita = ...
+ | initb = ...
+ | loop_1
+ | a = phi (inita, a + 2 + b)
+ | b = phi (initb, b + 1)
+ | endloop
+
+ When analyzing "a", the algorithm keeps "b" symbolically:
+
+ | a -> {inita, +, 2 + b}_1
+
+ Then, after instantiation, the analyzer ends on the evolution:
+
+ | a -> {inita, +, 2 + initb, +, 1}_1
+
+*/
+
+static tree
+add_to_evolution (unsigned loop_nb,
+ tree chrec_before,
+ enum tree_code code,
+ tree to_add)
+{
+ tree type = chrec_type (to_add);
+ tree res = NULL_TREE;
+
+ if (to_add == NULL_TREE)
+ return chrec_before;
+
+ /* TO_ADD is either a scalar, or a parameter. TO_ADD is not
+ instantiated at this point. */
+ if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
+ /* This should not happen. */
+ return chrec_dont_know;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(add_to_evolution \n");
+ fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
+ fprintf (dump_file, " (chrec_before = ");
+ print_generic_expr (dump_file, chrec_before, 0);
+ fprintf (dump_file, ")\n (to_add = ");
+ print_generic_expr (dump_file, to_add, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ if (code == MINUS_EXPR)
+ to_add = chrec_fold_multiply (type, to_add,
+ fold_convert (type, integer_minus_one_node));
+
+ res = add_to_evolution_1 (loop_nb, chrec_before, to_add);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (res = ");
+ print_generic_expr (dump_file, res, 0);
+ fprintf (dump_file, "))\n");
+ }
+
+ return res;
+}
+
+/* Helper function. */
+
+static inline tree
+set_nb_iterations_in_loop (struct loop *loop,
+ tree res)
+{
+ /* After the loop copy headers has transformed the code, each loop
+ runs at least once. */
+ res = chrec_fold_plus (chrec_type (res), res, integer_one_node);
+ /* FIXME HWI: However we want to store one iteration less than the
+ count of the loop in order to be compatible with the other
+ nb_iter computations in loop-iv. This also allows the
+ representation of nb_iters that are equal to MAX_INT. */
+ if ((TREE_CODE (res) == INTEGER_CST && TREE_INT_CST_LOW (res) == 0)
+ || TREE_OVERFLOW (res))
+ res = chrec_dont_know;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (set_nb_iterations_in_loop = ");
+ print_generic_expr (dump_file, res, 0);
+ fprintf (dump_file, "))\n");
+ }
+
+ loop->nb_iterations = res;
+ return res;
+}
+
+
+
+/* This section selects the loops that will be good candidates for the
+ scalar evolution analysis.
+
+ Note: This section will be rewritten to expose a better interface
+ to other client passes. For the moment, greedily select all the
+ loop nests we could analyze. */
+
+/* Determine whether it is possible to analyze this condition
+ expression. */
+
+static bool
+analyzable_condition (tree expr)
+{
+ tree condition;
+
+ if (TREE_CODE (expr) != COND_EXPR)
+ return false;
+
+ condition = TREE_OPERAND (expr, 0);
+
+ switch (TREE_CODE (condition))
+ {
+ case SSA_NAME:
+ /* Volatile expressions are not analyzable. */
+ if (TREE_THIS_VOLATILE (SSA_NAME_VAR (condition)))
+ return false;
+ return true;
+
+ case LT_EXPR:
+ case LE_EXPR:
+ case GT_EXPR:
+ case GE_EXPR:
+ case EQ_EXPR:
+ case NE_EXPR:
+ {
+ tree opnd0, opnd1;
+
+ opnd0 = TREE_OPERAND (condition, 0);
+ opnd1 = TREE_OPERAND (condition, 1);
+
+ if (TREE_CODE (opnd0) == SSA_NAME
+ && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd0)))
+ return false;
+
+ if (TREE_CODE (opnd1) == SSA_NAME
+ && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd1)))
+ return false;
+
+ return true;
+ }
+
+ default:
+ return false;
+ }
+
+ return false;
+}
+
+/* For a loop with a single exit edge, determine the COND_EXPR that
+ guards the exit edge. If the expression is too difficult to
+ analyze, then give up. */
+
+tree
+get_loop_exit_condition (struct loop *loop)
+{
+ tree res = NULL_TREE;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(get_loop_exit_condition \n ");
+
+ if (loop_exit_edges (loop))
+ {
+ edge exit_edge;
+ tree expr;
+
+ exit_edge = loop_exit_edge (loop, 0);
+ expr = last_stmt (edge_source (exit_edge));
+
+ if (analyzable_condition (expr))
+ res = expr;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ print_generic_expr (dump_file, res, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ return res;
+}
+
+/* Recursively determine and enqueue the exit conditions for a loop. */
+
+static void
+get_exit_conditions_rec (struct loop *loop,
+ varray_type *exit_conditions)
+{
+ if (!loop)
+ return;
+
+ /* Recurse on the inner loops, then on the next (sibling) loops. */
+ get_exit_conditions_rec (inner_loop (loop), exit_conditions);
+ get_exit_conditions_rec (next_loop (loop), exit_conditions);
+
+ flow_loop_scan (loop, LOOP_EXIT_EDGES);
+ if (loop_num_exits (loop) == 1)
+ {
+ tree loop_condition = get_loop_exit_condition (loop);
+
+ if (loop_condition)
+ VARRAY_PUSH_TREE (*exit_conditions, loop_condition);
+ }
+}
+
+/* Select the candidate loop nests for the analysis. This function
+ initializes the EXIT_CONDITIONS array. The vector EXIT_CONDITIONS is
+ initialized in a loop-depth-first order, ie. the inner loops
+ conditions appear before the outer. This property of the
+ EXIT_CONDITIONS list is exploited by the evolution analyzer. */
+
+static void
+select_loops_exit_conditions (struct loops *loops,
+ varray_type *exit_conditions)
+{
+ struct loop *function_body = loops->parray[0];
+
+ get_exit_conditions_rec (inner_loop (function_body), exit_conditions);
+}
+
+
+/* Depth first search algorithm. */
+
+static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
+
+/* 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)
+{
+ bool res = false;
+ tree rhs0, rhs1;
+ tree type_rhs = TREE_TYPE (rhs);
+
+ /* The RHS is one of the following cases:
+ - an SSA_NAME,
+ - an INTEGER_CST,
+ - a PLUS_EXPR,
+ - a MINUS_EXPR,
+ - other cases are not yet handled.
+ */
+ switch (TREE_CODE (rhs))
+ {
+ case NOP_EXPR:
+ /* This assignment is under the form "a_1 = (cast) rhs. */
+ res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi,
+ evolution_of_loop);
+ *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop);
+ break;
+
+ case INTEGER_CST:
+ /* This assignment is under the form "a_1 = 7". */
+ res = false;
+ break;
+
+ 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:
+ /* This case is under the form "rhs0 + rhs1". */
+ rhs0 = TREE_OPERAND (rhs, 0);
+ rhs1 = TREE_OPERAND (rhs, 1);
+ STRIP_TYPE_NOPS (rhs0);
+ STRIP_TYPE_NOPS (rhs1);
+
+ if (TREE_CODE (rhs0) == SSA_NAME)
+ {
+ if (TREE_CODE (rhs1) == SSA_NAME)
+ {
+ /* 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);
+ }
+ }
+
+ else
+ {
+ /* 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);
+ }
+ }
+
+ else if (TREE_CODE (rhs1) == SSA_NAME)
+ {
+ /* 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);
+ }
+
+ else
+ /* Otherwise, match an assignment under the form:
+ "a = ... + ...". */
+ /* And there is nothing to do. */
+ res = false;
+
+ break;
+
+ case MINUS_EXPR:
+ /* This case is under the form "opnd0 = rhs0 - rhs1". */
+ rhs0 = TREE_OPERAND (rhs, 0);
+ rhs1 = TREE_OPERAND (rhs, 1);
+ STRIP_TYPE_NOPS (rhs0);
+ STRIP_TYPE_NOPS (rhs1);
+
+ if (TREE_CODE (rhs0) == SSA_NAME)
+ {
+ if (TREE_CODE (rhs1) == SSA_NAME)
+ {
+ /* 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,
+ fold_convert (type_rhs,
+ integer_minus_one_node)),
+ PLUS_EXPR, rhs0);
+ }
+ }
+
+ else
+ {
+ /* 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);
+ }
+ }
+
+ else if (TREE_CODE (rhs1) == SSA_NAME)
+ {
+ /* 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,
+ fold_convert (type_rhs, integer_minus_one_node)),
+ PLUS_EXPR, rhs0);
+ }
+
+ else
+ /* Otherwise, match an assignment under the form:
+ "a = ... - ...". */
+ /* And there is nothing to do. */
+ res = false;
+
+ break;
+
+ case MULT_EXPR:
+ /* This case is under the form "opnd0 = rhs0 * rhs1". */
+ rhs0 = TREE_OPERAND (rhs, 0);
+ rhs1 = TREE_OPERAND (rhs, 1);
+ STRIP_TYPE_NOPS (rhs0);
+ STRIP_TYPE_NOPS (rhs1);
+
+ if (TREE_CODE (rhs0) == SSA_NAME)
+ {
+ if (TREE_CODE (rhs1) == SSA_NAME)
+ {
+ /* 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 = chrec_dont_know;
+
+ else
+ {
+ res = follow_ssa_edge
+ (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
+ evolution_of_loop);
+
+ if (res)
+ *evolution_of_loop = chrec_dont_know;
+ }
+ }
+
+ else
+ {
+ /* 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 = chrec_dont_know;
+ }
+ }
+
+ else if (TREE_CODE (rhs1) == SSA_NAME)
+ {
+ /* 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 = chrec_dont_know;
+ }
+
+ else
+ /* Otherwise, match an assignment under the form:
+ "a = ... * ...". */
+ /* And there is nothing to do. */
+ res = false;
+
+ break;
+
+ default:
+ res = false;
+ break;
+ }
+
+ 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_dont_know;
+
+ /* 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_dont_know, 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
+ effect of the loop, and following the symbolic initial conditions,
+ it follows the edges in the parent loop. The inner loop is
+ 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 = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
+
+ /* Sometimes, the inner loop is too difficult to analyze, and the
+ result of the analysis is a symbolic parameter. */
+ if (ev == PHI_RESULT (loop_phi_node))
+ {
+ bool res = false;
+ int i;
+
+ for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
+ {
+ tree arg = PHI_ARG_DEF (loop_phi_node, i);
+ basic_block bb;
+
+ /* Follow the edges that exit the inner loop. */
+ bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
+ if (!flow_bb_inside_loop_p (loop, bb))
+ res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi,
+ evolution_of_loop);
+ }
+
+ /* If the path crosses this loop-phi, give up. */
+ if (res == true)
+ *evolution_of_loop = chrec_dont_know;
+
+ return res;
+ }
+
+ /* Otherwise, compute the overall effect of the inner loop. */
+ ev = compute_overall_effect_of_inner_loop (loop, ev);
+ 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);
+
+ default:
+ /* At this level of abstraction, the program is just a set
+ of MODIFY_EXPRs and PHI_NODEs. In principle there is no
+ other node to be handled. */
+ return false;
+ }
+}
+
+
+
+/* Given a LOOP_PHI_NODE, this function determines the evolution
+ function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
+
+static tree
+analyze_evolution_in_loop (tree loop_phi_node,
+ tree init_cond)
+{
+ 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))
+ {
+ fprintf (dump_file, "(analyze_evolution_in_loop \n");
+ fprintf (dump_file, " (loop_phi_node = ");
+ print_generic_expr (dump_file, loop_phi_node, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
+ {
+ 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
+ evolution is represented by a peeled chrec, ie. the
+ first iteration, EV_FN has the value INIT_COND, then
+ all the other iterations it has the value of ARG.
+ For the moment, PEELED_CHREC nodes are not built. */
+ if (!res)
+ ev_fn = chrec_dont_know;
+
+ /* 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);
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (evolution_function = ");
+ print_generic_expr (dump_file, evolution_function, 0);
+ fprintf (dump_file, "))\n");
+ }
+
+ return evolution_function;
+}
+
+/* Given a loop-phi-node, this function determines the initial
+ conditions of the variable on entry of the loop. When the CCP has
+ propagated constants into the loop-phi-node, the initial condition
+ is instantiated, otherwise the initial condition is kept symbolic.
+ This analyzer does not analyze the evolution outside the current
+ loop, and leaves this task to the on-demand tree reconstructor. */
+
+static tree
+analyze_initial_condition (tree loop_phi_node)
+{
+ 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))
+ {
+ fprintf (dump_file, "(analyze_initial_condition \n");
+ fprintf (dump_file, " (loop_phi_node = \n");
+ print_generic_expr (dump_file, loop_phi_node, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ 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_dont_know;
+ break;
+ }
+
+ init_cond = chrec_merge (init_cond, branch);
+ }
+
+ /* Ooops -- a loop without an entry??? */
+ if (init_cond == chrec_not_analyzed_yet)
+ init_cond = chrec_dont_know;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (init_cond = ");
+ print_generic_expr (dump_file, init_cond, 0);
+ fprintf (dump_file, "))\n");
+ }
+
+ return init_cond;
+}
+
+/* Analyze the scalar evolution for LOOP_PHI_NODE. */
+
+static tree
+interpret_loop_phi (struct loop *loop, tree loop_phi_node)
+{
+ tree res;
+ struct loop *phi_loop = loop_of_stmt (loop_phi_node);
+ tree init_cond;
+
+ if (phi_loop != loop)
+ {
+ struct loop *subloop;
+ tree evolution_fn = analyze_scalar_evolution
+ (phi_loop, PHI_RESULT (loop_phi_node));
+
+ /* Dive one level deeper. */
+ subloop = superloop_at_depth (phi_loop, loop->depth + 1);
+
+ /* Interpret the subloop. */
+ res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
+ return res;
+ }
+
+ /* Otherwise really interpret the loop phi. */
+ init_cond = analyze_initial_condition (loop_phi_node);
+ res = analyze_evolution_in_loop (loop_phi_node, init_cond);
+
+ return res;
+}
+
+/* This function merges the branches of a condition-phi-node,
+ contained in the outermost loop, and whose arguments are already
+ 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_dont_know;
+ break;
+ }
+
+ branch_chrec = analyze_scalar_evolution
+ (loop, PHI_ARG_DEF (condition_phi, i));
+
+ res = chrec_merge (res, branch_chrec);
+ }
+
+ return res;
+}
+
+/* Interpret the right hand side of a modify_expr OPND1. If we didn't
+ analyzed this node before, follow the definitions until ending
+ either on an analyzed modify_expr, or on a loop-phi-node. On the
+ return path, this function propagates evolutions (ala constant copy
+ propagation). OPND1 is not a GIMPLE expression because we could
+ 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_minus (type, fold_convert (type, integer_zero_node),
+ 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:
+ res = chrec_dont_know;
+ break;
+ }
+
+ return res;
+}
+
+
+
+/* This section contains all the entry points:
+ - number_of_iterations_in_loop,
+ - analyze_scalar_evolution,
+ - instantiate_parameters.
+*/
+
+/* Compute the evolution function in WRTO_LOOP, the nearest common
+ ancestor of DEF_LOOP and USE_LOOP. */
+
+static tree
+compute_scalar_evolution_in_loop (struct loop *wrto_loop,
+ struct loop *def_loop,
+ tree ev)
+{
+ tree res;
+ if (def_loop == wrto_loop)
+ return ev;
+
+ def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
+ res = compute_overall_effect_of_inner_loop (def_loop, ev);
+
+ return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
+}
+
+/* Helper recursive function. */
+
+static tree
+analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
+{
+ tree def, type = TREE_TYPE (var);
+ basic_block bb;
+ struct loop *def_loop;
+
+ if (loop == NULL)
+ return chrec_dont_know;
+
+ if (TREE_CODE (var) != SSA_NAME)
+ return interpret_rhs_modify_expr (loop, var, type);
+
+ def = SSA_NAME_DEF_STMT (var);
+ bb = bb_for_stmt (def);
+ def_loop = bb ? bb->loop_father : NULL;
+
+ if (bb == NULL
+ || !flow_bb_inside_loop_p (loop, bb))
+ {
+ /* Keep the symbolic form. */
+ res = var;
+ goto set_and_end;
+ }
+
+ if (res != chrec_not_analyzed_yet)
+ {
+ if (loop != bb->loop_father)
+ res = compute_scalar_evolution_in_loop
+ (find_common_loop (loop, bb->loop_father), bb->loop_father, res);
+
+ goto set_and_end;
+ }
+
+ if (loop != def_loop)
+ {
+ res = analyze_scalar_evolution_1 (def_loop, var, chrec_not_analyzed_yet);
+ res = compute_scalar_evolution_in_loop (loop, def_loop, res);
+
+ goto set_and_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_dont_know;
+ break;
+ }
+
+ set_and_end:
+
+ /* Keep the symbolic form. */
+ if (res == chrec_dont_know)
+ res = var;
+
+ if (loop == def_loop)
+ set_scalar_evolution (var, res);
+
+ return res;
+}
+
+/* Entry point for the scalar evolution analyzer.
+ Analyzes and returns the scalar evolution of the ssa_name VAR.
+ LOOP_NB is the identifier number of the loop in which the variable
+ is used.
+
+ Example of use: having a pointer VAR to a SSA_NAME node, STMT a
+ pointer to the statement that uses this variable, in order to
+ determine the evolution function of the variable, use the following
+ calls:
+
+ unsigned loop_nb = loop_num (loop_of_stmt (stmt));
+ tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
+ tree chrec_instantiated = instantiate_parameters
+ (loop_nb, chrec_with_symbols);
+*/
+
+tree
+analyze_scalar_evolution (struct loop *loop, tree var)
+{
+ tree res;
+
+ 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, var, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
+
+ if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
+ res = var;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+
+ return res;
+}
+
+/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
+ WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
+ of VERSION). */
+
+static tree
+analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
+ tree version)
+{
+ bool val = false;
+ tree ev = version;
+
+ while (1)
+ {
+ ev = analyze_scalar_evolution (use_loop, ev);
+ ev = resolve_mixers (use_loop, ev);
+
+ if (use_loop == wrto_loop)
+ return ev;
+
+ /* If the value of the use changes in the inner loop, we cannot express
+ its value in the outer loop (we might try to return interval chrec,
+ but we do not have a user for it anyway) */
+ if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
+ || !val)
+ return chrec_dont_know;
+
+ use_loop = use_loop->outer;
+ }
+}
+
+/* Analyze all the parameters of the chrec that were left under a symbolic form,
+ with respect to LOOP. CHREC is the chrec to instantiate. If
+ ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
+ outer loop chrecs is done. */
+
+static tree
+instantiate_parameters_1 (struct loop *loop, tree chrec,
+ bool allow_superloop_chrecs)
+{
+ tree res, op0, op1, op2;
+ basic_block def_bb;
+ struct loop *def_loop;
+
+ if (chrec == NULL_TREE
+ || automatically_generated_chrec_p (chrec))
+ return chrec;
+
+ if (is_gimple_min_invariant (chrec))
+ return chrec;
+
+ switch (TREE_CODE (chrec))
+ {
+ case SSA_NAME:
+ def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
+
+ /* A parameter (or loop invariant and we do not want to include
+ evolutions in outer loops), nothing to do. */
+ if (!def_bb
+ || (!allow_superloop_chrecs
+ && !flow_bb_inside_loop_p (loop, def_bb)))
+ return chrec;
+
+ /* 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:
+
+ | a_2 -> {0, +, 1, +, a_2}_1 */
+
+ if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
+ {
+ if (!flow_bb_inside_loop_p (loop, def_bb))
+ {
+ /* We may keep the loop invariant in symbolic form. */
+ return chrec;
+ }
+ else
+ {
+ /* Something with unknown behavior in LOOP. */
+ return chrec_dont_know;
+ }
+ }
+
+ def_loop = find_common_loop (loop, def_bb->loop_father);
+
+ /* If the analysis yields a parametric chrec, instantiate the
+ result again. Avoid the cyclic instantiation in mixers. */
+ bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
+ res = analyze_scalar_evolution (def_loop, chrec);
+ res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs);
+ bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
+ return res;
+
+ case POLYNOMIAL_CHREC:
+ op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
+ allow_superloop_chrecs);
+ op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
+ allow_superloop_chrecs);
+ return build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
+
+ case PLUS_EXPR:
+ op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
+ allow_superloop_chrecs);
+ op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
+ allow_superloop_chrecs);
+ return chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
+
+ case MINUS_EXPR:
+ op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
+ allow_superloop_chrecs);
+ op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
+ allow_superloop_chrecs);
+ return chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
+
+ case MULT_EXPR:
+ op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
+ allow_superloop_chrecs);
+ op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
+ allow_superloop_chrecs);
+ return chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
+
+ case NOP_EXPR:
+ case CONVERT_EXPR:
+ case NON_LVALUE_EXPR:
+ op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
+ allow_superloop_chrecs);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
+ return chrec_convert (TREE_TYPE (chrec), op0);
+
+ case SCEV_NOT_KNOWN:
+ return chrec_dont_know;
+
+ case SCEV_KNOWN:
+ return chrec_known;
+
+ default:
+ break;
+ }
+
+ switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
+ {
+ case 3:
+ op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
+ allow_superloop_chrecs);
+ op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
+ allow_superloop_chrecs);
+ op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
+ allow_superloop_chrecs);
+ if (op0 == chrec_dont_know
+ || op1 == chrec_dont_know
+ || op2 == chrec_dont_know)
+ return chrec_dont_know;
+ return fold (build (TREE_CODE (chrec),
+ TREE_TYPE (chrec), op0, op1, op2));
+
+ case 2:
+ op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
+ allow_superloop_chrecs);
+ op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
+ allow_superloop_chrecs);
+ if (op0 == chrec_dont_know
+ || op1 == chrec_dont_know)
+ return chrec_dont_know;
+ return fold (build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1));
+
+ case 1:
+ op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
+ allow_superloop_chrecs);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+ return fold (build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0));
+
+ case 0:
+ return chrec;
+
+ default:
+ break;
+ }
+
+ /* Too complicated to handle. */
+ return chrec_dont_know;
+}
+
+/* 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;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(instantiate_parameters \n");
+ fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
+ fprintf (dump_file, " (chrec = ");
+ print_generic_expr (dump_file, chrec, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ res = instantiate_parameters_1 (loop, chrec, true);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (res = ");
+ print_generic_expr (dump_file, res, 0);
+ fprintf (dump_file, "))\n");
+ }
+
+ return res;
+}
+
+/* Similar to instantiate_parameters, but does not introduce the
+ evolutions in outer loops for LOOP invariants in CHREC. */
+
+static tree
+resolve_mixers (struct loop *loop, tree chrec)
+{
+ return instantiate_parameters_1 (loop, chrec, false);
+}
+
+/* Entry point for the analysis of the number of iterations pass.
+ This function tries to safely approximate the number of iterations
+ the loop will run. When this property is not decidable at compile
+ time, the result is chrec_dont_know: [-oo, +oo]. Otherwise the result is
+ a scalar or a symbolic parameter.
+
+ Example of analysis: suppose that the loop has an exit condition:
+
+ "if (b > 49) goto end_loop;"
+
+ and that in a previous analysis we have determined that the
+ variable 'b' has an evolution function:
+
+ "EF = {23, +, 5}_2".
+
+ When we evaluate the function at the point 5, i.e. the value of the
+ variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
+ and EF (6) = 53. In this case the value of 'b' on exit is '53' and
+ the loop body has been executed 6 times. */
+
+tree
+number_of_iterations_in_loop (struct loop *loop)
+{
+ tree res, type;
+ edge exit;
+ struct tree_niter_desc niter_desc;
+
+ /* Determine whether the number_of_iterations_in_loop has already
+ been computed. */
+ res = loop_nb_iterations (loop);
+ if (res)
+ return res;
+ res = chrec_dont_know;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "(number_of_iterations_in_loop\n");
+
+ if (!loop_exit_edges (loop))
+ goto end;
+ exit = loop_exit_edge (loop, 0);
+
+ if (!number_of_iterations_exit (loop, exit, &niter_desc))
+ goto end;
+
+ type = TREE_TYPE (niter_desc.niter);
+ if (integer_nonzerop (niter_desc.may_be_zero))
+ res = fold_convert (type, integer_zero_node);
+ else if (integer_zerop (niter_desc.may_be_zero))
+ res = niter_desc.niter;
+ else
+ res = chrec_dont_know;
+
+end:
+ return set_nb_iterations_in_loop (loop, res);
+}
+
+/* One of the drivers for testing the scalar evolutions analysis.
+ This function computes the number of iterations for all the loops
+ from the EXIT_CONDITIONS array. */
+
+static void
+number_of_iterations_for_all_loops (varray_type exit_conditions)
+{
+ unsigned int i;
+ unsigned nb_chrec_dont_know_loops = 0;
+ unsigned nb_static_loops = 0;
+
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
+ {
+ tree res = number_of_iterations_in_loop
+ (loop_of_stmt (VARRAY_TREE (exit_conditions, i)));
+ if (chrec_contains_undetermined (res))
+ nb_chrec_dont_know_loops++;
+ else
+ nb_static_loops++;
+ }
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "\n(\n");
+ fprintf (dump_file, "-----------------------------------------\n");
+ fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
+ fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
+ fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
+ fprintf (dump_file, "-----------------------------------------\n");
+ fprintf (dump_file, ")\n\n");
+
+ print_loop_ir (dump_file);
+ }
+}
+
+
+
+/* Counters for the stats. */
+
+struct chrec_stats
+{
+ unsigned nb_chrecs;
+ unsigned nb_affine;
+ unsigned nb_affine_multivar;
+ unsigned nb_higher_poly;
+ unsigned nb_chrec_dont_know;
+ unsigned nb_undetermined;
+};
+
+/* Reset the counters. */
+
+static inline void
+reset_chrecs_counters (struct chrec_stats *stats)
+{
+ stats->nb_chrecs = 0;
+ stats->nb_affine = 0;
+ stats->nb_affine_multivar = 0;
+ stats->nb_higher_poly = 0;
+ stats->nb_chrec_dont_know = 0;
+ stats->nb_undetermined = 0;
+}
+
+/* Dump the contents of a CHREC_STATS structure. */
+
+static void
+dump_chrecs_stats (FILE *file, struct chrec_stats *stats)
+{
+ fprintf (file, "\n(\n");
+ fprintf (file, "-----------------------------------------\n");
+ fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
+ fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
+ fprintf (file, "%d\tdegree greater than 2 polynomials\n",
+ stats->nb_higher_poly);
+ fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
+ fprintf (file, "-----------------------------------------\n");
+ fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
+ fprintf (file, "%d\twith undetermined coefficients\n",
+ stats->nb_undetermined);
+ fprintf (file, "-----------------------------------------\n");
+ fprintf (file, "%d\tchrecs in the scev database\n",
+ (int) htab_elements (scalar_evolution_info));
+ fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
+ fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
+ fprintf (file, "-----------------------------------------\n");
+ fprintf (file, ")\n\n");
+}
+
+/* Gather statistics about CHREC. */
+
+static void
+gather_chrec_stats (tree chrec, struct chrec_stats *stats)
+{
+ if (dump_file && (dump_flags & TDF_STATS))
+ {
+ fprintf (dump_file, "(classify_chrec ");
+ print_generic_expr (dump_file, chrec, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ stats->nb_chrecs++;
+
+ if (chrec == NULL_TREE)
+ {
+ stats->nb_undetermined++;
+ return;
+ }
+
+ switch (TREE_CODE (chrec))
+ {
+ case POLYNOMIAL_CHREC:
+ if (evolution_function_is_affine_p (chrec))
+ {
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " affine_univariate\n");
+ stats->nb_affine++;
+ }
+ else if (evolution_function_is_affine_multivariate_p (chrec))
+ {
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " affine_multivariate\n");
+ stats->nb_affine_multivar++;
+ }
+ else
+ {
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " higher_degree_polynomial\n");
+ stats->nb_higher_poly++;
+ }
+
+ break;
+
+ default:
+ break;
+ }
+
+ if (chrec_contains_undetermined (chrec))
+ {
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, " undetermined\n");
+ stats->nb_undetermined++;
+ }
+
+ if (dump_file && (dump_flags & TDF_STATS))
+ fprintf (dump_file, ")\n");
+}
+
+/* One of the drivers for testing the scalar evolutions analysis.
+ This function analyzes the scalar evolution of all the scalars
+ defined as loop phi nodes in one of the loops from the
+ EXIT_CONDITIONS array.
+
+ TODO Optimization: A loop is in canonical form if it contains only
+ a single scalar loop phi node. All the other scalars that have an
+ evolution in the loop are rewritten in function of this single
+ index. This allows the parallelization of the loop. */
+
+static void
+analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions)
+{
+ unsigned int i;
+ struct chrec_stats stats;
+
+ reset_chrecs_counters (&stats);
+
+ 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 (chrec, &stats);
+ }
+ }
+
+ if (dump_file && (dump_flags & TDF_STATS))
+ dump_chrecs_stats (dump_file, &stats);
+}
+
+/* Callback for htab_traverse, gathers information on chrecs in the
+ hashtable. */
+
+static int
+gather_stats_on_scev_database_1 (void **slot, void *stats)
+{
+ struct scev_info_str *entry = *slot;
+
+ gather_chrec_stats (entry->chrec, stats);
+
+ return 1;
+}
+
+/* Classify the chrecs of the whole database. */
+
+void
+gather_stats_on_scev_database (void)
+{
+ struct chrec_stats stats;
+
+ if (!dump_file)
+ return;
+
+ reset_chrecs_counters (&stats);
+
+ htab_traverse (scalar_evolution_info, gather_stats_on_scev_database_1,
+ &stats);
+
+ dump_chrecs_stats (dump_file, &stats);
+}
+
+
+
+/* Initializer. */
+
+static void
+initialize_scalar_evolutions_analyzer (void)
+{
+ /* The elements below are unique. */
+ if (chrec_dont_know == NULL_TREE)
+ {
+ chrec_not_analyzed_yet = NULL_TREE;
+ chrec_dont_know = make_node (SCEV_NOT_KNOWN);
+ chrec_known = make_node (SCEV_KNOWN);
+ TREE_TYPE (chrec_dont_know) = NULL_TREE;
+ TREE_TYPE (chrec_known) = NULL_TREE;
+ }
+}
+
+/* Initialize the analysis of scalar evolutions for LOOPS. */
+
+void
+scev_initialize (struct loops *loops)
+{
+ unsigned i;
+ current_loops = loops;
+
+ scalar_evolution_info = htab_create (100, hash_scev_info,
+ eq_scev_info, del_scev_info);
+ already_instantiated = BITMAP_XMALLOC ();
+
+ initialize_scalar_evolutions_analyzer ();
+
+ for (i = 1; i < loops->num; i++)
+ if (loops->parray[i])
+ {
+ flow_loop_scan (loops->parray[i], LOOP_EXIT_EDGES);
+ loops->parray[i]->nb_iterations = NULL_TREE;
+ }
+}
+
+/* Cleans up the information cached by the scalar evolutions analysis. */
+
+void
+scev_reset (void)
+{
+ unsigned i;
+ struct loop *loop;
+
+ htab_empty (scalar_evolution_info);
+ for (i = 1; i < current_loops->num; i++)
+ {
+ loop = current_loops->parray[i];
+ if (loop)
+ loop->nb_iterations = NULL_TREE;
+ }
+}
+
+/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
+ its BASE and STEP if possible. */
+
+bool
+simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step)
+{
+ basic_block bb = bb_for_stmt (stmt);
+ tree type, ev;
+
+ *base = NULL_TREE;
+ *step = NULL_TREE;
+
+ type = TREE_TYPE (op);
+ if (TREE_CODE (type) != INTEGER_TYPE
+ && TREE_CODE (type) != POINTER_TYPE)
+ return false;
+
+ ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op);
+ if (chrec_contains_undetermined (ev))
+ return false;
+
+ if (tree_does_not_contain_chrecs (ev)
+ && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
+ {
+ *base = ev;
+ return true;
+ }
+
+ if (TREE_CODE (ev) != POLYNOMIAL_CHREC
+ || CHREC_VARIABLE (ev) != (unsigned) loop->num)
+ return false;
+
+ *step = CHREC_RIGHT (ev);
+ if (TREE_CODE (*step) != INTEGER_CST)
+ return false;
+ *base = CHREC_LEFT (ev);
+ if (tree_contains_chrecs (*base)
+ || chrec_contains_symbols_defined_in_loop (*base, loop->num))
+ return false;
+
+ return true;
+}
+
+/* Runs the analysis of scalar evolutions. */
+
+void
+scev_analysis (void)
+{
+ varray_type exit_conditions;
+
+ VARRAY_GENERIC_PTR_INIT (exit_conditions, 37, "exit_conditions");
+ select_loops_exit_conditions (current_loops, &exit_conditions);
+
+ if (dump_file && (dump_flags & TDF_STATS))
+ analyze_scalar_evolution_for_all_loop_phi_nodes (exit_conditions);
+
+ number_of_iterations_for_all_loops (exit_conditions);
+ VARRAY_CLEAR (exit_conditions);
+}
+
+/* Finalize the scalar evolution analysis. */
+
+void
+scev_finalize (void)
+{
+ htab_delete (scalar_evolution_info);
+ BITMAP_XFREE (already_instantiated);
+}
+
Index: tree-scalar-evolution.h
===================================================================
RCS file: tree-scalar-evolution.h
diff -N tree-scalar-evolution.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tree-scalar-evolution.h 30 Jun 2004 23:13:58 -0000
@@ -0,0 +1,39 @@
+/* Scalar evolution detector.
+ Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+ Contributed by Sebastian Pop <s.pop@laposte.net>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
+
+#ifndef GCC_TREE_SCALAR_EVOLUTION_H
+#define GCC_TREE_SCALAR_EVOLUTION_H
+
+extern tree number_of_iterations_in_loop (struct loop *);
+extern tree get_loop_exit_condition (struct loop *);
+
+extern void scev_initialize (struct loops *loops);
+extern void scev_reset (void);
+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);
+extern void scev_analysis (void);
+
+bool simple_iv (struct loop *, tree, tree, tree *, tree *);
+
+#endif /* GCC_TREE_SCALAR_EVOLUTION_H */
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: tree-ssa-loop-niter.c
diff -N tree-ssa-loop-niter.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tree-ssa-loop-niter.c 30 Jun 2004 23:13:58 -0000
@@ -0,0 +1,1271 @@
+/* Functions to determine/estimate number of iterations of a loop.
+ Copyright (C) 2004 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 2, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "output.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "cfgloop.h"
+#include "tree-pass.h"
+#include "ggc.h"
+#include "tree-chrec.h"
+#include "tree-scalar-evolution.h"
+#include "params.h"
+#include "flags.h"
+#include "tree-inline.h"
+
+#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
+
+/* Just to shorten the ugly names. */
+#define EXEC_BINARY nondestructive_fold_binary_to_constant
+#define EXEC_UNARY nondestructive_fold_unary_to_constant
+
+/*
+
+ Analysis of number of iterations of an affine exit test.
+
+*/
+
+/* Checks whether ARG is either NULL_TREE or constant zero. */
+
+static bool
+zero_p (tree arg)
+{
+ if (!arg)
+ return true;
+
+ return integer_zerop (arg);
+}
+
+/* Computes inverse of X modulo 2^s, where MASK = 2^s-1. */
+
+static tree
+inverse (tree x, tree mask)
+{
+ tree type = TREE_TYPE (x);
+ tree ctr = EXEC_BINARY (RSHIFT_EXPR, type, mask, integer_one_node);
+ tree rslt = convert (type, integer_one_node);
+
+ while (integer_nonzerop (ctr))
+ {
+ rslt = EXEC_BINARY (MULT_EXPR, type, rslt, x);
+ rslt = EXEC_BINARY (BIT_AND_EXPR, type, rslt, mask);
+ x = EXEC_BINARY (MULT_EXPR, type, x, x);
+ x = EXEC_BINARY (BIT_AND_EXPR, type, x, mask);
+ ctr = EXEC_BINARY (RSHIFT_EXPR, type, ctr, integer_one_node);
+ }
+
+ return rslt;
+}
+
+/* Returns unsigned variant of TYPE. */
+
+static tree
+unsigned_type_for (tree type)
+{
+ return make_unsigned_type (TYPE_PRECISION (type));
+}
+
+/* Returns signed variant of TYPE. */
+
+static tree
+signed_type_for (tree type)
+{
+ return make_signed_type (TYPE_PRECISION (type));
+}
+
+/* Determine the number of iterations according to condition (for staying
+ inside loop) BASE0 + STEP0 * i (CODE) BASE1 + STEP1 * i, computed in TYPE.
+ Store the results to NITER. */
+
+void
+number_of_iterations_cond (tree type, tree base0, tree step0,
+ enum tree_code code, tree base1, tree step1,
+ struct tree_niter_desc *niter)
+{
+ tree step, delta, mmin, mmax;
+ tree may_xform, bound, s, d, tmp;
+ bool was_sharp = false;
+ tree assumption;
+ tree assumptions = boolean_true_node;
+ tree noloop_assumptions = boolean_false_node;
+ tree niter_type, signed_niter_type;
+
+ /* The meaning of these assumptions is this:
+ if !assumptions
+ then the rest of information does not have to be valid
+ if noloop_assumptions then the loop does not have to roll
+ (but it is only conservative approximation, i.e. it only says that
+ if !noloop_assumptions, then the loop does not end before the computed
+ number of iterations) */
+
+ /* Make < comparison from > ones. */
+ if (code == GE_EXPR
+ || code == GT_EXPR)
+ {
+ SWAP (base0, base1);
+ SWAP (step0, step1);
+ code = swap_tree_comparison (code);
+ }
+
+ /* We can take care of the case of two induction variables chasing each other
+ if the test is NE. I have never seen a loop using it, but still it is
+ cool. */
+ if (!zero_p (step0) && !zero_p (step1))
+ {
+ if (code != NE_EXPR)
+ return;
+
+ step0 = EXEC_BINARY (MINUS_EXPR, type, step0, step1);
+ step1 = NULL_TREE;
+ }
+
+ /* If the result is a constant, the loop is weird. More precise handling
+ would be possible, but the situation is not common enough to waste time
+ on it. */
+ if (zero_p (step0) && zero_p (step1))
+ return;
+
+ /* Ignore loops of while (i-- < 10) type. */
+ if (code != NE_EXPR)
+ {
+ if (step0 && !tree_expr_nonnegative_p (step0))
+ return;
+
+ if (!zero_p (step1) && tree_expr_nonnegative_p (step1))
+ return;
+ }
+
+ if (TREE_CODE (type) == POINTER_TYPE)
+ {
+ /* We assume pointer arithmetics never overflows. */
+ mmin = mmax = NULL_TREE;
+ }
+ else
+ {
+ mmin = TYPE_MIN_VALUE (type);
+ mmax = TYPE_MAX_VALUE (type);
+ }
+
+ /* Some more condition normalization. We must record some assumptions
+ due to overflows. */
+
+ if (code == LT_EXPR)
+ {
+ /* We want to take care only of <=; this is easy,
+ as in cases the overflow would make the transformation unsafe the loop
+ does not roll. Seemingly it would make more sense to want to take
+ care of <, as NE is more simmilar to it, but the problem is that here
+ the transformation would be more difficult due to possibly infinite
+ loops. */
+ if (zero_p (step0))
+ {
+ if (mmax)
+ assumption = fold (build (EQ_EXPR, boolean_type_node, base0, mmax));
+ else
+ assumption = boolean_false_node;
+ if (integer_nonzerop (assumption))
+ goto zero_iter;
+ base0 = fold (build (PLUS_EXPR, type, base0,
+ convert (type, integer_one_node)));
+ }
+ else
+ {
+ if (mmin)
+ assumption = fold (build (EQ_EXPR, boolean_type_node, base1, mmin));
+ else
+ assumption = boolean_false_node;
+ if (integer_nonzerop (assumption))
+ goto zero_iter;
+ base1 = fold (build (MINUS_EXPR, type, base1,
+ convert (type, integer_one_node)));
+ }
+ noloop_assumptions = assumption;
+ code = LE_EXPR;
+
+ /* It will be useful to be able to tell the difference once more in
+ <= -> != reduction. */
+ was_sharp = true;
+ }
+
+ /* Take care of trivially infinite loops. */
+ if (code != NE_EXPR)
+ {
+ if (zero_p (step0)
+ && mmin
+ && operand_equal_p (base0, mmin, 0))
+ return;
+ if (zero_p (step1)
+ && mmax
+ && operand_equal_p (base1, mmax, 0))
+ return;
+ }
+
+ /* If we can we want to take care of NE conditions instead of size
+ comparisons, as they are much more friendly (most importantly
+ this takes care of special handling of loops with step 1). We can
+ do it if we first check that upper bound is greater or equal to
+ lower bound, their difference is constant c modulo step and that
+ there is not an overflow. */
+ if (code != NE_EXPR)
+ {
+ if (zero_p (step0))
+ step = EXEC_UNARY (NEGATE_EXPR, type, step1);
+ else
+ step = step0;
+ delta = build (MINUS_EXPR, type, base1, base0);
+ delta = fold (build (FLOOR_MOD_EXPR, type, delta, step));
+ may_xform = boolean_false_node;
+
+ if (TREE_CODE (delta) == INTEGER_CST)
+ {
+ tmp = EXEC_BINARY (MINUS_EXPR, type, step,
+ convert (type, integer_one_node));
+ if (was_sharp
+ && operand_equal_p (delta, tmp, 0))
+ {
+ /* A special case. We have transformed condition of type
+ for (i = 0; i < 4; i += 4)
+ into
+ for (i = 0; i <= 3; i += 4)
+ obviously if the test for overflow during that transformation
+ passed, we cannot overflow here. Most importantly any
+ loop with sharp end condition and step 1 falls into this
+ cathegory, so handling this case specially is definitely
+ worth the troubles. */
+ may_xform = boolean_true_node;
+ }
+ else if (zero_p (step0))
+ {
+ if (!mmin)
+ may_xform = boolean_true_node;
+ else
+ {
+ bound = EXEC_BINARY (PLUS_EXPR, type, mmin, step);
+ bound = EXEC_BINARY (MINUS_EXPR, type, bound, delta);
+ may_xform = fold (build (LE_EXPR, boolean_type_node,
+ bound, base0));
+ }
+ }
+ else
+ {
+ if (!mmax)
+ may_xform = boolean_true_node;
+ else
+ {
+ bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step);
+ bound = EXEC_BINARY (PLUS_EXPR, type, bound, delta);
+ may_xform = fold (build (LE_EXPR, boolean_type_node,
+ base1, bound));
+ }
+ }
+ }
+
+ if (!integer_zerop (may_xform))
+ {
+ /* We perform the transformation always provided that it is not
+ completely senseless. This is OK, as we would need this assumption
+ to determine the number of iterations anyway. */
+ if (!integer_nonzerop (may_xform))
+ assumptions = may_xform;
+
+ if (zero_p (step0))
+ {
+ base0 = build (PLUS_EXPR, type, base0, delta);
+ base0 = fold (build (MINUS_EXPR, type, base0, step));
+ }
+ else
+ {
+ base1 = build (MINUS_EXPR, type, base1, delta);
+ base1 = fold (build (PLUS_EXPR, type, base1, step));
+ }
+
+ assumption = fold (build (GT_EXPR, boolean_type_node, base0, base1));
+ noloop_assumptions = fold (build (TRUTH_OR_EXPR, boolean_type_node,
+ noloop_assumptions, assumption));
+ code = NE_EXPR;
+ }
+ }
+
+ /* Count the number of iterations. */
+ niter_type = unsigned_type_for (type);
+ signed_niter_type = signed_type_for (type);
+
+ if (code == NE_EXPR)
+ {
+ /* Everything we do here is just arithmetics modulo size of mode. This
+ makes us able to do more involved computations of number of iterations
+ than in other cases. First transform the condition into shape
+ s * i <> c, with s positive. */
+ base1 = fold (build (MINUS_EXPR, type, base1, base0));
+ base0 = NULL_TREE;
+ if (!zero_p (step1))
+ step0 = EXEC_UNARY (NEGATE_EXPR, type, step1);
+ step1 = NULL_TREE;
+ if (!tree_expr_nonnegative_p (convert (signed_niter_type, step0)))
+ {
+ step0 = EXEC_UNARY (NEGATE_EXPR, type, step0);
+ base1 = fold (build1 (NEGATE_EXPR, type, base1));
+ }
+
+ base1 = convert (niter_type, base1);
+ step0 = convert (niter_type, step0);
+
+ /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
+ is infinite. Otherwise, the number of iterations is
+ (inverse(s/d) * (c/d)) mod (size of mode/d). */
+ s = step0;
+ d = integer_one_node;
+ bound = convert (niter_type, build_int_2 (~0, ~0));
+ while (1)
+ {
+ tmp = EXEC_BINARY (BIT_AND_EXPR, niter_type, s,
+ convert (niter_type, integer_one_node));
+ if (integer_nonzerop (tmp))
+ break;
+
+ s = EXEC_BINARY (RSHIFT_EXPR, niter_type, s,
+ convert (niter_type, integer_one_node));
+ d = EXEC_BINARY (LSHIFT_EXPR, niter_type, d,
+ convert (niter_type, integer_one_node));
+ bound = EXEC_BINARY (RSHIFT_EXPR, niter_type, bound,
+ convert (niter_type, integer_one_node));
+ }
+
+ tmp = fold (build (EXACT_DIV_EXPR, niter_type, base1, d));
+ tmp = fold (build (MULT_EXPR, niter_type, tmp, inverse (s, bound)));
+ niter->niter = fold (build (BIT_AND_EXPR, niter_type, tmp, bound));
+ }
+ else
+ {
+ if (zero_p (step1))
+ /* Condition in shape a + s * i <= b
+ We must know that b + s does not overflow and a <= b + s and then we
+ can compute number of iterations as (b + s - a) / s. (It might
+ seem that we in fact could be more clever about testing the b + s
+ overflow condition using some information about b - a mod s,
+ but it was already taken into account during LE -> NE transform). */
+ {
+ if (mmax)
+ {
+ bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step0);
+ assumption = fold (build (LE_EXPR, boolean_type_node,
+ base1, bound));
+ assumptions = fold (build (TRUTH_AND_EXPR, boolean_type_node,
+ assumptions, assumption));
+ }
+
+ step = step0;
+ tmp = fold (build (PLUS_EXPR, type, base1, step0));
+ assumption = fold (build (GT_EXPR, boolean_type_node, base0, tmp));
+ delta = fold (build (PLUS_EXPR, type, base1, step));
+ delta = fold (build (MINUS_EXPR, type, delta, base0));
+ delta = convert (niter_type, delta);
+ }
+ else
+ {
+ /* Condition in shape a <= b - s * i
+ We must know that a - s does not overflow and a - s <= b and then
+ we can again compute number of iterations as (b - (a - s)) / s. */
+ if (mmin)
+ {
+ bound = EXEC_BINARY (MINUS_EXPR, type, mmin, step1);
+ assumption = fold (build (LE_EXPR, boolean_type_node,
+ bound, base0));
+ assumptions = fold (build (TRUTH_AND_EXPR, boolean_type_node,
+ assumptions, assumption));
+ }
+ step = fold (build1 (NEGATE_EXPR, type, step1));
+ tmp = fold (build (PLUS_EXPR, type, base0, step1));
+ assumption = fold (build (GT_EXPR, boolean_type_node, tmp, base1));
+ delta = fold (build (MINUS_EXPR, type, base0, step));
+ delta = fold (build (MINUS_EXPR, type, base1, delta));
+ delta = convert (niter_type, delta);
+ }
+ noloop_assumptions = fold (build (TRUTH_OR_EXPR, boolean_type_node,
+ noloop_assumptions, assumption));
+ delta = fold (build (FLOOR_DIV_EXPR, niter_type, delta,
+ convert (niter_type, step)));
+ niter->niter = delta;
+ }
+
+ niter->assumptions = assumptions;
+ niter->may_be_zero = noloop_assumptions;
+ return;
+
+zero_iter:
+ niter->assumptions = boolean_true_node;
+ niter->may_be_zero = boolean_true_node;
+ niter->niter = convert (type, integer_zero_node);
+ return;
+}
+
+/* Tries to simplify EXPR using the evolutions of the loop invariants
+ in the outer loops. */
+
+static tree
+simplify_using_outer_evolutions (struct loop *loop, tree expr)
+{
+ enum tree_code code = TREE_CODE (expr);
+ bool changed;
+ tree e, e0, e1, e2;
+
+ if (is_gimple_min_invariant (expr))
+ return expr;
+
+ if (code == TRUTH_OR_EXPR
+ || code == TRUTH_AND_EXPR
+ || code == COND_EXPR)
+ {
+ changed = false;
+
+ e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
+ if (TREE_OPERAND (expr, 0) != e0)
+ changed = true;
+
+ e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
+ if (TREE_OPERAND (expr, 1) != e1)
+ changed = true;
+
+ if (code == COND_EXPR)
+ {
+ e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
+ if (TREE_OPERAND (expr, 2) != e2)
+ changed = true;
+ }
+ else
+ e2 = NULL_TREE;
+
+ if (changed)
+ {
+ if (code == COND_EXPR)
+ expr = build (code, boolean_type_node, e0, e1, e2);
+ else
+ expr = build (code, boolean_type_node, e0, e1);
+ expr = fold (expr);
+ }
+
+ return expr;
+ }
+
+ e = instantiate_parameters (loop, expr);
+ if (is_gimple_min_invariant (e))
+ return e;
+
+ return expr;
+}
+
+/* Tries to simplify EXPR using the condition COND. */
+
+static tree
+tree_simplify_using_condition (tree cond, tree expr)
+{
+ bool changed;
+ tree e, e0, e1, e2, notcond;
+ enum tree_code code = TREE_CODE (expr);
+
+ if (code == INTEGER_CST)
+ return expr;
+
+ if (code == TRUTH_OR_EXPR
+ || code == TRUTH_AND_EXPR
+ || code == COND_EXPR)
+ {
+ changed = false;
+
+ e0 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 0));
+ if (TREE_OPERAND (expr, 0) != e0)
+ changed = true;
+
+ e1 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 1));
+ if (TREE_OPERAND (expr, 1) != e1)
+ changed = true;
+
+ if (code == COND_EXPR)
+ {
+ e2 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 2));
+ if (TREE_OPERAND (expr, 2) != e2)
+ changed = true;
+ }
+ else
+ e2 = NULL_TREE;
+
+ if (changed)
+ {
+ if (code == COND_EXPR)
+ expr = build (code, boolean_type_node, e0, e1, e2);
+ else
+ expr = build (code, boolean_type_node, e0, e1);
+ expr = fold (expr);
+ }
+
+ return expr;
+ }
+
+ /* Check whether COND ==> EXPR. */
+ notcond = invert_truthvalue (cond);
+ e = fold (build (TRUTH_OR_EXPR, boolean_type_node,
+ notcond, expr));
+ if (integer_nonzerop (e))
+ return e;
+
+ /* Check whether COND ==> not EXPR. */
+ e = fold (build (TRUTH_AND_EXPR, boolean_type_node,
+ cond, expr));
+ if (integer_zerop (e))
+ return e;
+
+ return expr;
+}
+
+/* Tries to simplify EXPR using the conditions on entry to LOOP.
+ Record the conditions used to CONDS_USED. */
+
+static tree
+simplify_using_initial_conditions (struct loop *loop, tree expr,
+ tree *conds_used)
+{
+ edge e;
+ basic_block bb;
+ tree exp, cond;
+
+ if (TREE_CODE (expr) == INTEGER_CST)
+ return expr;
+
+ for (bb = loop->header;
+ bb != ENTRY_BLOCK_PTR;
+ bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+ {
+ e = bb->pred;
+ if (e->pred_next)
+ continue;
+
+ if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
+ continue;
+
+ cond = COND_EXPR_COND (last_stmt (e->src));
+ if (e->flags & EDGE_FALSE_VALUE)
+ cond = invert_truthvalue (cond);
+ exp = tree_simplify_using_condition (cond, expr);
+
+ if (exp != expr)
+ *conds_used = fold (build (TRUTH_AND_EXPR,
+ boolean_type_node,
+ *conds_used,
+ cond));
+
+ expr = exp;
+ }
+
+ return expr;
+}
+
+/* Stores description of number of iterations of LOOP derived from EXIT
+ in NITER. */
+
+bool
+number_of_iterations_exit (struct loop *loop, edge exit,
+ struct tree_niter_desc *niter)
+{
+ tree stmt, cond, type;
+ tree op0, base0, step0;
+ tree op1, base1, step1;
+ enum tree_code code;
+
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
+ return false;
+
+ niter->assumptions = convert (boolean_type_node, integer_zero_node);
+ stmt = last_stmt (exit->src);
+ if (!stmt || TREE_CODE (stmt) != COND_EXPR)
+ return false;
+
+ /* We want the condition for staying inside loop. */
+ cond = COND_EXPR_COND (stmt);
+ if (exit->flags & EDGE_TRUE_VALUE)
+ cond = invert_truthvalue (cond);
+
+ code = TREE_CODE (cond);
+ switch (code)
+ {
+ case GT_EXPR:
+ case GE_EXPR:
+ case NE_EXPR:
+ case LT_EXPR:
+ case LE_EXPR:
+ break;
+
+ default:
+ return false;
+ }
+
+ op0 = TREE_OPERAND (cond, 0);
+ op1 = TREE_OPERAND (cond, 1);
+ type = TREE_TYPE (op0);
+
+ if (TREE_CODE (type) != INTEGER_TYPE
+ && TREE_CODE (type) != POINTER_TYPE)
+ return false;
+
+ if (!simple_iv (loop, stmt, op0, &base0, &step0))
+ return false;
+ if (!simple_iv (loop, stmt, op1, &base1, &step1))
+ return false;
+
+ niter->niter = NULL_TREE;
+ number_of_iterations_cond (type, base0, step0, code, base1, step1,
+ niter);
+ if (!niter->niter)
+ return false;
+
+ niter->assumptions = simplify_using_outer_evolutions (loop,
+ niter->assumptions);
+ niter->may_be_zero = simplify_using_outer_evolutions (loop,
+ niter->may_be_zero);
+ niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
+
+ niter->additional_info = boolean_true_node;
+ niter->assumptions
+ = simplify_using_initial_conditions (loop,
+ niter->assumptions,
+ &niter->additional_info);
+ niter->may_be_zero
+ = simplify_using_initial_conditions (loop,
+ niter->may_be_zero,
+ &niter->additional_info);
+ return integer_onep (niter->assumptions);
+}
+
+/*
+
+ Analysis of a number of iterations of a loop by a brute-force evaluation.
+
+*/
+
+/* Bound on the number of iterations we try to evaluate. */
+
+#define MAX_ITERATIONS_TO_TRACK 1000
+
+/* Determines a loop phi node of LOOP such that X is derived from it
+ by a chain of operations with constants. */
+
+static tree
+chain_of_csts_start (struct loop *loop, tree x)
+{
+ tree stmt = SSA_NAME_DEF_STMT (x);
+ basic_block bb = bb_for_stmt (stmt);
+ use_optype uses;
+
+ if (!bb
+ || !flow_bb_inside_loop_p (loop, bb))
+ return NULL_TREE;
+
+ if (TREE_CODE (stmt) == PHI_NODE)
+ {
+ if (bb == loop->header)
+ return stmt;
+
+ return NULL_TREE;
+ }
+
+ if (TREE_CODE (stmt) != MODIFY_EXPR)
+ return NULL_TREE;
+
+ get_stmt_operands (stmt);
+ if (NUM_VUSES (STMT_VUSE_OPS (stmt)) > 0)
+ return NULL_TREE;
+ if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0)
+ return NULL_TREE;
+ if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
+ return NULL_TREE;
+ if (NUM_DEFS (STMT_DEF_OPS (stmt)) > 1)
+ return NULL_TREE;
+ uses = STMT_USE_OPS (stmt);
+ if (NUM_USES (uses) != 1)
+ return NULL_TREE;
+
+ return chain_of_csts_start (loop, USE_OP (uses, 0));
+}
+
+/* Determines whether X is derived from a value of a phi node in LOOP
+ such that
+
+ * this derivation consists only from operations with constants
+ * the initial value of the phi node is constant
+ * its value in the next iteration can be derived from the current one
+ by a chain of operations with constants. */
+
+static tree
+get_base_for (struct loop *loop, tree x)
+{
+ tree phi, init, next;
+
+ if (is_gimple_min_invariant (x))
+ return x;
+
+ phi = chain_of_csts_start (loop, x);
+ if (!phi)
+ return NULL_TREE;
+
+ init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
+ next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
+
+ if (TREE_CODE (next) != SSA_NAME)
+ return NULL_TREE;
+
+ if (!is_gimple_min_invariant (init))
+ return NULL_TREE;
+
+ if (chain_of_csts_start (loop, next) != phi)
+ return NULL_TREE;
+
+ return phi;
+}
+
+/* Evaluates value of X, provided that the value of the variable defined
+ in the loop phi node from that X is derived by operations with constants
+ is BASE. */
+
+static tree
+get_val_for (tree x, tree base)
+{
+ tree stmt, nx, val;
+ use_optype uses;
+ use_operand_p op;
+
+ if (!x)
+ return base;
+
+ stmt = SSA_NAME_DEF_STMT (x);
+ if (TREE_CODE (stmt) == PHI_NODE)
+ return base;
+
+ uses = STMT_USE_OPS (stmt);
+ op = USE_OP_PTR (uses, 0);
+
+ nx = USE_FROM_PTR (op);
+ val = get_val_for (nx, base);
+ SET_USE (op, val);
+ val = fold (TREE_OPERAND (stmt, 1));
+ SET_USE (op, nx);
+
+ return val;
+}
+
+/* Tries to count the number of iterations of LOOP till it exits by EXIT
+ by brute force. */
+
+tree
+loop_niter_by_eval (struct loop *loop, edge exit)
+{
+ tree cond, cnd, acnd;
+ tree op[2], val[2], next[2], aval[2], phi[2];
+ unsigned i, j;
+ enum tree_code cmp;
+
+ cond = last_stmt (exit->src);
+ if (!cond || TREE_CODE (cond) != COND_EXPR)
+ return chrec_dont_know;
+
+ cnd = COND_EXPR_COND (cond);
+ if (exit->flags & EDGE_TRUE_VALUE)
+ cnd = invert_truthvalue (cnd);
+
+ cmp = TREE_CODE (cnd);
+ switch (cmp)
+ {
+ case EQ_EXPR:
+ case NE_EXPR:
+ case GT_EXPR:
+ case GE_EXPR:
+ case LT_EXPR:
+ case LE_EXPR:
+ for (j = 0; j < 2; j++)
+ op[j] = TREE_OPERAND (cnd, j);
+ break;
+
+ default:
+ return chrec_dont_know;
+ }
+
+ for (j = 0; j < 2; j++)
+ {
+ phi[j] = get_base_for (loop, op[j]);
+ if (!phi[j])
+ return chrec_dont_know;
+ }
+
+ for (j = 0; j < 2; j++)
+ {
+ if (TREE_CODE (phi[j]) == PHI_NODE)
+ {
+ val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
+ next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
+ }
+ else
+ {
+ val[j] = phi[j];
+ next[j] = NULL_TREE;
+ op[j] = NULL_TREE;
+ }
+ }
+
+ for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
+ {
+ for (j = 0; j < 2; j++)
+ aval[j] = get_val_for (op[j], val[j]);
+
+ acnd = fold (build (cmp, boolean_type_node, aval[0], aval[1]));
+ if (integer_zerop (acnd))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ "Proved that loop %d iterates %d times using brute force.\n",
+ loop->num, i);
+ return build_int_2 (i, 0);
+ }
+
+ for (j = 0; j < 2; j++)
+ val[j] = get_val_for (next[j], val[j]);
+ }
+
+ return chrec_dont_know;
+}
+
+/* Finds the exit of the LOOP by that the loop exits after a constant
+ number of iterations and stores it to *EXIT. The iteration count
+ is returned. */
+
+tree
+find_loop_niter_by_eval (struct loop *loop, edge *exit)
+{
+ unsigned n_exits, i;
+ edge *exits = get_loop_exit_edges (loop, &n_exits);
+ edge ex;
+ tree niter = NULL_TREE, aniter;
+
+ *exit = NULL;
+ for (i = 0; i < n_exits; i++)
+ {
+ ex = exits[i];
+ if (!just_once_each_iteration_p (loop, ex->src))
+ continue;
+
+ aniter = loop_niter_by_eval (loop, ex);
+ if (chrec_contains_undetermined (aniter)
+ || TREE_CODE (aniter) != INTEGER_CST)
+ continue;
+
+ if (niter
+ && !integer_nonzerop (fold (build (LT_EXPR, boolean_type_node,
+ aniter, niter))))
+ continue;
+
+ niter = aniter;
+ *exit = ex;
+ }
+ free (exits);
+
+ return niter ? niter : chrec_dont_know;
+}
+
+/*
+
+ Analysis of upper bounds on number of iterations of a loop.
+
+*/
+
+/* Bound on number of iterations of a loop. */
+
+struct nb_iter_bound
+{
+ tree bound; /* The bound on the number of executions of anything
+ after ... */
+ tree at_stmt; /* ... this statement during one execution of loop. */
+ tree additional; /* Additional information about the bound. */
+ struct nb_iter_bound *next;
+ /* The next bound in a list. */
+};
+
+/* Records that AT_STMT is executed at most BOUND times in LOOP. The
+ additional condition ADDITIONAL is recorded as well. */
+
+static void
+record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
+{
+ struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Statements after ");
+ print_generic_expr (dump_file, at_stmt, TDF_SLIM);
+ fprintf (dump_file, " are executed at most ");
+ print_generic_expr (dump_file, bound, TDF_SLIM);
+ fprintf (dump_file, " times in loop %d.\n", loop->num);
+ }
+
+ elt->bound = bound;
+ elt->at_stmt = at_stmt;
+ elt->additional = additional;
+ elt->next = loop->bounds;
+ loop->bounds = elt;
+}
+
+/* Records estimates on numbers of iterations of LOOP. */
+
+static void
+estimate_numbers_of_iterations_loop (struct loop *loop)
+{
+ edge *exits;
+ tree niter, type;
+ unsigned i, n_exits;
+ struct tree_niter_desc niter_desc;
+
+ exits = get_loop_exit_edges (loop, &n_exits);
+ for (i = 0; i < n_exits; i++)
+ {
+ if (!number_of_iterations_exit (loop, exits[i], &niter_desc))
+ continue;
+
+ niter = niter_desc.niter;
+ type = TREE_TYPE (niter);
+ if (!integer_zerop (niter_desc.may_be_zero)
+ && !integer_nonzerop (niter_desc.may_be_zero))
+ niter = build (COND_EXPR, type, niter_desc.may_be_zero,
+ convert (type, integer_zero_node),
+ niter);
+ record_estimate (loop, niter,
+ niter_desc.additional_info,
+ last_stmt (exits[i]->src));
+ }
+ free (exits);
+
+ /* TODO Here we could use other possibilities, like bounds of arrays accessed
+ in the loop. */
+}
+
+/* Records estimates on numbers of iterations of LOOPS. */
+
+void
+estimate_numbers_of_iterations (struct loops *loops)
+{
+ unsigned i;
+ struct loop *loop;
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (loop)
+ estimate_numbers_of_iterations_loop (loop);
+ }
+}
+
+/* If A > B, returns -1. If A == B, returns 0. If A < B, returns 1.
+ If neither of these relations can be proved, returns 2. */
+
+static int
+compare_trees (tree a, tree b)
+{
+ tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
+ tree type;
+
+ if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
+ type = typea;
+ else
+ type = typeb;
+
+ a = convert (type, a);
+ b = convert (type, b);
+
+ if (integer_nonzerop (fold (build (EQ_EXPR, boolean_type_node, a, b))))
+ return 0;
+ if (integer_nonzerop (fold (build (LT_EXPR, boolean_type_node, a, b))))
+ return 1;
+ if (integer_nonzerop (fold (build (GT_EXPR, boolean_type_node, a, b))))
+ return -1;
+
+ return 2;
+}
+
+/* Returns the largest value obtainable by casting something in INNER type to
+ OUTER type. */
+
+tree
+upper_bound_in_type (tree outer, tree inner)
+{
+ unsigned HOST_WIDE_INT lo, hi;
+ unsigned bits = TYPE_PRECISION (inner);
+
+ if (TYPE_UNSIGNED (outer) || TYPE_UNSIGNED (inner))
+ {
+ /* Zero extending in these cases. */
+ if (bits <= HOST_BITS_PER_WIDE_INT)
+ {
+ hi = 0;
+ lo = (~(unsigned HOST_WIDE_INT) 0)
+ >> (HOST_BITS_PER_WIDE_INT - bits);
+ }
+ else
+ {
+ hi = (~(unsigned HOST_WIDE_INT) 0)
+ >> (2 * HOST_BITS_PER_WIDE_INT - bits);
+ lo = ~(unsigned HOST_WIDE_INT) 0;
+ }
+ }
+ else
+ {
+ /* Sign extending in these cases. */
+ if (bits <= HOST_BITS_PER_WIDE_INT)
+ {
+ hi = 0;
+ lo = (~(unsigned HOST_WIDE_INT) 0)
+ >> (HOST_BITS_PER_WIDE_INT - bits) >> 1;
+ }
+ else
+ {
+ hi = (~(unsigned HOST_WIDE_INT) 0)
+ >> (2 * HOST_BITS_PER_WIDE_INT - bits) >> 1;
+ lo = ~(unsigned HOST_WIDE_INT) 0;
+ }
+ }
+
+ return convert (outer,
+ convert (inner,
+ build_int_2 (lo, hi)));
+}
+
+/* Returns the smallest value obtainable by casting something in INNER type to
+ OUTER type. */
+
+tree
+lower_bound_in_type (tree outer, tree inner)
+{
+ unsigned HOST_WIDE_INT lo, hi;
+ unsigned bits = TYPE_PRECISION (inner);
+
+ if (TYPE_UNSIGNED (outer) || TYPE_UNSIGNED (inner))
+ lo = hi = 0;
+ else if (bits <= HOST_BITS_PER_WIDE_INT)
+ {
+ hi = ~(unsigned HOST_WIDE_INT) 0;
+ lo = (~(unsigned HOST_WIDE_INT) 0) << (bits - 1);
+ }
+ else
+ {
+ hi = (~(unsigned HOST_WIDE_INT) 0) << (bits - HOST_BITS_PER_WIDE_INT - 1);
+ lo = 0;
+ }
+
+ return convert (outer,
+ convert (inner,
+ build_int_2 (lo, hi)));
+}
+
+/* Returns true if statement S1 dominates statement S2. */
+
+static bool
+stmt_dominates_stmt_p (tree s1, tree s2)
+{
+ basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
+
+ if (!bb1
+ || s1 == s2)
+ return true;
+
+ if (bb1 == bb2)
+ {
+ block_stmt_iterator bsi;
+
+ for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
+ if (bsi_stmt (bsi) == s1)
+ return true;
+
+ return false;
+ }
+
+ return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
+}
+
+/* Checks whether it is correct to count the induction variable BASE + STEP * I
+ at AT_STMT in wider TYPE, using the fact that statement OF is executed at
+ most BOUND times in the loop. If it is possible, return the value of step in
+ the TYPE, otherwise return NULL_TREE.
+
+ ADDITIONAL is the additional information recorded for bound. This is useful
+ in the following case, created by loop header copying:
+
+ i = 0;
+ if (n > 0)
+ do
+ {
+ something;
+ } while (++i < n)
+
+ If the n > 0 condition is taken into account, the number of iterations of the
+ loop can be expressed as n - 1. If the type of n is signed, the ADDITIONAL
+ assumption "n > 0" says us that the value of the number of iterations is at
+ most MAX_TYPE - 1 (without this assumption, it might overflow). */
+
+static tree
+can_count_iv_in_wider_type_bound (tree type, tree base, tree step,
+ tree at_stmt,
+ tree bound,
+ tree additional,
+ tree of)
+{
+ tree inner_type = TREE_TYPE (base), b, bplusstep, new_step, new_step_abs;
+ tree valid_niter, extreme, unsigned_type, delta, bound_type;
+ tree cond;
+
+ b = convert (type, base);
+ bplusstep = convert (type,
+ fold (build (PLUS_EXPR, inner_type, base, step)));
+ new_step = fold (build (MINUS_EXPR, type, bplusstep, b));
+ if (TREE_CODE (new_step) != INTEGER_CST)
+ return NULL_TREE;
+
+ switch (compare_trees (bplusstep, b))
+ {
+ case -1:
+ extreme = upper_bound_in_type (type, inner_type);
+ delta = fold (build (MINUS_EXPR, type, extreme, b));
+ new_step_abs = new_step;
+ break;
+
+ case 1:
+ extreme = lower_bound_in_type (type, inner_type);
+ new_step_abs = fold (build (NEGATE_EXPR, type, new_step));
+ delta = fold (build (MINUS_EXPR, type, b, extreme));
+ break;
+
+ case 0:
+ return new_step;
+
+ default:
+ return NULL_TREE;
+ }
+
+ unsigned_type = unsigned_type_for (type);
+ delta = convert (unsigned_type, delta);
+ new_step_abs = convert (unsigned_type, new_step_abs);
+ valid_niter = fold (build (FLOOR_DIV_EXPR, unsigned_type,
+ delta, new_step_abs));
+
+ bound_type = TREE_TYPE (bound);
+ if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
+ bound = convert (unsigned_type, bound);
+ else
+ valid_niter = convert (bound_type, valid_niter);
+
+ if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
+ {
+ /* After the statement OF we know that anything is executed at most
+ BOUND times. */
+ cond = build (GE_EXPR, boolean_type_node, valid_niter, bound);
+ }
+ else
+ {
+ /* Before the statement OF we know that anything is executed at most
+ BOUND + 1 times. */
+ cond = build (GT_EXPR, boolean_type_node, valid_niter, bound);
+ }
+
+ cond = fold (cond);
+ if (integer_nonzerop (cond))
+ return new_step;
+
+ /* Try taking additional conditions into account. */
+ cond = build (TRUTH_OR_EXPR, boolean_type_node,
+ invert_truthvalue (additional),
+ cond);
+ cond = fold (cond);
+ if (integer_nonzerop (cond))
+ return new_step;
+
+ return NULL_TREE;
+}
+
+/* Checks whether it is correct to count the induction variable BASE + STEP * I
+ at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a
+ LOOP. If it is possible, return the value of step in the TYPE, otherwise
+ return NULL_TREE. */
+
+tree
+can_count_iv_in_wider_type (struct loop *loop, tree type, tree base, tree step,
+ tree at_stmt)
+{
+ struct nb_iter_bound *bound;
+ tree new_step;
+
+ for (bound = loop->bounds; bound; bound = bound->next)
+ {
+ new_step = can_count_iv_in_wider_type_bound (type, base, step,
+ at_stmt,
+ bound->bound,
+ bound->additional,
+ bound->at_stmt);
+
+ if (new_step)
+ return new_step;
+ }
+
+ return NULL_TREE;
+}
+
+/* Frees the information on upper bounds on numbers of iterations of LOOP. */
+
+static void
+free_numbers_of_iterations_estimates_loop (struct loop *loop)
+{
+ struct nb_iter_bound *bound, *next;
+
+ for (bound = loop->bounds; bound; bound = next)
+ {
+ next = bound->next;
+ free (bound);
+ }
+
+ loop->bounds = NULL;
+}
+
+/* Frees the information on upper bounds on numbers of iterations of LOOPS. */
+
+void
+free_numbers_of_iterations_estimates (struct loops *loops)
+{
+ unsigned i;
+ struct loop *loop;
+
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (loop)
+ free_numbers_of_iterations_estimates_loop (loop);
+ }
+}
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.534
diff -d -u -p -r1.534 tree.h
--- tree.h 30 Jun 2004 21:11:28 -0000 1.534
+++ tree.h 30 Jun 2004 23:13:58 -0000
@@ -3781,4 +3781,9 @@ extern int tree_node_sizes[];
restricted to creating gimple expressions. */
extern bool in_gimple_form;
+/* In tree-ssa-loop-niter.c. */
+
+tree lower_bound_in_type (tree, tree);
+tree upper_bound_in_type (tree, tree);
+
#endif /* GCC_TREE_H */