This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]