OSDN Git Service

* tree-vrp.c (set_value_range_to_nonnegative): New function.
authorlaw <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Fri, 17 Feb 2006 04:15:32 +0000 (04:15 +0000)
committerlaw <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Fri, 17 Feb 2006 04:15:32 +0000 (04:15 +0000)
(vrp_expr_computes_nonnegative, ssa_name_nonnegative_p): Likewise.
(ssa_name_nonzero_p): Likewise.
(get_value_range): Return NULL if VRP is not running.
(extract_range_from_expr): Fallback to tree_expr_XXX_p if
VRP routines do not discover a range.
(vrp_finalize): Clear VR_VALUE to indicate VRP is not running.
* tree.h (ssa_name_nonzero_p, ssa_name_nonnegative_p): Prototype.
* fold-const.c (tree_expr_nonzero_p): For SSA_NAMEs, query VRP.
(tree_expr_nonnegative_p): Similarly.
* tree-ssa-dom.c (nonzero_vars, nonzero_vars_stack): Remove.
(restore_nonzero_vars_to_original_value): Remove.
(unsafe_associative_fp_binop): Remove.
(tree_ssa_dominator_optimize): Remove initialization and
finalization of nonzero_vars and nonzero_vars_stack.
(dom_opt_initialize_block): No longer push marker on
nonzero_vars_stack.
(dom_opt_finalize_block): No longer call
restore_nonzero_vars_to_original_value.
(record_equivalences_from_phis): No longer look for
nonzero PHI arguments.
(cprop_into_successor_phis): No longer propagate nonzero
property into PHI arguments.  Lose unused argument.  Caller
updated.
(record_equivalences_from_stmt): No longer record nonzero
values for SSA_NAMEs.
(lookup_avail_expr): No longer use nonzero_vars.

* gcc.dg/tree-ssa/vrp24.c: Update expected output.
* gcc.dg/tree-ssa/vrp26.c: New test.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@111175 138bc75d-0d04-0410-961f-82ee72b054a4

gcc/ChangeLog
gcc/fold-const.c
gcc/testsuite/ChangeLog
gcc/testsuite/gcc.dg/tree-ssa/vrp24.c
gcc/testsuite/gcc.dg/tree-ssa/vrp26.c [new file with mode: 0644]
gcc/tree-ssa-dom.c
gcc/tree-vrp.c
gcc/tree.h

index 57696b6..79edc91 100644 (file)
@@ -1,5 +1,33 @@
 2006-02-16  Jeff Law  <law@redhat.com>
 
+       * tree-vrp.c (set_value_range_to_nonnegative): New function.
+       (vrp_expr_computes_nonnegative, ssa_name_nonnegative_p): Likewise.
+       (ssa_name_nonzero_p): Likewise.
+       (get_value_range): Return NULL if VRP is not running.
+       (extract_range_from_expr): Fallback to tree_expr_XXX_p if
+       VRP routines do not discover a range.
+       (vrp_finalize): Clear VR_VALUE to indicate VRP is not running.
+       * tree.h (ssa_name_nonzero_p, ssa_name_nonnegative_p): Prototype.
+       * fold-const.c (tree_expr_nonzero_p): For SSA_NAMEs, query VRP.
+       (tree_expr_nonnegative_p): Similarly.
+       * tree-ssa-dom.c (nonzero_vars, nonzero_vars_stack): Remove.
+       (restore_nonzero_vars_to_original_value): Remove.
+       (unsafe_associative_fp_binop): Remove.
+       (tree_ssa_dominator_optimize): Remove initialization and
+       finalization of nonzero_vars and nonzero_vars_stack.
+       (dom_opt_initialize_block): No longer push marker on
+       nonzero_vars_stack.
+       (dom_opt_finalize_block): No longer call
+       restore_nonzero_vars_to_original_value.
+       (record_equivalences_from_phis): No longer look for
+       nonzero PHI arguments.
+       (cprop_into_successor_phis): No longer propagate nonzero
+       property into PHI arguments.  Lose unused argument.  Caller
+       updated.
+       (record_equivalences_from_stmt): No longer record nonzero
+       values for SSA_NAMEs.
+       (lookup_avail_expr): No longer use nonzero_vars.
+
        * stor-layout.c (set_sizetype): Set TYPE_MAX_VALUE properly
        for sizetype when sizetype is unsigned.
 
