OSDN Git Service

2008-04-02 Richard Guenther <rguenther@suse.de>
authorrguenth <rguenth@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 2 Apr 2008 12:54:08 +0000 (12:54 +0000)
committerrguenth <rguenth@138bc75d-0d04-0410-961f-82ee72b054a4>
Wed, 2 Apr 2008 12:54:08 +0000 (12:54 +0000)
PR tree-optimization/14495
PR tree-optimization/34793
* tree-vrp.c (struct switch_update): New structure.
(to_remove_edges, to_update_switch_stmts): New VECs.
(simplify_switch_using_ranges): New function.  Remove not taken
case labels and edges.
(simplify_stmt_using_ranges): Call it.
(identify_jump_threads): Mark edges we have queued for removal
so we don't thread them.
(execute_vrp): Remove edges queued for removal, update SWITCH_STMT
case label vector.
* tree-cfg.c (group_case_labels): Deal with missing default label.
(tree_verify_flow_info): Allow missing default label.
* stmt.c (emit_case_bit_tests): Deal with NULL default_label.
(emit_case_nodes): Likewise.
(expand_case): Do not rely on the default label to be present.
* expr.c (try_casesi): Deal with NULL default_label.
(do_tablejump): Likewise.

* gcc.dg/tree-ssa/vrp41.c: New testcase.
* gcc.dg/tree-ssa/vrp42.c: Likewise.

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

gcc/ChangeLog
gcc/expr.c
gcc/stmt.c
gcc/testsuite/ChangeLog
gcc/testsuite/gcc.dg/tree-ssa/vrp41.c [new file with mode: 0644]
gcc/testsuite/gcc.dg/tree-ssa/vrp42.c [new file with mode: 0644]
gcc/tree-cfg.c
gcc/tree-vrp.c

index c9d8a48..2bd5c04 100644 (file)
@@ -1,6 +1,27 @@
 2008-04-02  Richard Guenther  <rguenther@suse.de>
 
        PR tree-optimization/14495
+       PR tree-optimization/34793
+       * tree-vrp.c (struct switch_update): New structure.
+       (to_remove_edges, to_update_switch_stmts): New VECs.
+       (simplify_switch_using_ranges): New function.  Remove not taken
+       case labels and edges.
+       (simplify_stmt_using_ranges): Call it.
+       (identify_jump_threads): Mark edges we have queued for removal
+       so we don't thread them.
+       (execute_vrp): Remove edges queued for removal, update SWITCH_STMT
+       case label vector.
+       * tree-cfg.c (group_case_labels): Deal with missing default label.
+       (tree_verify_flow_info): Allow missing default label.
+       * stmt.c (emit_case_bit_tests): Deal with NULL default_label.
+       (emit_case_nodes): Likewise.
+       (expand_case): Do not rely on the default label to be present.
+       * expr.c (try_casesi): Deal with NULL default_label.
+       (do_tablejump): Likewise.
+
+2008-04-02  Richard Guenther  <rguenther@suse.de>
+
+       PR tree-optimization/14495
        * tree-vrp.c (vrp_visit_cond_stmt): Do not handle
        SWITCH_EXPR here ...
        (vrp_visit_switch_stmt): ... but here (new function).
index dbb2b4c..a2bd86c 100644 (file)
@@ -9851,8 +9851,9 @@ try_casesi (tree index_type, tree index_expr, tree minval, tree range,
                           index_expr, minval);
       minval = integer_zero_node;
       index = expand_normal (index_expr);
-      emit_cmp_and_jump_insns (rangertx, index, LTU, NULL_RTX,
-                              omode, 1, default_label);
+      if (default_label)
+        emit_cmp_and_jump_insns (rangertx, index, LTU, NULL_RTX,
+                                omode, 1, default_label);
       /* Now we can safely truncate.  */
       index = convert_to_mode (index_mode, index, 0);
     }
