--- a/gcc/tree-vrp.c	Fri Feb 12 23:41:23 2010 +0900
+++ b/gcc/tree-vrp.c	Mon May 24 12:47:05 2010 +0900
@@ -1,5 +1,6 @@
 /* Support routines for Value Range Propagation (VRP).
-   Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
+   Free Software Foundation, Inc.
    Contributed by Diego Novillo <dnovillo@redhat.com>.
 
 This file is part of GCC.
@@ -31,6 +32,8 @@
 #include "tree-dump.h"
 #include "timevar.h"
 #include "diagnostic.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
 #include "toplev.h"
 #include "intl.h"
 #include "cfgloop.h"
@@ -763,6 +766,27 @@
 	 && integer_zerop (vr->max);
 }
 
+/* Return true if max and min of VR are INTEGER_CST.  It's not necessary
+   a singleton.  */
+
+static inline bool
+range_int_cst_p (value_range_t *vr)
+{
+  return (vr->type == VR_RANGE
+	  && TREE_CODE (vr->max) == INTEGER_CST
+	  && TREE_CODE (vr->min) == INTEGER_CST
+	  && !TREE_OVERFLOW (vr->max)
+	  && !TREE_OVERFLOW (vr->min));
+}
+
+/* Return true if VR is a INTEGER_CST singleton.  */
+
+static inline bool
+range_int_cst_singleton_p (value_range_t *vr)
+{
+  return (range_int_cst_p (vr)
+	  && tree_int_cst_equal (vr->min, vr->max));
+}
 
 /* Return true if value range VR involves at least one symbol.  */
 
@@ -1342,6 +1366,10 @@
 {
   value_range_t *vr = get_value_range (t);
 
+  if (INTEGRAL_TYPE_P (t)
+      && TYPE_UNSIGNED (t))
+    return true;
+
   if (!vr)
     return false;
 
@@ -1898,9 +1926,9 @@
 
   res = int_const_binop (code, val1, val2, 0);
 
-  /* If we are not using wrapping arithmetic, operate symbolically
-     on -INF and +INF.  */
-  if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
+  /* If we are using unsigned arithmetic, operate symbolically
+     on -INF and +INF as int_const_binop only handles signed overflow.  */
+  if (TYPE_UNSIGNED (TREE_TYPE (val1)))
     {
       int checkz = compare_values (res, val1);
       bool overflow = false;
@@ -1937,6 +1965,10 @@
 	}
 
     }
+  else if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
+    /* If the singed operation wraps then int_const_binop has done
+       everything we want.  */
+    ;
   else if ((TREE_OVERFLOW (res)
 	    && !TREE_OVERFLOW (val1)
 	    && !TREE_OVERFLOW (val2))
@@ -2053,6 +2085,7 @@
       && code != CEIL_DIV_EXPR
       && code != EXACT_DIV_EXPR
       && code != ROUND_DIV_EXPR
+      && code != TRUNC_MOD_EXPR
       && code != RSHIFT_EXPR
       && code != MIN_EXPR
       && code != MAX_EXPR
@@ -2121,6 +2154,7 @@
       && code != CEIL_DIV_EXPR
       && code != EXACT_DIV_EXPR
       && code != ROUND_DIV_EXPR
+      && code != TRUNC_MOD_EXPR
       && (vr0.type == VR_VARYING
 	  || vr1.type == VR_VARYING
 	  || vr0.type != vr1.type
@@ -2471,6 +2505,31 @@
 	    }
 	}
     }