index 2683dab..7413883 100644 (file)
@@ -11054,6 +11054,11 @@ tree_expr_nonnegative_p (tree t)
 
   switch (TREE_CODE (t))
     {
+    case SSA_NAME:
+      /* Query VRP to see if it has recorded any information about
+        the range of this object.  */
+      return ssa_name_nonnegative_p (t);
+
     case ABS_EXPR:
       /* We can't return 1 if flag_wrapv is set because
         ABS_EXPR<INT_MIN> = INT_MIN.  */
@@ -11317,6 +11322,11 @@ tree_expr_nonzero_p (tree t)
 
   switch (TREE_CODE (t))
     {
+    case SSA_NAME:
+      /* Query VRP to see if it has recorded any information about
+        the range of this object.  */
+      return ssa_name_nonzero_p (t);
+
     case ABS_EXPR:
       return tree_expr_nonzero_p (TREE_OPERAND (t, 0));
 
index ffacb6a..cb41751 100644 (file)
@@ -1,3 +1,8 @@
+2006-02-16  Jeff Law  <law@redhat.com>
+
+       * gcc.dg/tree-ssa/vrp24.c: Update expected output.
+       * gcc.dg/tree-ssa/vrp26.c: New test.
+
 2006-02-16  Joseph S. Myers  <joseph@codesourcery.com>
 
        PR target/20353
index b181cfa..85e5b62 100644 (file)
@@ -79,11 +79,13 @@ L7:
 
 }
 
-
-
-/* The n_sets > 0 test can be simplified into n_sets == 1 since the
-   only way to reach the test is when n_sets <= 1, and the only value
-   which satisfies both conditions is n_sets == 1.  */
-/* { dg-final { scan-tree-dump-times "Simplified relational" 1 "vrp1" } } */
+/* The first n_sets > 0 test can be simplfiied into n_sets == 1 since
+   n_sets can only have the values [0, 1] as it's the result of a
+   boolean operation.
+
+   The second n_sets > 0 test can also be simplified into n_sets == 1
+   as the only way to reach the tests is when n_sets <= 1 and the only
+   value which satisfies both conditions is n_sets == 1.  */
+/* { dg-final { scan-tree-dump-times "Simplified relational" 2 "vrp1" } } */
 /* { dg-final { cleanup-tree-dump "vrp1" } } */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp26.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp26.c
new file mode 100644 (file)
index 0000000..6215416
--- /dev/null
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+int 
+foo(int a)
+{
+  int z = a | 1;
+  return z != 0;
+}
+
+/* VRP should optimize this to a trivial "return 1".   */
+/* { dg-final { scan-tree-dump-times "return 1" 1 "vrp1" } } * /
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
+
+
+
+
index 4802572..c79a4ca 100644 (file)
@@ -135,17 +135,6 @@ struct expr_hash_elt
    restored during finalization of this block.  */
 static VEC(tree,heap) *const_and_copies_stack;
 
-/* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
-   know their exact value.  */
-static bitmap nonzero_vars;
-
-/* Stack of SSA_NAMEs which need their NONZERO_VARS property cleared
-   when the current block is finalized. 
-
-   A NULL entry is used to mark the end of names needing their 
-   entry in NONZERO_VARS cleared during finalization of this block.  */
-static VEC(tree,heap) *nonzero_vars_stack;
-
 /* Track whether or not we have changed the control flow graph.  */
 static bool cfg_altered;
 
@@ -194,8 +183,6 @@ static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
 static void remove_local_expressions_from_table (void);
 static void restore_vars_to_original_value (void);
 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
-static void restore_nonzero_vars_to_original_value (void);
-static inline bool unsafe_associative_fp_binop (tree);
 
 
 /* Allocate an EDGE_INFO for edge E and attach it to E.
@@ -261,9 +248,7 @@ tree_ssa_dominator_optimize (void)
   avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
   avail_exprs_stack = VEC_alloc (tree, heap, 20);
   const_and_copies_stack = VEC_alloc (tree, heap, 20);
-  nonzero_vars_stack = VEC_alloc (tree, heap, 20);
   stmts_to_rescan = VEC_alloc (tree, heap, 20);
-  nonzero_vars = BITMAP_ALLOC (NULL);
   need_eh_cleanup = BITMAP_ALLOC (NULL);
 
   /* Setup callbacks for the generic dominator tree walker.  */
@@ -367,13 +352,11 @@ tree_ssa_dominator_optimize (void)
   /* And finalize the dominator walker.  */
   fini_walk_dominator_tree (&walk_data);
 
-  /* Free nonzero_vars.  */
-  BITMAP_FREE (nonzero_vars);
+  /* Free asserted bitmaps and stacks.  */
   BITMAP_FREE (need_eh_cleanup);
   
   VEC_free (tree, heap, avail_exprs_stack);
   VEC_free (tree, heap, const_and_copies_stack);
-  VEC_free (tree, heap, nonzero_vars_stack);
   VEC_free (tree, heap, stmts_to_rescan);
 }
 