@@ -9931,8 +9932,9 @@ do_tablejump (rtx index, enum machine_mode mode, rtx range, rtx table_label,
      or equal to the minimum value of the range and less than or equal to
      the maximum value of the range.  */
 
-  emit_cmp_and_jump_insns (index, range, GTU, NULL_RTX, mode, 1,
-                          default_label);
+  if (default_label)
+    emit_cmp_and_jump_insns (index, range, GTU, NULL_RTX, mode, 1,
+                            default_label);
 
   /* If index is in range, it must fit in Pmode.
      Convert to Pmode so we can index with it.  */
index 35ba37b..6f8d494 100644 (file)
@@ -2258,8 +2258,9 @@ emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
 
   mode = TYPE_MODE (index_type);
   expr = expand_normal (range);
-  emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
-                          default_label);
+  if (default_label)
+    emit_cmp_and_jump_insns (index, expr, GTU, NULL_RTX, mode, 1,
+                            default_label);
 
   index = convert_to_mode (word_mode, index, 0);
   index = expand_binop (word_mode, ashl_optab, const1_rtx,
@@ -2274,7 +2275,8 @@ emit_case_bit_tests (tree index_type, tree index_expr, tree minval,
                               word_mode, 1, test[i].label);
     }
 
-  emit_jump (default_label);
+  if (default_label)
+    emit_jump (default_label);
 }
 
 #ifndef HAVE_casesi
@@ -2320,7 +2322,7 @@ expand_case (tree exp)
   struct case_node *case_list = 0;
 
   /* Label to jump to if no case matches.  */
-  tree default_label_decl;
+  tree default_label_decl = NULL_TREE;
 
   alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool",
                                                  sizeof (struct case_node),
@@ -2338,18 +2340,21 @@ expand_case (tree exp)
     {
       tree elt;
       bitmap label_bitmap;
+      int vl = TREE_VEC_LENGTH (vec);
 
       /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
         expressions being INTEGER_CST.  */
       gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
 
-      /* The default case is at the end of TREE_VEC.  */
-      elt = TREE_VEC_ELT (vec, TREE_VEC_LENGTH (vec) - 1);
-      gcc_assert (!CASE_HIGH (elt));
-      gcc_assert (!CASE_LOW (elt));
-      default_label_decl = CASE_LABEL (elt);
+      /* The default case, if ever taken, is at the end of TREE_VEC.  */
+      elt = TREE_VEC_ELT (vec, vl - 1);
+      if (!CASE_LOW (elt) && !CASE_HIGH (elt))
+       {
+         default_label_decl = CASE_LABEL (elt);
+         --vl;
+       }
 
-      for (i = TREE_VEC_LENGTH (vec) - 1; --i >= 0; )
+      for (i = vl - 1; i >= 0; --i)
        {
          tree low, high;
          elt = TREE_VEC_ELT (vec, i);
@@ -2368,7 +2373,8 @@ expand_case (tree exp)
 
 
       before_case = start = get_last_insn ();
-      default_label = label_rtx (default_label_decl);
+      if (default_label_decl)
+       default_label = label_rtx (default_label_decl);
 
       /* Get upper and lower bounds of case values.  */
 
@@ -2413,7 +2419,8 @@ expand_case (tree exp)
         type, so we may still get a zero here.  */
       if (count == 0)
        {
-         emit_jump (default_label);
+         if (default_label)
+           emit_jump (default_label);
           free_alloc_pool (case_node_pool);
          return;
        }
@@ -2509,7 +2516,8 @@ expand_case (tree exp)
               && estimate_case_costs (case_list));
          balance_case_nodes (&case_list, NULL);
          emit_case_nodes (index, case_list, default_label, index_type);
-         emit_jump (default_label);
+         if (default_label)
+           emit_jump (default_label);
        }
       else
        {
@@ -2559,9 +2567,10 @@ expand_case (tree exp)
            }
 
          /* Fill in the gaps with the default.  */
-         for (i = 0; i < ncases; i++)
-           if (labelvec[i] == 0)
-             labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
+         if (default_label)
+           for (i = 0; i < ncases; i++)
+             if (labelvec[i] == 0)
+               labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
 
          /* Output the table.  */
          emit_label (table_label);
@@ -3043,7 +3052,8 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
              emit_case_nodes (index, node->left, default_label, index_type);
              /* If left-hand subtree does nothing,
                 go to default.  */
