This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[autovect] [committed] Patch for PR17100
- From: Sebastian Pop <sebastian dot pop at cri dot ensmp dot fr>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 20 Dec 2004 00:20:50 +0100
- Subject: [autovect] [committed] Patch for PR17100
Hello,
Here is a patch that resurrects tree-elim-checks.c from lno-branch.
This solves PR17100:
for (i = 0; i < 10; i++)
{
if (i == -5) bar (); /* This call is now removed. */
}
Bootstrapped with BOOT_CFLAGS="-g -O2 -ftree-elim-checks -fdump-tree-elimchk-details"
and tested on i686-pc-linux-gnu. Applied to autovect-branch.
Sebastian
* Makefile.in (OBJS-common): Add tree-elim-check.o.
(tree-elim-check.o): New.
* common.opt (ftree-elim-checks): New.
* timevar.def (TV_TREE_ELIM_CHECKS): New.
* tree-flow.h (eliminate_redundant_checks): Declared.
* tree-optimize.c (init_tree_optimization_passes): Execute
pass_elim_checks.
* tree-pass.h (pass_elim_checks): Declare.
* tree-ssa-loop-niter.c (number_of_iterations_exit): Handle a
special case of EQ_EXPR.
* tree-ssa-loop.c (tree_elim_checks, gate_tree_elim_checks): New.
(pass_elim_checks): Defined.
* doc/invoke.texi (-ftree-elim-checks): Document the flag.
* tree-elim-check.c: New file, adapted from LNO-branch.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1419.2.3
diff -d -u -p -r1.1419.2.3 Makefile.in
--- Makefile.in 15 Dec 2004 18:26:14 -0000 1.1419.2.3
+++ Makefile.in 19 Dec 2004 23:20:23 -0000
@@ -892,7 +892,7 @@ C_OBJS = c-parse.o c-lang.o stub-objc.o
# Language-independent object files.
OBJS-common = \
- tree-chrec.o tree-scalar-evolution.o tree-data-ref.o \
+ tree-chrec.o tree-scalar-evolution.o tree-data-ref.o tree-elim-check.o \
tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o \
gimplify.o tree-pretty-print.o tree-into-ssa.o \
tree-outof-ssa.o tree-ssa-ccp.o tree-ssa-align.o tree-vn.o \
@@ -1766,6 +1766,10 @@ tree-data-ref.o: tree-data-ref.c $(CONFI
errors.h $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) diagnostic.h \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h \
tree-data-ref.h $(SCEV_H) tree-pass.h $(LAMBDA_H)
+tree-elim-check.o: tree-elim-check.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 \
+ $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h $(LAMBDA_H)
tree-vectorizer.o: tree-vectorizer.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
errors.h $(GGC_H) $(OPTABS_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) diagnostic.h \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) cfgloop.h tree-pass.h $(EXPR_H) \
Index: common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.59
diff -d -u -p -r1.59 common.opt
--- common.opt 28 Oct 2004 03:42:22 -0000 1.59
+++ common.opt 19 Dec 2004 23:20:23 -0000
@@ -848,6 +848,10 @@ ftree-dse
Common Report Var(flag_tree_dse)
Enable dead store elimination
+ftree-elim-checks
+Common Report Var(flag_tree_elim_checks)
+Enable Redundant Checks Elimination
+
ftree-fre
Common Report Var(flag_tree_fre)
Enable Full Redundancy Elimination (FRE) on trees
Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.39.4.1
diff -d -u -p -r1.39.4.1 timevar.def
--- timevar.def 14 Dec 2004 08:45:23 -0000 1.39.4.1
+++ timevar.def 19 Dec 2004 23:20:23 -0000
@@ -91,6 +91,7 @@ DEFTIMEVAR (TV_TREE_LOOP_UNSWITCH , "
DEFTIMEVAR (TV_COMPLETE_UNROLL , "complete unrolling")
DEFTIMEVAR (TV_TREE_VECTORIZATION , "tree loop vectorization")
DEFTIMEVAR (TV_TREE_LINEAR_TRANSFORM , "tree loop linear transforms")
+DEFTIMEVAR (TV_TREE_ELIM_CHECKS , "tree elimination of checks")
DEFTIMEVAR (TV_TREE_LOOP_IVOPTS , "tree iv optimization")
DEFTIMEVAR (TV_TREE_LOOP_INIT , "tree loop init")
DEFTIMEVAR (TV_TREE_LOOP_FINI , "tree loop fini")
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.61.2.2
diff -d -u -p -r2.61.2.2 tree-flow.h
--- tree-flow.h 14 Dec 2004 08:45:39 -0000 2.61.2.2
+++ tree-flow.h 19 Dec 2004 23:20:23 -0000
@@ -746,6 +746,9 @@ void insert_edge_copies (tree, basic_blo
/* In tree-loop-linear.c */
extern void linear_transform_loops (struct loops *);
+/* In tree-elim-checks.c */
+extern void eliminate_redundant_checks (struct loops *);
+
/* In tree-ssa-loop-ivopts.c */
extern bool expr_invariant_in_loop_p (struct loop *, tree);
/* In gimplify.c */
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.61.2.2
diff -d -u -p -r2.61.2.2 tree-optimize.c
--- tree-optimize.c 14 Dec 2004 08:45:45 -0000 2.61.2.2
+++ tree-optimize.c 19 Dec 2004 23:20:23 -0000
@@ -398,6 +398,7 @@ init_tree_optimization_passes (void)
NEXT_PASS (pass_lim);
NEXT_PASS (pass_unswitch);
NEXT_PASS (pass_record_bounds);
+ NEXT_PASS (pass_elim_checks);
NEXT_PASS (pass_linear_transform);
NEXT_PASS (pass_iv_canon);
NEXT_PASS (pass_if_conversion);
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.20.4.2
diff -d -u -p -r2.20.4.2 tree-pass.h
--- tree-pass.h 14 Dec 2004 08:45:48 -0000 2.20.4.2
+++ tree-pass.h 19 Dec 2004 23:20:23 -0000
@@ -165,6 +165,7 @@ extern struct tree_opt_pass pass_expand;
extern struct tree_opt_pass pass_rest_of_compilation;
extern struct tree_opt_pass pass_fre;
extern struct tree_opt_pass pass_linear_transform;
+extern struct tree_opt_pass pass_elim_checks;
extern struct tree_opt_pass pass_maybe_create_global_var;
#endif /* GCC_TREE_PASS_H */
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.15.2.1
diff -d -u -p -r2.15.2.1 tree-ssa-loop-niter.c
--- tree-ssa-loop-niter.c 14 Dec 2004 08:46:00 -0000 2.15.2.1
+++ tree-ssa-loop-niter.c 19 Dec 2004 23:20:24 -0000
@@ -778,6 +778,7 @@ number_of_iterations_exit (struct loop *
case GT_EXPR:
case GE_EXPR:
case NE_EXPR:
+ case EQ_EXPR:
case LT_EXPR:
case LE_EXPR:
break;
@@ -799,6 +800,23 @@ number_of_iterations_exit (struct loop *
if (!simple_iv (loop, stmt, op1, &base1, &step1))
return false;
+ if (code == EQ_EXPR)
+ {
+ tree diff = fold (build2 (MINUS_EXPR, type, base0, base1));
+
+ /* The loop is exited directly when bases differ. */
+ if (diff != NULL_TREE
+ && TREE_CODE (diff) == INTEGER_CST
+ && !integer_zerop (diff))
+ {
+ niter->may_be_zero = boolean_true_node;
+ niter->niter = fold_convert (type, integer_zero_node);
+ return true;
+ }
+ else
+ return false;
+ }
+
niter->niter = NULL_TREE;
number_of_iterations_cond (type, base0, step0, code, base1, step1,
niter);
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop.c,v
retrieving revision 2.21.4.2
diff -d -u -p -r2.21.4.2 tree-ssa-loop.c
--- tree-ssa-loop.c 14 Dec 2004 08:46:00 -0000 2.21.4.2
+++ tree-ssa-loop.c 19 Dec 2004 23:20:24 -0000
@@ -430,3 +430,37 @@ struct tree_opt_pass pass_loop_done =
0 /* letter */
};
+/* Elimination of redundant checks. */
+
+static void
+tree_elim_checks (void)
+{
+ if (!current_loops)
+ return;
+
+ eliminate_redundant_checks (current_loops);
+}
+
+static bool
+gate_tree_elim_checks (void)
+{
+ return flag_tree_elim_checks != 0;
+}
+
+struct tree_opt_pass pass_elim_checks =
+{
+ "elimchk", /* name */
+ gate_tree_elim_checks, /* gate */
+ tree_elim_checks, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_ELIM_CHECKS, /* tv_id */
+ PROP_cfg | PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
+};
+
Index: tree-elim-check.c
===================================================================
RCS file: tree-elim-check.c
diff -N tree-elim-check.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tree-elim-check.c 19 Dec 2004 23:20:24 -0000
@@ -0,0 +1,507 @@
+/* Elimination of redundant checks.
+ Copyright (C) 2004 Free Software Foundation, Inc.
+ Contributed by Sebastian Pop <sebastian.pop@cri.ensmp.fr>
+
+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:
+
+ Compute the scalar evolutions for all the scalar variables of a
+ condition expression, and based on this information performs a
+ proof. The condition is rewritten based on the result of this
+ static proof.
+
+ Examples:
+
+ Example 1: A simple illustration of the algorithm.
+
+ Given the COND_EXPR "if (a < b)" with "a -> {2, +, 1}_1" and "b
+ -> {3, +, 1}_1", the proof consists in comparing these evolution
+ functions: is it always true for a given iteration x that "{2, +,
+ 1}_1 (x) < {3, +, 1}_1 (x)"? The answer is yes, and the test of
+ the condition is consequently replaced by "1".
+
+ Further readings:
+
+ There is no further readings for the moment.
+
+ Based on the fact that this algorithm is similar to the Value
+ Range Propagation you can have a look at the corresponding
+ papers: ...
+*/
+
+#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-data-ref.h"
+#include "tree-scalar-evolution.h"
+#include "tree-pass.h"
+#include "flags.h"
+
+
+/* Given two integer constants A and B, determine whether "A >= B". */
+
+static inline bool
+tree_is_ge (tree a, tree b, bool *res)
+{
+ tree cmp = fold (build (GE_EXPR, boolean_type_node, a, b));
+ if (TREE_CODE (cmp) != INTEGER_CST)
+ return false;
+
+ *res = (tree_int_cst_sgn (cmp) != 0);
+ return true;
+}
+
+/* Determines whether "CHREC0 (x) > CHREC1 (x)" for all the integers x
+ such that "0 <= x < nb_iter". When this property is statically
+ computable, set VALUE and return true. */
+
+static inline bool
+prove_truth_value_gt (tree type, tree chrec0, tree chrec1, bool *value)
+{
+ tree diff = chrec_fold_minus (type, chrec0, chrec1);
+ return chrec_is_positive (diff, value);
+}
+
+/* Determines whether "CHREC0 (x) < CHREC1 (x)" for all the integers
+ x such that "x >= 0". When this property is statically computable,
+ set VALUE and return true. */
+
+static inline bool
+prove_truth_value_lt (tree type, tree chrec0, tree chrec1, bool *value)
+{
+ return prove_truth_value_gt (type, chrec1, chrec0, value);
+}
+
+/* Determines whether "CHREC0 (x) <= CHREC1 (x)" for all the integers
+ x such that "x >= 0". When this property is statically computable,
+ set VALUE and return true. */
+
+static inline bool
+prove_truth_value_le (tree type, tree chrec0, tree chrec1, bool *value)
+{
+ if (prove_truth_value_gt (type, chrec0, chrec1, value))
+ {
+ *value = !*value;
+ return true;
+ }
+
+ return false;
+}
+
+/* Determines whether "CHREC0 (x) >= CHREC1 (x)" for all the integers
+ x such that "x >= 0". When this property is statically computable,
+ set VALUE and return true. */
+
+static inline bool
+prove_truth_value_ge (tree type, tree chrec0, tree chrec1, bool *value)
+{
+ if (prove_truth_value_gt (type, chrec1, chrec0, value))
+ {
+ *value = !*value;
+ return true;
+ }
+
+ return false;
+}
+
+/* Determines whether "CHREC0 (x) == CHREC1 (x)" for all the integers
+ x such that "x >= 0". When this property is statically computable,
+ set VALUE and return true. */
+
+static inline bool
+prove_truth_value_eq (tree type, tree chrec0, tree chrec1, bool *value)
+{
+ tree diff = chrec_fold_minus (type, chrec0, chrec1);
+
+ if (TREE_CODE (diff) == INTEGER_CST)
+ {
+ if (integer_zerop (diff))
+ *value = true;
+
+ else
+ *value = false;
+
+ return true;
+ }
+
+ else
+ return false;
+}
+
+/* Determines whether "CHREC0 (x) != CHREC1 (x)" for all the integers
+ x such that "x >= 0". When this property is statically computable,
+ set VALUE and return true. */
+
+static inline bool
+prove_truth_value_ne (tree type, tree chrec0, tree chrec1, bool *value)
+{
+ if (prove_truth_value_eq (type, chrec0, chrec1, value))
+ {
+ *value = !*value;
+ return true;
+ }
+
+ return false;
+}
+
+/* Try to determine whether "CHREC0 (x) CODE CHREC1 (x)", using
+ symbolic computations. When this property is computable, set VALUE
+ and return true. */
+
+static bool
+prove_truth_value_symbolic (enum tree_code code, tree chrec0, tree chrec1,
+ bool *value)
+{
+ tree type0 = chrec_type (chrec0);
+ tree type1 = chrec_type (chrec1);
+
+ /* Disabled for the moment. */
+ return false;
+
+ if (type0 != type1)
+ return false;
+
+ switch (code)
+ {
+ case EQ_EXPR:
+ return prove_truth_value_eq (type1, chrec0, chrec1, value);
+
+ case NE_EXPR:
+ return prove_truth_value_ne (type1, chrec0, chrec1, value);
+
+ case LT_EXPR:
+ return prove_truth_value_lt (type1, chrec0, chrec1, value);
+
+ case LE_EXPR:
+ return prove_truth_value_le (type1, chrec0, chrec1, value);
+
+ case GT_EXPR:
+ return prove_truth_value_gt (type1, chrec0, chrec1, value);
+
+ case GE_EXPR:
+ return prove_truth_value_ge (type1, chrec0, chrec1, value);
+
+ default:
+ return false;
+ }
+}
+
+/* Return the negation of the comparison code. */
+
+static inline enum tree_code
+not_code (enum tree_code code)
+{
+ switch (code)
+ {
+ case EQ_EXPR:
+ return NE_EXPR;
+ case NE_EXPR:
+ return EQ_EXPR;
+ case LT_EXPR:
+ return GE_EXPR;
+ case LE_EXPR:
+ return GT_EXPR;
+ case GT_EXPR:
+ return LE_EXPR;
+ case GE_EXPR:
+ return LT_EXPR;
+
+ default:
+ return code;
+ }
+}
+
+/* Determine whether "CHREC0 (x) CODE CHREC1 (x)", for all the
+ integers x such that "0 <= x <= NB_ITERS_IN_LOOP". When this
+ property is statically computable, set VALUE and return true. */
+
+static bool
+prove_truth_value (tree cond,
+ enum tree_code code,
+ tree chrec0,
+ tree chrec1,
+ bool *value)
+{
+ bool val = false;
+ tree nb_iters_in_then = chrec_dont_know;
+ tree nb_iters_in_else = chrec_dont_know;
+ struct tree_niter_desc niter_desc;
+ struct loop *loop = loop_containing_stmt (cond);
+ tree nb_iters_in_loop = number_of_iterations_in_loop (loop);
+ tree type;
+ basic_block bb;
+ edge e;
+ edge_iterator ei;
+
+ if (chrec_contains_undetermined (nb_iters_in_loop))
+ return prove_truth_value_symbolic (code, chrec0, chrec1, value);
+
+ /* Compute the number of iterations that fall in the THEN clause,
+ and the number of iterations that fall in the ELSE clause. */
+ bb = bb_for_stmt (cond);
+ if (EDGE_COUNT (bb->succs) != 2)
+ return false;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (e->flags & EDGE_FALSE_VALUE)
+ {
+ if (!number_of_iterations_exit (loop, e, &niter_desc))
+ return false;
+
+ type = TREE_TYPE (niter_desc.niter);
+ if (integer_nonzerop (niter_desc.may_be_zero))
+ nb_iters_in_then = build_int_cst (type, 0);
+ else if (integer_zerop (niter_desc.may_be_zero))
+ nb_iters_in_then = niter_desc.niter;
+ }
+
+ if (e->flags & EDGE_TRUE_VALUE)
+ {
+ if (!number_of_iterations_exit (loop, e, &niter_desc))
+ return false;
+
+ type = TREE_TYPE (niter_desc.niter);
+ if (integer_nonzerop (niter_desc.may_be_zero))
+ nb_iters_in_else = build_int_cst (type, 0);
+ else if (integer_zerop (niter_desc.may_be_zero))
+ nb_iters_in_else = niter_desc.niter;
+ }
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (nb_iters_in_loop = ");
+ print_generic_expr (dump_file, nb_iters_in_loop, 0);
+ fprintf (dump_file, ")\n (nb_iters_in_then = ");
+ print_generic_expr (dump_file, nb_iters_in_then, 0);
+ fprintf (dump_file, ")\n (nb_iters_in_else = ");
+ print_generic_expr (dump_file, nb_iters_in_else, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ if (chrec_contains_undetermined (nb_iters_in_then)
+ || chrec_contains_undetermined (nb_iters_in_else))
+ return prove_truth_value_symbolic (code, chrec0, chrec1, value);
+
+ if (nb_iters_in_then == chrec_known
+ && integer_zerop (nb_iters_in_else))
+ {
+ *value = true;
+ return true;
+ }
+
+ if (nb_iters_in_else == chrec_known
+ && integer_zerop (nb_iters_in_then))
+ {
+ *value = false;
+ return true;
+ }
+
+ if (TREE_CODE (nb_iters_in_then) == INTEGER_CST
+ && TREE_CODE (nb_iters_in_else) == INTEGER_CST)
+ {
+ if (integer_zerop (nb_iters_in_then)
+ && tree_is_ge (nb_iters_in_else, nb_iters_in_loop, &val)
+ && val)
+ {
+ *value = false;
+ return true;
+ }
+
+ if (integer_zerop (nb_iters_in_else)
+ && tree_is_ge (nb_iters_in_then, nb_iters_in_loop, &val)
+ && val)
+ {
+ *value = true;
+ return true;
+ }
+ }
+
+ return prove_truth_value_symbolic (code, chrec0, chrec1, value);
+}
+
+/* Remove the check by setting the condition COND to VALUE. */
+
+static inline void
+remove_redundant_check (tree cond, bool value)
+{
+ /* A dead COND_EXPR means the condition is dead. We don't change any
+ flow, just replace the expression with a constant. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Replacing one of the conditions.\n");
+
+ if (value == true)
+ COND_EXPR_COND (cond) = boolean_true_node;
+
+ else
+ COND_EXPR_COND (cond) = boolean_false_node;
+
+ modify_stmt (cond);
+}
+
+/* If the condition TEST is decidable at compile time, then eliminate
+ the check. */
+
+static void
+try_eliminate_check (tree cond)
+{
+ bool value;
+ tree test, opnd0, opnd1;
+ tree chrec0, chrec1;
+ struct loop *loop = loop_containing_stmt (cond);
+ tree nb_iters = number_of_iterations_in_loop (loop);
+ enum tree_code code;
+
+ if (chrec_contains_undetermined (nb_iters))
+ return;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "(try_eliminate_check \n");
+ fprintf (dump_file, " (cond = ");
+ print_generic_expr (dump_file, cond, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ test = COND_EXPR_COND (cond);
+ code = TREE_CODE (test);
+ switch (code)
+ {
+ case SSA_NAME:
+ /* Matched "if (opnd0)" ie, "if (opnd0 != 0)". */
+ opnd0 = test;
+ chrec0 = instantiate_parameters
+ (loop, analyze_scalar_evolution (loop, opnd0));
+ if (chrec_contains_undetermined (chrec0))
+ goto end;
+
+ chrec1 = fold_convert (TREE_TYPE (opnd0), integer_zero_node);
+ code = NE_EXPR;
+ break;
+
+ case LT_EXPR:
+ case LE_EXPR:
+ case GT_EXPR:
+ case GE_EXPR:
+ case EQ_EXPR:
+ case NE_EXPR:
+ opnd0 = TREE_OPERAND (test, 0);
+ opnd1 = TREE_OPERAND (test, 1);
+
+ chrec0 = instantiate_parameters
+ (loop, analyze_scalar_evolution (loop, opnd0));
+ chrec1 = instantiate_parameters
+ (loop, analyze_scalar_evolution (loop, opnd1));
+
+ if (chrec_contains_undetermined (chrec0)
+ || chrec_contains_undetermined (chrec1))
+ goto end;
+
+ break;
+
+ default:
+ goto end;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " (test = ");
+ print_generic_expr (dump_file, test, 0);
+ fprintf (dump_file, ")\n (loop_nb = %d)\n", loop->num);
+ fprintf (dump_file, " (nb_iters = ");
+ print_generic_expr (dump_file, nb_iters, 0);
+ fprintf (dump_file, ")\n (chrec0 = ");
+ print_generic_expr (dump_file, chrec0, 0);
+ fprintf (dump_file, ")\n (chrec1 = ");
+ print_generic_expr (dump_file, chrec1, 0);
+ fprintf (dump_file, ")\n");
+ }
+
+ if (prove_truth_value (cond, code, chrec0, chrec1, &value))
+ remove_redundant_check (cond, value);
+
+ end:;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, ")\n");
+}
+
+/* Walk over all the statements, searching for conditional statements.
+
+ A better way to determine the conditional expressions that are good
+ candidates for elimination would be needed. For the moment
+ systematically search the conditional expressions over the whole
+ function. */
+
+void
+eliminate_redundant_checks (struct loops *loops)
+{
+ basic_block bb;
+ block_stmt_iterator bsi;
+ unsigned i;
+
+ /* Scan the loops. */
+ for (i = 1; i < loops->num; i++)
+ flow_loop_scan (loops->parray[i], LOOP_ALL);
+
+ bb = BASIC_BLOCK (0);
+ if (bb && bb->loop_father)
+ FOR_EACH_BB (bb)
+ {
+ struct loop *loop = bb->loop_father;
+
+ /* Don't try to prove anything about the loop exit
+ conditions: avoid the block that contains the condition
+ that guards the exit of the loop. */
+ if (!loop->exit_edges
+ || loop->exit_edges[0]->src == bb)
+ continue;
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree expr = bsi_stmt (bsi);
+
+ switch (TREE_CODE (expr))
+ {
+ case COND_EXPR:
+ try_eliminate_check (expr);
+ break;
+
+ default:
+ break;
+ }
+ }
+ }
+}
+
Index: ChangeLog.autovect
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.autovect,v
retrieving revision 1.1.2.13
diff -d -u -p -r1.1.2.13 ChangeLog.autovect
--- ChangeLog.autovect 16 Dec 2004 21:01:03 -0000 1.1.2.13
+++ ChangeLog.autovect 19 Dec 2004 23:20:24 -0000
@@ -1,3 +1,20 @@
+2004-12-20 Sebastian Pop <pop@cri.ensmp.fr>
+
+ * Makefile.in (OBJS-common): Add tree-elim-check.o.
+ (tree-elim-check.o): New.
+ * common.opt (ftree-elim-checks): New.
+ * timevar.def (TV_TREE_ELIM_CHECKS): New.
+ * tree-flow.h (eliminate_redundant_checks): Declared.
+ * tree-optimize.c (init_tree_optimization_passes): Execute
+ pass_elim_checks.
+ * tree-pass.h (pass_elim_checks): Declare.
+ * tree-ssa-loop-niter.c (number_of_iterations_exit): Handle a
+ special case of EQ_EXPR.
+ * tree-ssa-loop.c (tree_elim_checks, gate_tree_elim_checks): New.
+ (pass_elim_checks): Defined.
+ * doc/invoke.texi (-ftree-elim-checks): Document the flag.
+ * tree-elim-check.c: New file, adapted from LNO-branch.
+
2004-12-16 Devang Patel <dpatel@apple.com>
* tree-ssa-forwprop.c (replacable_use_in_cond_expr): Add SSA_NAME check
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.557.2.1
diff -d -u -p -r1.557.2.1 invoke.texi
--- doc/invoke.texi 14 Dec 2004 08:53:18 -0000 1.557.2.1
+++ doc/invoke.texi 19 Dec 2004 23:20:24 -0000
@@ -321,6 +321,7 @@ Objective-C and Objective-C++ Dialects}.
-ftree-loop-linear -ftree-loop-im -ftree-loop-ivcanon -fivopts @gol
-ftree-dominator-opts -ftree-dse -ftree-copyrename @gol
-ftree-ch -ftree-sra -ftree-ter -ftree-lrs -ftree-fre -ftree-vectorize @gol
+-ftree-elim-checks @gol
--param @var{name}=@var{value}
-O -O0 -O1 -O2 -O3 -Os}
@@ -4654,6 +4655,11 @@ at @option{-O} and higher.
Perform linear loop transformations on tree. This flag can improve cache
performance and allow further loop optimizations to take place.
+@item -ftree-elim-checks
+Perform redundant checks elimination. This pass tries to statically
+prove that one of the branches of a condition is always taken,
+eliminating other dead branches.
+
@item -ftree-lim
Perform loop invariant motion on trees. This pass moves only invartiants that
would be hard to handle on rtl level (function calls, operations that expand to
Index: testsuite/gcc.dg/tree-ssa/pr17100.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/pr17100.c
diff -N testsuite/gcc.dg/tree-ssa/pr17100.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/tree-ssa/pr17100.c 19 Dec 2004 23:20:24 -0000
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftree-elim-checks -fdump-tree-elimchk-all" } */
+
+void bar (void);
+
+void foo ()
+{
+ int i;
+ for (i = 0; i < 10; i++)
+ {
+ bar ();
+
+ /* The following call to "bar ()" should be removed. */
+ if (i == -5) bar ();
+ }
+}
+
+/* { dg-final { scan-tree-dump-times "Replacing one of the conditions" 1 "elimchk"} } */
Index: testsuite/ChangeLog.autovect
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/Attic/ChangeLog.autovect,v
retrieving revision 1.1.2.4
diff -d -u -p -r1.1.2.4 ChangeLog.autovect
--- testsuite/ChangeLog.autovect 15 Dec 2004 20:12:33 -0000 1.1.2.4
+++ testsuite/ChangeLog.autovect 19 Dec 2004 23:20:24 -0000
@@ -1,3 +1,7 @@
+2004-12-20 Sebastian Pop <pop@cri.ensmp.fr>
+
+ * gcc.dg/tree-ssa/pr17100.c: New test.
+
2004-12-15 Dorit Naishlos <dorit@il.ibm.com>
* gcc.dg/vect/vect-92.c: New test.