@@ -466,7 +449,6 @@ dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
      far to unwind when we finalize this block.  */
   VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);
   VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
-  VEC_safe_push (tree, heap, nonzero_vars_stack, NULL_TREE);
 
   record_equivalences_from_incoming_edge (bb);
 
@@ -540,23 +522,6 @@ remove_local_expressions_from_table (void)
     }
 }
 
-/* Use the SSA_NAMES in LOCALS to restore TABLE to its original
-   state, stopping when there are LIMIT entries left in LOCALs.  */
-
-static void
-restore_nonzero_vars_to_original_value (void)
-{
-  while (VEC_length (tree, nonzero_vars_stack) > 0)
-    {
-      tree name = VEC_pop (tree, nonzero_vars_stack);
-
-      if (name == NULL)
-       break;
-
-      bitmap_clear_bit (nonzero_vars, SSA_NAME_VERSION (name));
-    }
-}
-
 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
    CONST_AND_COPIES to its original state, stopping when we hit a
    NULL marker.  */
@@ -728,7 +693,6 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
     }
 
   remove_local_expressions_from_table ();
-  restore_nonzero_vars_to_original_value ();
   restore_vars_to_original_value ();
 
   /* If we queued any statements to rescan in this block, then
@@ -750,11 +714,7 @@ dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
 
    Ignoring any alternatives which are the same as the result, if
    all the alternatives are equal, then the PHI node creates an
-   equivalence.
-
-   Additionally, if all the PHI alternatives are known to have a nonzero
-   value, then the result of this PHI is known to have a nonzero value,
-   even if we do not know its exact value.  */
+   equivalence.  */
 
 static void
 record_equivalences_from_phis (basic_block bb)
@@ -802,17 +762,6 @@ record_equivalences_from_phis (basic_block bb)
       if (i == PHI_NUM_ARGS (phi)
          && may_propagate_copy (lhs, rhs))
        SSA_NAME_VALUE (lhs) = rhs;
-
-      /* Now see if we know anything about the nonzero property for the
-        result of this PHI.  */
-      for (i = 0; i < PHI_NUM_ARGS (phi); i++)
-       {
-         if (!PHI_ARG_NONZERO (phi, i))
-           break;
-       }
-
-      if (i == PHI_NUM_ARGS (phi))
-       bitmap_set_bit (nonzero_vars, SSA_NAME_VERSION (PHI_RESULT (phi)));
     }
 }
 
@@ -944,26 +893,6 @@ htab_statistics (FILE *file, htab_t htab)
           htab_collisions (htab));
 }
 