-             emit_jump (default_label);
+             if (default_label)
+               emit_jump (default_label);
 
              /* Code branches here for the right-hand subtree.  */
              expand_label (test_label);
@@ -3178,7 +3188,8 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
            {
              /* If the left-hand subtree fell through,
                 don't let it fall into the right-hand subtree.  */
-             emit_jump (default_label);
+             if (default_label)
+               emit_jump (default_label);
 
              expand_label (test_label);
              emit_case_nodes (index, node->right, default_label, index_type);
index 03ac5b4..432e9e0 100644 (file)
@@ -1,6 +1,13 @@
 2008-04-02  Richard Guenther  <rguenther@suse.de>
 
        PR tree-optimization/14495
+       PR tree-optimization/34793
+       * gcc.dg/tree-ssa/vrp41.c: New testcase.
+       * gcc.dg/tree-ssa/vrp42.c: Likewise.
+
+2008-04-02  Richard Guenther  <rguenther@suse.de>
+
+       PR tree-optimization/14495
        * gcc.dg/tree-ssa/vrp40.c: New testcase.
 
 2008-04-02  Eric Botcazou  <ebotcazou@adacore.com>
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp41.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp41.c
new file mode 100644 (file)
index 0000000..d573fbb
--- /dev/null
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+void bar0 (void);
+void bar1 (void);
+void bar2 (void);
+void bar3 (void);
+
+void
+foo (int a)
+{
+  if (a < 100)
+    return;
+  if (200 < a)
+    return;
+
+  switch (a)
+    {
+    case  99: bar0 (); return;
+    case 100: bar1 (); return;
+    case 101: bar2 (); return;
+    case 102: bar3 (); return;
+    }
+}
+
+/* { dg-final { scan-tree-dump-not "case 99:" "vrp1" } } */
+/* { dg-final { cleanup-tree-dump "vrp1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp42.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp42.c
new file mode 100644 (file)
index 0000000..79eb22c
--- /dev/null
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -Wuninitialized" } */
+
+int foo(int val)
+{
+  int tmp;
+  if ((val > 5) && (val < 8))
+    {
+      switch (val)
+        {
+        case 6:
+          tmp = 1;
+          break;
+        case 7:
+          tmp = 2;
+          break;
+        }
+      return tmp; /* { dg-bogus "used uninitialized" } */
+    }
+  return 0;
+}
+
index 944b31f..70d0404 100644 (file)
@@ -1060,18 +1060,23 @@ group_case_labels (void)
          tree labels = SWITCH_LABELS (stmt);
          int old_size = TREE_VEC_LENGTH (labels);
          int i, j, new_size = old_size;
-         tree default_case = TREE_VEC_ELT (labels, old_size - 1);
-         tree default_label;
+         tree default_case = NULL_TREE;
+         tree default_label = NULL_TREE;
 
          /* The default label is always the last case in a switch
-            statement after gimplification.  */
-         default_label = CASE_LABEL (default_case);
+            statement after gimplification if it was not optimized
+            away.  */
+         if (!CASE_LOW (TREE_VEC_ELT (labels, old_size - 1))
+             && !CASE_HIGH (TREE_VEC_ELT (labels, old_size - 1)))
+           {
+             default_case = TREE_VEC_ELT (labels, old_size - 1);
+             default_label = CASE_LABEL (default_case);
+             old_size--;
+           }
 
-         /* Look for possible opportunities to merge cases.
-            Ignore the last element of the label vector because it
-            must be the default case.  */
+         /* Look for possible opportunities to merge cases.  */
           i = 0;
-         while (i < old_size - 1)
+         while (i < old_size)
            {
              tree base_case, base_label, base_high;
              base_case = TREE_VEC_ELT (labels, i);
@@ -1095,7 +1100,7 @@ group_case_labels (void)
              /* Try to merge case labels.  Break out when we reach the end
                 of the label vector or when we cannot merge the next case
                 label with the current one.  */
-             while (i < old_size - 1)
+             while (i < old_size)
                {
                  tree merge_case = TREE_VEC_ELT (labels, i);
                  tree merge_label = CASE_LABEL (merge_case);
@@ -4604,13 +4609,16 @@ tree_verify_flow_info (void)
 
            /* Verify that the case labels are sorted.  */
            prev = TREE_VEC_ELT (vec, 0);
-           for (i = 1; i < n - 1; ++i)
+           for (i = 1; i < n; ++i)
              {
                tree c = TREE_VEC_ELT (vec, i);
                if (! CASE_LOW (c))
                  {
-                   error ("found default case not at end of case vector");
-                   err = 1;
+                   if (i != n - 1)
+                     {
+                       error ("found default case not at end of case vector");
+                       err = 1;
+                     }
                    continue;
                  }
                if (! tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c)))
@@ -4624,11 +4632,9 @@ tree_verify_flow_info (void)
                  }
                prev = c;
              }