+  else if (code == TRUNC_MOD_EXPR)
+    {
+      bool sop = false;
+      if (vr1.type != VR_RANGE
+	  || symbolic_range_p (&vr1)
+	  || range_includes_zero_p (&vr1)
+	  || vrp_val_is_min (vr1.min))
+	{
+	  set_value_range_to_varying (vr);
+	  return;
+	}
+      type = VR_RANGE;
+      /* Compute MAX <|vr1.min|, |vr1.max|> - 1.  */
+      max = fold_unary_to_constant (ABS_EXPR, TREE_TYPE (vr1.min), vr1.min);
+      if (tree_int_cst_lt (max, vr1.max))
+	max = vr1.max;
+      max = int_const_binop (MINUS_EXPR, max, integer_one_node, 0);
+      /* If the dividend is non-negative the modulus will be
+	 non-negative as well.  */
+      if (TYPE_UNSIGNED (TREE_TYPE (max))
+	  || (vrp_expr_computes_nonnegative (op0, &sop) && !sop))
+	min = build_int_cst (TREE_TYPE (max), 0);
+      else
+	min = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (max), max);
+    }
   else if (code == MINUS_EXPR)
     {
       /* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
@@ -2493,19 +2552,20 @@
     }
   else if (code == BIT_AND_EXPR)
     {
-      if (vr0.type == VR_RANGE
-	  && vr0.min == vr0.max
-	  && TREE_CODE (vr0.max) == INTEGER_CST
-	  && !TREE_OVERFLOW (vr0.max)
-	  && tree_int_cst_sgn (vr0.max) >= 0)
+      bool vr0_int_cst_singleton_p, vr1_int_cst_singleton_p;
+
+      vr0_int_cst_singleton_p = range_int_cst_singleton_p (&vr0);
+      vr1_int_cst_singleton_p = range_int_cst_singleton_p (&vr1);
+
+      if (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
+	min = max = int_const_binop (code, vr0.max, vr1.max, 0);
+      else if (vr0_int_cst_singleton_p
+	       && tree_int_cst_sgn (vr0.max) >= 0)
 	{
 	  min = build_int_cst (expr_type, 0);
 	  max = vr0.max;
 	}
-      else if (vr1.type == VR_RANGE
-	       && vr1.min == vr1.max
-	       && TREE_CODE (vr1.max) == INTEGER_CST
-	       && !TREE_OVERFLOW (vr1.max)
+      else if (vr1_int_cst_singleton_p
 	       && tree_int_cst_sgn (vr1.max) >= 0)
 	{
 	  type = VR_RANGE;
@@ -2520,12 +2580,8 @@
     }
   else if (code == BIT_IOR_EXPR)
     {
-      if (vr0.type == VR_RANGE
-          && vr1.type == VR_RANGE
-	  && TREE_CODE (vr0.min) == INTEGER_CST
-	  && TREE_CODE (vr1.min) == INTEGER_CST
-	  && TREE_CODE (vr0.max) == INTEGER_CST
-	  && TREE_CODE (vr1.max) == INTEGER_CST
+      if (range_int_cst_p (&vr0)
+	  && range_int_cst_p (&vr1)
 	  && tree_int_cst_sgn (vr0.min) >= 0
 	  && tree_int_cst_sgn (vr1.min) >= 0)
 	{
@@ -2710,8 +2766,16 @@
 	   || vr0.type == VR_ANTI_RANGE)
 	  && TREE_CODE (vr0.min) == INTEGER_CST
 	  && TREE_CODE (vr0.max) == INTEGER_CST
-	  && !is_overflow_infinity (vr0.min)
-	  && !is_overflow_infinity (vr0.max)
+	  && (!is_overflow_infinity (vr0.min)
+	      || (vr0.type == VR_RANGE
+		  && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
+		  && needs_overflow_infinity (outer_type)
+		  && supports_overflow_infinity (outer_type)))
+	  && (!is_overflow_infinity (vr0.max)
+	      || (vr0.type == VR_RANGE
+		  && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
+		  && needs_overflow_infinity (outer_type)
+		  && supports_overflow_infinity (outer_type)))
 	  && (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type)
 	      || (vr0.type == VR_RANGE
 		  && integer_zerop (int_const_binop (RSHIFT_EXPR,
@@ -2725,6 +2789,10 @@
 	  new_max = force_fit_type_double (outer_type,
 					   TREE_INT_CST_LOW (vr0.max),
 					   TREE_INT_CST_HIGH (vr0.max), 0, 0);
+	  if (is_overflow_infinity (vr0.min))
+	    new_min = negative_overflow_infinity (outer_type);
+	  if (is_overflow_infinity (vr0.max))
+	    new_max = positive_overflow_infinity (outer_type);
 	  set_and_canonicalize_value_range (vr, vr0.type,
 					    new_min, new_max, NULL);
 	  return;
@@ -3136,7 +3204,7 @@
 adjust_range_with_scev (value_range_t *vr, struct loop *loop,
 			gimple stmt, tree var)
 {
-  tree init, step, chrec, tmin, tmax, min, max, type;
+  tree init, step, chrec, tmin, tmax, min, max, type, tem;
   enum ev_direction dir;
 
   /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
@@ -3157,7 +3225,13 @@
     return;
 
   init = initial_condition_in_loop_num (chrec, loop->num);
+  tem = op_with_constant_singleton_value_range (init);
+  if (tem)
+    init = tem;
   step = evolution_part_in_loop_num (chrec, loop->num);
+  tem = op_with_constant_singleton_value_range (step);
+  if (tem)
+    step = tem;
 
   /* If STEP is symbolic, we can't know whether INIT will be the
      minimum or maximum value in the range.  Also, unless INIT is
@@ -3276,7 +3350,8 @@
     return true;
 
   l = loop_containing_stmt (stmt);
-  if (l == NULL)
+  if (l == NULL
+      || !loop_outer (l))
     return true;
 
   chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
@@ -4831,6 +4906,10 @@
   edge_iterator ei;
   edge e;
 
+  /* If we have X <=> X do not insert an assert expr for that.  */
+  if (loc->expr == loc->val)
+    return false;
+
   cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
   assert_stmt = build_assert_expr_for (cond, name);
   if (loc->e)
@@ -4976,23 +5055,46 @@
 {
   value_range_t* vr = NULL;
   tree low_sub, up_sub;
-  tree low_bound, up_bound = array_ref_up_bound (ref);
+  tree low_bound, up_bound, up_bound_p1;
+  tree base;
+
+  if (TREE_NO_WARNING (ref))
+    return;
 
   low_sub = up_sub = TREE_OPERAND (ref, 1);
-
-  if (!up_bound || TREE_NO_WARNING (ref)
-      || TREE_CODE (up_bound) != INTEGER_CST
-      /* Can not check flexible arrays.  */
-      || (TYPE_SIZE (TREE_TYPE (ref)) == NULL_TREE
-          && TYPE_DOMAIN (TREE_TYPE (ref)) != NULL_TREE
-          && TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (ref))) == NULL_TREE)
-      /* Accesses after the end of arrays of size 0 (gcc
-         extension) and 1 are likely intentional ("struct
-         hack").  */
-      || compare_tree_int (up_bound, 1) <= 0)
+  up_bound = array_ref_up_bound (ref);
+
+  /* Can not check flexible arrays.  */
+  if (!up_bound
+      || TREE_CODE (up_bound) != INTEGER_CST)
     return;
 