-/* Record the fact that VAR has a nonzero value, though we may not know
-   its exact value.  Note that if VAR is already known to have a nonzero
-   value, then we do nothing.  */
-
-static void
-record_var_is_nonzero (tree var)
-{
-  int indx = SSA_NAME_VERSION (var);
-
-  if (bitmap_bit_p (nonzero_vars, indx))
-    return;
-
-  /* Mark it in the global table.  */
-  bitmap_set_bit (nonzero_vars, indx);
-
-  /* Record this SSA_NAME so that we can reset the global table
-     when we leave this block.  */
-  VEC_safe_push (tree, heap, nonzero_vars_stack, var);
-}
-
 /* Enter a statement into the true/false expression hash table indicating
    that the condition COND has the value VALUE.  */
 
@@ -1213,19 +1142,6 @@ record_equality (tree x, tree y)
   record_const_or_copy_1 (x, y, prev_x);
 }
 
-/* Return true, if it is ok to do folding of an associative expression.
-   EXP is the tree for the associative expression.  */ 
-
-static inline bool
-unsafe_associative_fp_binop (tree exp)
-{
-  enum tree_code code = TREE_CODE (exp);
-  return !(!flag_unsafe_math_optimizations
-           && (code == MULT_EXPR || code == PLUS_EXPR
-              || code == MINUS_EXPR)
-           && FLOAT_TYPE_P (TREE_TYPE (exp)));
-}
-
 /* Returns true when STMT is a simple iv increment.  It detects the
    following situation:
    
@@ -1269,14 +1185,11 @@ simple_iv_increment_p (tree stmt)
 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
    known value for that SSA_NAME (or NULL if no value is known).  
 
-   NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
-   even if we don't know their precise value.
-
-   Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
-   nodes of the successors of BB.  */
+   Propagate values from CONST_AND_COPIES into the PHI nodes of the
+   successors of BB.  */
 
 static void
-cprop_into_successor_phis (basic_block bb, bitmap nonzero_vars)
+cprop_into_successor_phis (basic_block bb)
 {
   edge e;
   edge_iterator ei;
@@ -1309,11 +1222,6 @@ cprop_into_successor_phis (basic_block bb, bitmap nonzero_vars)
          if (TREE_CODE (orig) != SSA_NAME)
            continue;
 
-         /* If the alternative is known to have a nonzero value, record
-            that fact in the PHI node itself for future use.  */
-         if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (orig)))
-           PHI_ARG_NONZERO (phi, indx) = true;
-
          /* If we have *ORIG_P in our constant/copy table, then replace
             ORIG_P with its value in our constant/copy table.  */
          new = SSA_NAME_VALUE (orig);