-           if (CASE_LOW (TREE_VEC_ELT (vec, n - 1)))
-             {
-               error ("no default case found at end of case vector");
-               err = 1;
-             }
+           /* VRP will remove the default case if it can prove it will
+              never be executed.  So do not verify there always exists
+              a default case here.  */
 
            FOR_EACH_EDGE (e, ei, bb->succs)
              {
index 1d8ade7..6563528 100644 (file)
@@ -104,6 +104,16 @@ static value_range_t **vr_value;
    node.  */
 static int *vr_phi_edge_counts;
 
+typedef struct {
+  tree stmt;
+  tree vec;
+} switch_update;
+
+static VEC (edge, heap) *to_remove_edges;
+DEF_VEC_O(switch_update);
+DEF_VEC_ALLOC_O(switch_update, heap);
+static VEC (switch_update, heap) *to_update_switch_stmts;
+
 
 /* Return the maximum value for TYPEs base type.  */
 
@@ -6298,6 +6308,106 @@ simplify_cond_using_ranges (tree stmt)
     }
 }
 
+/* Simplify a switch statement using the value range of the switch
+   argument.  */
+
+static void
+simplify_switch_using_ranges (tree stmt)
+{
+  tree op = TREE_OPERAND (stmt, 0);
+  value_range_t *vr;
+  bool take_default;
+  edge e;
+  edge_iterator ei;
+  size_t i = 0, j = 0, n, n2;
+  tree vec, vec2;
+  switch_update su;
+
+  if (TREE_CODE (op) != SSA_NAME)
+    return;
+
+  vr = get_value_range (op);
+
+  /* We can only handle integer ranges.  */
+  if (vr->type != VR_RANGE
+      || symbolic_range_p (vr))
+    return;
+
+  /* Find case label for min/max of the value range.  */
+  vec = SWITCH_LABELS (stmt);
+  n = TREE_VEC_LENGTH (vec);
+  take_default = !find_case_label_index (vec, 0, vr->min, &i);
+  take_default |= !find_case_label_index (vec, i, vr->max, &j);
+
+  /* If the case label range is continuous, we do not need to
+     preserve the default case label.  Verify that.  */
+  if (!take_default && j > i)
+    {
+      tree low, high;
+      size_t k;
+
+      high = CASE_LOW (TREE_VEC_ELT (vec, i));
+      if (CASE_HIGH (TREE_VEC_ELT (vec, i)))
+       high = CASE_HIGH (TREE_VEC_ELT (vec, i));
+      for (k = i + 1; k <= j; ++k)
+       {
+         low = CASE_LOW (TREE_VEC_ELT (vec, k));
+         if (!integer_onep (int_const_binop (MINUS_EXPR, low, high, 0)))
+           {
+             take_default = true;
+             break;
+           }
+         high = low;
+         if (CASE_HIGH (TREE_VEC_ELT (vec, k)))
+           high = CASE_HIGH (TREE_VEC_ELT (vec, k));
+       }
+    }
+
+  /* Bail out if this is just all edges taken.  */
+  if (i == 0
+      && j == n - 2
+      && take_default)
+    return;
+
+  /* Build a new vector of taken case labels.  */
+  vec2 = make_tree_vec (j - i + 1 + (int)take_default);
+  for (n2 = 0; i <= j; ++i, ++n2)
+    TREE_VEC_ELT (vec2, n2) = TREE_VEC_ELT (vec, i);
+
+  /* Add the default edge, if necessary.  */
+  if (take_default)
+    TREE_VEC_ELT (vec2, n2++) = TREE_VEC_ELT (vec, n - 1);
+
+  /* Mark needed edges.  */
+  for (i = 0; i < n2; ++i)
+    {
+      e = find_edge (bb_for_stmt (stmt),
+                    label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2, i))));
+      e->aux = (void *)-1;
+    }
+
+  /* Queue not needed edges for later removal.  */
+  FOR_EACH_EDGE (e, ei, bb_for_stmt (stmt)->succs)
+    {
+      if (e->aux == (void *)-1)
+       {
+         e->aux = NULL;
+         continue;
+       }
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+       {
+         fprintf (dump_file, "removing unreachable case label\n");
+       }
+      VEC_safe_push (edge, heap, to_remove_edges, e);
+    }
+
+  /* And queue an update for the stmt.  */
+  su.stmt = stmt;
+  su.vec = vec2;
+  VEC_safe_push (switch_update, heap, to_update_switch_stmts, &su);
+}
+
 /* Simplify STMT using ranges if possible.  */
 
 void