+  /* Accesses to trailing arrays via pointers may access storage
+     beyond the types array bounds.  */
+  base = get_base_address (ref);
+  if (base
+      && INDIRECT_REF_P (base))
+    {
+      tree cref, next = NULL_TREE;
+
+      if (TREE_CODE (TREE_OPERAND (ref, 0)) != COMPONENT_REF)
+	return;
+
+      cref = TREE_OPERAND (ref, 0);
+      if (TREE_CODE (TREE_TYPE (TREE_OPERAND (cref, 0))) == RECORD_TYPE)
+	for (next = TREE_CHAIN (TREE_OPERAND (cref, 1));
+	     next && TREE_CODE (next) != FIELD_DECL;
+	     next = TREE_CHAIN (next))
+	  ;
+
+      /* If this is the last field in a struct type or a field in a
+	 union type do not warn.  */
+      if (!next)
+	return;
+    }
+
   low_bound = array_ref_low_bound (ref);
+  up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound, integer_one_node, 0);
 
   if (TREE_CODE (low_sub) == SSA_NAME)
     {
@@ -5017,14 +5119,11 @@
         }
     }
   else if (TREE_CODE (up_sub) == INTEGER_CST
-           && tree_int_cst_lt (up_bound, up_sub)
-           && !tree_int_cst_equal (up_bound, up_sub)
-           && (!ignore_off_by_one
-               || !tree_int_cst_equal (int_const_binop (PLUS_EXPR,
-                                                        up_bound,
-                                                        integer_one_node,
-                                                        0),
-                                       up_sub)))
+	   && (ignore_off_by_one
+	       ? (tree_int_cst_lt (up_bound, up_sub)
+		  && !tree_int_cst_equal (up_bound_p1, up_sub))
+	       : (tree_int_cst_lt (up_bound, up_sub)
+		  || tree_int_cst_equal (up_bound_p1, up_sub))))
     {
       warning_at (location, OPT_Warray_bounds,
 		  "array subscript is above array bounds");
@@ -5122,36 +5221,16 @@
 
   FOR_EACH_BB (bb)
     {
-      /* Skip bb's that are clearly unreachable.  */
-      if (single_pred_p (bb))
-      {
-	int i;
-	bool reachable = true;
-	edge e2;
-	edge e = EDGE_PRED (bb, 0);
-	basic_block pred_bb = e->src;
-	gimple ls = NULL;
-
-	for (i = 0; VEC_iterate (edge, to_remove_edges, i, e2); ++i)
-	  if (e == e2)
-	    {
-	      reachable = false;
-	      break;
-	    }
-
-	if (!reachable)
-	  continue;
-
-	if (!gsi_end_p (gsi_last_bb (pred_bb)))
-	  ls = gsi_stmt (gsi_last_bb (pred_bb));
-
-	if (ls && gimple_code (ls) == GIMPLE_COND
-	    && ((gimple_cond_false_p (ls)
-		 && (EDGE_PRED (bb, 0)->flags & EDGE_TRUE_VALUE))
-		|| (gimple_cond_true_p (ls)
-		    && (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE))))
-	  continue;
-      }
+      edge_iterator ei;
+      edge e;
+      bool executable = false;
+
+      /* Skip blocks that were found to be unreachable.  */
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	executable |= !!(e->flags & EDGE_EXECUTABLE);
+      if (!executable)
+	continue;
+
       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 	{
 	  gimple stmt = gsi_stmt (si);
@@ -5358,7 +5437,6 @@
 	   && TYPE_MAX_VALUE (TREE_TYPE (lhs)))
 	  || POINTER_TYPE_P (TREE_TYPE (lhs))))
     {
-      struct loop *l;
       value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
 
       if (code == GIMPLE_CALL)
@@ -5366,12 +5444,6 @@
       else
 	extract_range_from_assignment (&new_vr, stmt);
 
-      /* If STMT is inside a loop, we may be able to know something
-	 else about the range of LHS by examining scalar evolution
-	 information.  */
-      if (current_loops && (l = loop_containing_stmt (stmt)))
-	adjust_range_with_scev (&new_vr, l, stmt, lhs);
-
       if (update_value_range (lhs, &new_vr))
 	{
 	  *output_p = lhs;
@@ -6275,6 +6347,7 @@
   value_range_t *lhs_vr = get_value_range (lhs);
   value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
   int edges, old_edges;
+  struct loop *l;
 
   copy_value_range (&vr_result, lhs_vr);
 
@@ -6338,6 +6411,13 @@
 	}
     }
 
