This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] Lno branch merge part 5 -- #s of loop iterations
Hello,
> >this patch contains some functions dealing with determining numbers of
> >iteration of a loop. To break a circular dependency on the scalar
> >evolutions analysis, dummy functions (simple_iv and
> >instantiate_parameters) are provided.
> >
> >
> This looks pretty good to me. I don't think I should approve it without
> letting RTH comment, since he's been looking at the previous patches in
> this series, but the structure makes sense to me. However, if you
> don't hear back from him in a bit, let me know, and I'll see if I can help.
>
> I have indicated a few changes below, mostly to help with documentation
> issues; these are things that made it harder for me to understand your
> change. Please make these changes before check-in.
here is the patch with changes according to your suggestions.
Zdenek
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1320
diff -c -3 -p -r1.1320 Makefile.in
*** Makefile.in 6 Jul 2004 16:28:29 -0000 1.1320
--- Makefile.in 7 Jul 2004 04:43:22 -0000
*************** TREE_SSA_LIVE_H = tree-ssa-live.h $(PART
*** 728,733 ****
--- 728,734 ----
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.
*************** C_OBJS = c-parse.o c-lang.o stub-objc.o
*** 886,892 ****
# Language-independent object files.
OBJS-common = \
! tree-chrec.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 \
--- 887,893 ----
# Language-independent object files.
OBJS-common = \
! tree-chrec.o tree-scalar-evolution.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 \
*************** OBJS-common = \
*** 895,900 ****
--- 896,902 ----
tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o \
tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o tree-iterator.o \
tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
+ tree-ssa-loop-niter.o \
alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o \
cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o \
cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o \
*************** tree-ssa-loop.o : tree-ssa-loop.c $(TREE
*** 1676,1681 ****
--- 1678,1687 ----
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
tree-pass.h $(FLAGS_H) tree-inline.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-ssa-loop-ch.o : tree-ssa-loop-ch.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) tree-inline.h \
output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
*************** tree-browser.o : tree-browser.c tree-bro
*** 1708,1713 ****
--- 1714,1723 ----
$(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-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)
tree-mudflap.o : $(CONFIG_H) errors.h $(SYSTEM_H) $(TREE_H) tree-inline.h \
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.20
diff -c -3 -p -r1.20 cfgloop.h
*** cfgloop.h 20 Jun 2004 21:31:28 -0000 1.20
--- cfgloop.h 7 Jul 2004 04:43:22 -0000
*************** struct loop
*** 175,180 ****
--- 175,183 ----
/* The number of LABEL_REFs on exit_labels for this loop and all
loops nested inside it. */
int exit_count;
+
+ /* Upper bound on number of iterations of a loop. */
+ struct nb_iter_bound *bounds;
};
/* Flags for state of loop structure. */
Index: params.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.def,v
retrieving revision 1.41
diff -c -3 -p -r1.41 params.def
*** params.def 25 May 2004 12:54:54 -0000 1.41
--- params.def 7 Jul 2004 04:43:22 -0000
*************** DEFPARAM(PARAM_MAX_UNSWITCH_LEVEL,
*** 229,234 ****
--- 229,242 ----
"The maximum number of unswitchings in a single loop",
3)
+ /* The maximum number of iterations of a loop the brute force algorithm
+ for analysis of # of iterations of the loop tries to evaluate. */
+ DEFPARAM(PARAM_MAX_ITERATIONS_TO_TRACK,
+ "max-iterations-to-track",
+ "Bound on the number of iterations the brute force # of iterations \
+ analysis algorithm evaluates",
+ 1000)
+
DEFPARAM(PARAM_MAX_SMS_LOOP_NUMBER,
"max-sms-loop-number",
"Maximum number of loops to perform swing modulo scheduling on \
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.18
diff -c -3 -p -r2.18 tree-flow.h
*** tree-flow.h 2 Jul 2004 07:34:30 -0000 2.18
--- tree-flow.h 7 Jul 2004 04:43:22 -0000
*************** extern void propagate_value (use_operand
*** 592,597 ****
--- 592,641 ----
extern void propagate_tree_value (tree *, tree);
extern void replace_exp (use_operand_p, tree);
+ /* Description of number of iterations of a loop. All the expressions inside
+ the structure can be evaluated at the end of the loop's preheader
+ (and due to ssa form, also anywhere inside the body of the loop). */
+
+ struct tree_niter_desc
+ {
+ tree assumptions; /* The boolean expression. If this expression evalutes
+ to false, then the other fields in this structure
+ should not be used; there is no guarantee that they
+ will be correct. */
+ tree may_be_zero; /* The booleand expression. If it evaluates to true,
+ the loop will exit in the first iteration (i.e.
+ its latch will not be executed), even if the niter
+ field says otherwise. */
+ tree niter; /* The expression giving the number of iterations of
+ a loop (provided that assumptions == true and
+ may_be_zero == false), more precisely the number
+ of executions of the latch of the loop. */
+ tree additional_info; /* The boolean expression. Sometimes we use additional
+ knowledge to simplify the other expressions
+ contained in this structure (for example the
+ knowledge about value ranges of operands on entry to
+ the loop). If this is a case, conjunction of such
+ condition is stored in this field, so that we do not
+ lose the information: for example if may_be_zero
+ is (n <= 0) and niter is (unsigned) n, we know
+ that the number of iterations is at most
+ MAX_SIGNED_INT. However if the (n <= 0) assumption
+ is eliminated (by looking at the guard on entry of
+ the loop), then the information would be lost. */
+ };
+
+ /* In tree-ssa-loop*.c */
+
+ void number_of_iterations_cond (tree, tree, tree, enum tree_code, tree, tree,
+ struct tree_niter_desc *);
+ bool number_of_iterations_exit (struct loop *, edge,
+ struct tree_niter_desc *niter);
+ tree loop_niter_by_eval (struct loop *, edge);
+ tree find_loop_niter_by_eval (struct loop *, edge *);
+ void estimate_numbers_of_iterations (struct loops *);
+ tree can_count_iv_in_wider_type (struct loop *, tree, tree, tree, tree);
+ 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);
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 7 Jul 2004 04:43:22 -0000
***************
*** 0 ****
--- 1,61 ----
+ /* 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. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "errors.h"
+ #include "ggc.h"
+ #include "tree.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"
+
+ /* 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 ATTRIBUTE_UNUSED,
+ tree chrec)
+ {
+ /* Just a dummy definition for now. */
+ return chrec;
+ }
+
+ /* 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 ATTRIBUTE_UNUSED, tree stmt ATTRIBUTE_UNUSED,
+ tree op ATTRIBUTE_UNUSED, tree *base ATTRIBUTE_UNUSED,
+ tree *step ATTRIBUTE_UNUSED)
+ {
+ /* Just a dummy definition for now. */
+ return false;
+ }
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 7 Jul 2004 04:43:22 -0000
***************
*** 0 ****
--- 1,28 ----
+ /* 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 instantiate_parameters (struct loop *, tree);
+ extern 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 7 Jul 2004 04:43:22 -0000
***************
*** 0 ****
--- 1,1295 ----
+ /* 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.
+
+ */
+
+ /* Returns true if ARG is either NULL_TREE or constant zero. */
+
+ static bool
+ zero_p (tree arg)
+ {
+ if (!arg)
+ return true;
+
+ return integer_zerop (arg);
+ }
+
+ /* Returns 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 handle the case when neither of the sides of the comparison is
+ invariant, provided that the test is NE_EXPR. This rarely occurs in
+ practice, but it is simple enough to manage. */
+ 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 arithmetic 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 superloops of LOOP. Returns the simplified expression
+ (or EXPR unchanged, if no simplification was possible). */
+
+ 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. Returns the simplified
+ expression (or EXPR unchanged, if no simplification was possible).*/
+
+ 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 for simplification to CONDS_USED.
+ Returns the simplified expression (or EXPR unchanged, if no
+ simplification was possible).*/
+
+ 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 (an exit edge of the LOOP) in NITER. Returns true if some
+ useful information could be derived (and fields of NITER has
+ meaning described in comments at struct tree_niter_desc
+ declaration), false otherwise. */
+
+ 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 = boolean_false_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 (PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
+
+ /* Returns the loop phi node of LOOP such that ssa name X is derived from its
+ result by a chain of operations such that all but exactly one of their
+ operands are 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 the expression X is derived from a result of a phi node
+ in header of LOOP such that
+
+ * the derivation of X consists only from operations with constants
+ * the initial value of the phi node is constant
+ * the value of the phi node in the next iteration can be derived from the
+ value in the current iteration by a chain of operations with constants.
+
+ If such phi node exists, it is returned. If X is a constant, X is returned
+ unchanged. Otherwise NULL_TREE is returned. */
+
+ 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;
+ }
+
+ /* Given an expression X, then
+
+ * if BASE is NULL_TREE, X must be a constant and we return X.
+ * otherwise X is a SSA name, whose value in the considered loop is derived
+ by a chain of operations with constant from a result of a phi node in
+ the header of the loop. Then we return value of X when the value of the
+ result of this phi node is given by the constant 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 -- i.e. by determining the value of the operands of the
+ condition at EXIT in first few iterations of the loop (assuming that
+ these values are constant) and determining the first one in that the
+ condition is not satisfied. Returns the constant giving the number
+ of the iterations of LOOP if successful, chrec_dont_know otherwise. */
+
+ 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 the exit edge to *EXIT. The constant
+ giving the number of iterations of LOOP is returned. The number of
+ iterations is determined using loop_niter_by_eval (i.e. by brute force
+ evaluation). If we are unable to find the exit for that loop_niter_by_eval
+ determines the number of iterations, chrec_dont_know 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.
+
+ */
+
+ /* The structure describing a bound on number of iterations of a loop. */
+
+ struct nb_iter_bound
+ {
+ tree bound; /* The expression whose value is an upper bound on the
+ number of executions of anything after ... */
+ tree at_stmt; /* ... this statement during one execution of loop. */
+ tree additional; /* A conjunction of conditions the operands of BOUND
+ satisfy. The additional information about the value
+ of the bound may be derived from it. */
+ 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 with the bound. */
+
+ 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
+ of the induction variable in the TYPE, otherwise return NULL_TREE.
+
+ ADDITIONAL is the additional condition recorded for operands of the 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 of the induction variable
+ 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.543
diff -c -3 -p -r1.543 tree.h
*** tree.h 6 Jul 2004 08:51:12 -0000 1.543
--- tree.h 7 Jul 2004 04:43:24 -0000
*************** extern int tree_node_sizes[];
*** 3786,3789 ****
--- 3786,3794 ----
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 */
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.479
diff -c -3 -p -r1.479 invoke.texi
*** doc/invoke.texi 5 Jul 2004 19:49:20 -0000 1.479
--- doc/invoke.texi 7 Jul 2004 04:43:29 -0000
*************** The maximum number of insns of an unswit
*** 5174,5179 ****
--- 5187,5197 ----
@item max-unswitch-level
The maximum number of branches unswitched in a single loop.
+ @item max-iterations-to-track
+
+ The maximum number of iterations of a loop the brute force algorithm
+ for analysis of # of iterations of the loop tries to evaluate.
+
@item hot-bb-count-fraction
Select fraction of the maximal count of repetitions of basic block in program
given basic block needs to have to be considered hot.