@@ -6324,9 +6434,9 @@ simplify_stmt_using_ranges (tree stmt)
     }
   else if (TREE_CODE (stmt) == COND_EXPR
           && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
-    {
-      simplify_cond_using_ranges (stmt);
-    }
+    simplify_cond_using_ranges (stmt);
+  else if (TREE_CODE (stmt) == SWITCH_EXPR)
+    simplify_switch_using_ranges (stmt);
 }
 
 /* Stack of dest,src equivalency pairs that need to be restored after
@@ -6378,6 +6488,8 @@ identify_jump_threads (void)
 {
   basic_block bb;
   tree dummy;
+  int i;
+  edge e;
 
   /* Ugh.  When substituting values earlier in this pass we can
      wipe the dominance information.  So rebuild the dominator
@@ -6391,6 +6503,11 @@ identify_jump_threads (void)
      recompute it.  */
   mark_dfs_back_edges ();
 
+  /* Do not thread across edges we are about to remove.  Just marking
+     them as EDGE_DFS_BACK will do.  */
+  for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i)
+    e->flags |= EDGE_DFS_BACK;
+
   /* Allocate our unwinder stack to unwind any temporary equivalences
      that might be recorded.  */
   stack = VEC_alloc (tree, heap, 20);
@@ -6436,7 +6553,6 @@ identify_jump_threads (void)
              && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
        {
          edge_iterator ei;
-         edge e;
 
          /* We've got a block with multiple predecessors and multiple
             successors which also ends in a suitable conditional.  For
@@ -6603,6 +6719,10 @@ record_numbers_of_iterations (void)
 static unsigned int
 execute_vrp (void)
 {
+  int i;
+  edge e;
+  switch_update *su;
+
   loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
   scev_initialize ();
@@ -6620,10 +6740,27 @@ execute_vrp (void)
      ranges are corrected.  */
   record_numbers_of_iterations ();
 
+  to_remove_edges = VEC_alloc (edge, heap, 10);
+  to_update_switch_stmts = VEC_alloc (switch_update, heap, 5);
+
   vrp_initialize ();
   ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
   vrp_finalize ();
 
+  /* Remove dead edges from SWITCH_EXPR optimization.  This leaves the
+     CFG in a broken state and requires a cfg_cleanup run.  */
+  for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i)
+    remove_edge (e);
+  /* Update SWITCH_EXPR case label vector.  */
+  for (i = 0; VEC_iterate (switch_update, to_update_switch_stmts, i, su); ++i)
+    SWITCH_LABELS (su->stmt) = su->vec;
+
+  if (VEC_length (edge, to_remove_edges) > 0)
+    free_dominance_info (CDI_DOMINATORS);
+
+  VEC_free (edge, heap, to_remove_edges);
+  VEC_free (switch_update, heap, to_update_switch_stmts);
+
   /* ASSERT_EXPRs must be removed before finalizing jump threads
      as finalizing jump threads calls the CFG cleanup code which
      does not properly handle ASSERT_EXPRs.  */