+  /* If this is a loop PHI node SCEV may known more about its
+     value-range.  */
+  if (current_loops
+      && (l = loop_containing_stmt (phi))
+      && l->header == gimple_bb (phi))
+    adjust_range_with_scev (&vr_result, l, phi, lhs);
+
   if (vr_result.type == VR_VARYING)
     goto varying;
 
@@ -6409,7 +6489,18 @@
   /* If the new range is different than the previous value, keep
      iterating.  */
   if (update_value_range (lhs, &vr_result))
-    return SSA_PROP_INTERESTING;
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Found new range for ");
+	  print_generic_expr (dump_file, lhs, 0);
+	  fprintf (dump_file, ": ");
+	  dump_value_range (dump_file, &vr_result);
+	  fprintf (dump_file, "\n\n");
+	}
+
+      return SSA_PROP_INTERESTING;
+    }
 
   /* Nothing changed, don't add outgoing edges.  */
   return SSA_PROP_NOT_INTERESTING;
@@ -6926,6 +7017,7 @@
 	  fprintf (dump_file, "removing unreachable case label\n");
 	}
       VEC_safe_push (edge, heap, to_remove_edges, e);
+      e->flags &= ~EDGE_EXECUTABLE;
     }
 
   /* And queue an update for the stmt.  */
@@ -7255,7 +7347,7 @@
   substitute_and_fold (single_val_range, vrp_fold_stmt);
 
   if (warn_array_bounds)
-      check_all_array_refs ();
+    check_all_array_refs ();
 
   /* We must identify jump threading opportunities before we release
      the datastructures built by VRP.  */