@@ -1518,7 +1426,7 @@ propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
                             basic_block bb)
 {
   record_edge_info (bb);
-  cprop_into_successor_phis (bb, nonzero_vars);
+  cprop_into_successor_phis (bb);
 }
 
 /* Search for redundant computations in STMT.  If any are found, then
@@ -1626,7 +1534,6 @@ record_equivalences_from_stmt (tree stmt,
 {
   tree lhs = TREE_OPERAND (stmt, 0);
   enum tree_code lhs_code = TREE_CODE (lhs);
-  int i;
 
   if (lhs_code == SSA_NAME)
     {
@@ -1645,48 +1552,8 @@ record_equivalences_from_stmt (tree stmt,
          && (TREE_CODE (rhs) == SSA_NAME
              || is_gimple_min_invariant (rhs)))
        SSA_NAME_VALUE (lhs) = rhs;
-
-      if (tree_expr_nonzero_p (rhs))
-       record_var_is_nonzero (lhs);
     }
 
-  /* Look at both sides for pointer dereferences.  If we find one, then
-     the pointer must be nonnull and we can enter that equivalence into
-     the hash tables.  */
-  if (flag_delete_null_pointer_checks)
-    for (i = 0; i < 2; i++)
-      {
-       tree t = TREE_OPERAND (stmt, i);
-
-       /* Strip away any COMPONENT_REFs.  */
-       while (TREE_CODE (t) == COMPONENT_REF)
-         t = TREE_OPERAND (t, 0);
-
-       /* Now see if this is a pointer dereference.  */
-       if (INDIRECT_REF_P (t))
-          {
-           tree op = TREE_OPERAND (t, 0);
-
-           /* If the pointer is a SSA variable, then enter new
-              equivalences into the hash table.  */
-           while (TREE_CODE (op) == SSA_NAME)
-             {
-               tree def = SSA_NAME_DEF_STMT (op);
-
-               record_var_is_nonzero (op);
-
-               /* And walk up the USE-DEF chains noting other SSA_NAMEs
-                  which are known to have a nonzero value.  */
-               if (def
-                   && TREE_CODE (def) == MODIFY_EXPR
-                   && TREE_CODE (TREE_OPERAND (def, 1)) == NOP_EXPR)
-                 op = TREE_OPERAND (TREE_OPERAND (def, 1), 0);
-               else
-                 break;
-             }
-         }
-      }
-
   /* A memory store, even an aliased store, creates a useful
      equivalence.  By exchanging the LHS and RHS, creating suitable
      vops and recording the result in the available expression table,
@@ -2047,24 +1914,6 @@ lookup_avail_expr (tree stmt, bool insert)
       return NULL_TREE;
     }
 
-  /* If this is an equality test against zero, see if we have recorded a
-     nonzero value for the variable in question.  */
-  if ((TREE_CODE (element->rhs) == EQ_EXPR
-       || TREE_CODE  (element->rhs) == NE_EXPR)
-      && TREE_CODE (TREE_OPERAND (element->rhs, 0)) == SSA_NAME
-      && integer_zerop (TREE_OPERAND (element->rhs, 1)))
-    {
-      int indx = SSA_NAME_VERSION (TREE_OPERAND (element->rhs, 0));
-
-      if (bitmap_bit_p (nonzero_vars, indx))
-       {
-         tree t = element->rhs;
-         free (element);
-         return constant_boolean_node (TREE_CODE (t) != EQ_EXPR,
-                                       TREE_TYPE (t));
-       }
-    }
-
   /* Finally try to find the expression in the main expression hash table.  */
   slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
                                   (insert ? INSERT : NO_INSERT));
index a0950fe..b6b6d40 100644 (file)
@@ -191,6 +191,14 @@ copy_value_range (value_range_t *to, value_range_t *from)
   set_value_range (to, from->type, from->min, from->max, from->equiv);
 }
 
+/* Set value range VR to a non-negative range of type TYPE.  */
+
+static inline void
+set_value_range_to_nonnegative (value_range_t *vr, tree type)
+{
+  tree zero = build_int_cst (type, 0);
+  set_value_range (vr, VR_RANGE, zero, TYPE_MAX_VALUE (type), vr->equiv);
+}
 
 /* Set value range VR to a non-NULL range of type TYPE.  */
 
@@ -236,8 +244,10 @@ set_value_range_to_undefined (value_range_t *vr)
 }
 
 
-/* Return value range information for VAR.  Create an empty range
-   if none existed.  */
+/* Return value range information for VAR.  
+
+   If we have no values ranges recorded (ie, VRP is not running), then
+   return NULL.  Otherwise create an empty range if none existed for VAR.  */
 
 static value_range_t *
 get_value_range (tree var)
@@ -246,6 +256,10 @@ get_value_range (tree var)
   tree sym;
   unsigned ver = SSA_NAME_VERSION (var);
 
+  /* If we have no recorded ranges, then return NULL.  */
+  if (! vr_value)
+    return NULL;
+
   vr = vr_value[ver];
   if (vr)
     return vr;
@@ -358,6 +372,14 @@ symbolic_range_p (value_range_t *vr)
           || !is_gimple_min_invariant (vr->max));
 }
 
+/* Like tree_expr_nonnegative_p, but this function uses value ranges
+   obtained so far.  */
+
+static bool
+vrp_expr_computes_nonnegative (tree expr)
+{
+  return tree_expr_nonnegative_p (expr);
+}
 
 /* Like tree_expr_nonzero_p, but this function uses value ranges
    obtained so far.  */
@@ -629,6 +651,50 @@ range_includes_zero_p (value_range_t *vr)
   return (value_inside_range (zero, vr) == 1);
 }
 
+/* Return true if T, an SSA_NAME, is known to be nonnegative.  Return
+   false otherwise or if no value range information is available.  */
+
+bool
+ssa_name_nonnegative_p (tree t)
+{
+  value_range_t *vr = get_value_range (t);
+
+  if (!vr)
+    return false;
+
+  /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
+     which would return a useful value should be encoded as a VR_RANGE.  */
+  if (vr->type == VR_RANGE)
+    {
+      int result = compare_values (vr->min, integer_zero_node);
+
+      return (result == 0 || result == 1);
+    }
+  return false;
+}
+
+/* Return true if T, an SSA_NAME, is known to be nonzero.  Return
+   false otherwise or if no value range information is available.  */
+
+bool
+ssa_name_nonzero_p (tree t)
+{
+  value_range_t *vr = get_value_range (t);
+
+  if (!vr)
+    return false;
+
+  /* A VR_RANGE which does not include zero is a nonzero value.  */
+  if (vr->type == VR_RANGE && !symbolic_range_p (vr))
+    return ! range_includes_zero_p (vr);
+
+  /* A VR_ANTI_RANGE which does include zero is a nonzero value.  */
+  if (vr->type == VR_ANTI_RANGE && !symbolic_range_p (vr))
+    return range_includes_zero_p (vr);
+
+  return false;
+}
+
 
 /* When extracting ranges from X_i = ASSERT_EXPR <Y_j, pred>, we will
    initially consider X_i and Y_j equivalent, so the equivalence set
@@ -1868,10 +1934,21 @@ extract_range_from_expr (value_range_t *vr, tree expr)
     extract_range_from_comparison (vr, expr);
   else if (is_gimple_min_invariant (expr))
     set_value_range (vr, VR_RANGE, expr, expr, NULL);
-  else if (vrp_expr_computes_nonzero (expr))
-    set_value_range_to_nonnull (vr, TREE_TYPE (expr));
   else
     set_value_range_to_varying (vr);
+
+  /* If we got a varying range from the tests above, try a final
+     time to derive a nonnegative or nonzero range.  This time
+     relying primarily on generic routines in fold in conjunction
+     with range data.  */
+  if (vr->type == VR_VARYING)
+    {
+      if (INTEGRAL_TYPE_P (TREE_TYPE (expr))
+         && vrp_expr_computes_nonnegative (expr))
+        set_value_range_to_nonnegative (vr, TREE_TYPE (expr));
+      else if (vrp_expr_computes_nonzero (expr))
+        set_value_range_to_nonnull (vr, TREE_TYPE (expr));
+    }
 }
 
 /* Given a range VR, a LOOP and a variable VAR, determine whether it
@@ -4428,6 +4505,10 @@ vrp_finalize (void)
 
   free (single_val_range);
   free (vr_value);
+
+  /* So that we can distinguish between VRP data being available
+     and not available.  */
+  vr_value = NULL;
 }
 
 
index f0cb29d..3a321eb 100644 (file)
@@ -4520,6 +4520,10 @@ extern int tree_map_eq (const void *, const void *);
 extern tree tree_mem_ref_addr (tree, tree);
 extern void copy_mem_ref_info (tree, tree);
 
+/* In tree-vrp.c */
+extern bool ssa_name_nonzero_p (tree);
+extern bool ssa_name_nonnegative_p (tree);
+
 /* In tree-object-size.c.  */
 extern void init_object_sizes (void);
 extern void fini_object_sizes (void);