This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Fix PR14495 (1/2)
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Cc: Diego Novillo <dnovillo at google dot com>
- Date: Fri, 28 Mar 2008 15:52:01 +0100 (CET)
- Subject: [PATCH] Fix PR14495 (1/2)
This patch from last year fixes one part of PR14495 (VRP cannot
simulate a switch stmt properly). Namely it teaches VRP the case
of a single executable edge in a switch stmt. I believe this
it likely to happen (only) with C++ and inlining after exposing
constant propagation opportunities.
It also introduces the find_case_label_index helper which will be
needed in (2/2).
Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for mainline?
Thanks,
Richard.
2008-03-28 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).
(find_case_label_index): New helper function.
(vrp_visit_stmt): Dispatch to vrp_visit_switch_stmt.
* gcc.dg/tree-ssa/vrp38.c: New testcase.
Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig 2008-03-20 14:51:35.000000000 +0100
--- gcc/tree-vrp.c 2008-03-20 14:56:22.000000000 +0100
*************** vrp_visit_cond_stmt (tree stmt, edge *ta
*** 5300,5310 ****
bool sop;
*taken_edge_p = NULL;
-
- /* FIXME. Handle SWITCH_EXPRs. */
- if (TREE_CODE (stmt) == SWITCH_EXPR)
- return SSA_PROP_VARYING;
-
cond = COND_EXPR_COND (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
--- 5300,5305 ----
*************** vrp_visit_cond_stmt (tree stmt, edge *ta
*** 5398,5403 ****
--- 5393,5539 ----
}
+ /* Searches the case label vector VEC for the index *IDX the CASE_LABEL
+ includes the value VAL. The search starts at index START_IDX and
+ true is returned if *IDX corresponds to such an index. False is
+ returned in case VAL hits the default case label and *IDX in this
+ case is the next higher or the next lower case label index. */
+
+ static bool
+ find_case_label_index (tree vec, size_t start_idx, tree val, size_t *idx)
+ {
+ size_t n = TREE_VEC_LENGTH (vec);
+ size_t low, high, i = start_idx;
+
+ /* Find case label for minimum of the value range or the next one. */
+ for (low = start_idx - 1, high = n - 1; high - low > 1; )
+ {
+ tree t;
+ int cmp;
+ i = (high + low) / 2;
+ t = TREE_VEC_ELT (vec, i);
+
+ /* Cache the result of comparing CASE_LOW and val. */
+ cmp = tree_int_cst_compare (CASE_LOW (t), val);
+
+ if (cmp > 0)
+ high = i;
+ else
+ low = i;
+
+ if (CASE_HIGH (t) == NULL)
+ {
+ /* A singe-valued case label. */
+ if (cmp == 0)
+ {
+ *idx = i;
+ return true;
+ }
+ }
+ else
+ {
+ /* A case range. We can only handle integer ranges. */
+ if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
+ {
+ *idx = i;
+ return true;
+ }
+ }
+ }
+
+ *idx = i;
+ return false;
+ }
+
+ /* Visit switch statement STMT. If we can determine which edge
+ will be taken out of STMT's basic block, record it in
+ *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
+ SSA_PROP_VARYING. */
+
+ static enum ssa_prop_result
+ vrp_visit_switch_stmt (tree stmt, edge *taken_edge_p)
+ {
+ tree op, val;
+ value_range_t *vr;
+ size_t i = 0, j = 0, n;
+ tree vec;
+ bool min_take_default, max_take_default;
+
+ *taken_edge_p = NULL;
+ op = TREE_OPERAND (stmt, 0);
+ if (TREE_CODE (op) != SSA_NAME)
+ return SSA_PROP_VARYING;
+
+ vr = get_value_range (op);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\nVisiting switch expression with operand ");
+ print_generic_expr (dump_file, op, 0);
+ fprintf (dump_file, " with known range ");
+ dump_value_range (dump_file, vr);
+ fprintf (dump_file, "\n");
+ }
+
+ if (vr->type != VR_RANGE
+ || symbolic_range_p (vr))
+ return SSA_PROP_VARYING;
+
+ /* Find the single edge that is taken from the switch expression. */
+ vec = SWITCH_LABELS (stmt);
+ n = TREE_VEC_LENGTH (vec);
+
+ /* Find case label for minimum of the value range or the next one. */
+ min_take_default = !find_case_label_index (vec, 0, vr->min, &i);
+
+ /* Find case label for maximum of the value range or the previous one. */
+ max_take_default = !find_case_label_index (vec, i, vr->max, &j);
+
+ /* Check if we reach the default label only. */
+ if (j < i)
+ val = TREE_VEC_ELT (vec, n - 1);
+ /* Check if we reach exactly one label and not the default label. */
+ else if (i == j
+ && !min_take_default
+ && !max_take_default)
+ val = TREE_VEC_ELT (vec, i);
+ else
+ {
+ /* Check if labels with index i to j are all reaching the same label.
+ If we don't hit a single case label only, the default case also has
+ to branch to the same label. */
+ val = TREE_VEC_ELT (vec, i);
+ if (CASE_LABEL (TREE_VEC_ELT (vec, n - 1)) != CASE_LABEL (val))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " not a single destination for this "
+ "range\n");
+ return SSA_PROP_VARYING;
+ }
+ for (++i; i <= j; ++i)
+ {
+ if (CASE_LABEL (TREE_VEC_ELT (vec, i)) != CASE_LABEL (val))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " not a single destination for this "
+ "range\n");
+ return SSA_PROP_VARYING;
+ }
+ }
+ }
+
+ *taken_edge_p = find_edge (bb_for_stmt (stmt),
+ label_to_block (CASE_LABEL (val)));
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " will take edge to ");
+ print_generic_stmt (dump_file, CASE_LABEL (val), 0);
+ }
+
+ return SSA_PROP_INTERESTING;
+ }
+
+
/* Evaluate statement STMT. If the statement produces a useful range,
return SSA_PROP_INTERESTING and record the SSA name with the
interesting range into *OUTPUT_P.
*************** vrp_visit_stmt (tree stmt, edge *taken_e
*** 5436,5443 ****
|| ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
return vrp_visit_assignment (stmt, output_p);
}
! else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
return vrp_visit_cond_stmt (stmt, taken_edge_p);
/* All other statements produce nothing of interest for VRP, so mark
their outputs varying and prevent further simulation. */
--- 5572,5581 ----
|| ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
return vrp_visit_assignment (stmt, output_p);
}
! else if (TREE_CODE (stmt) == COND_EXPR)
return vrp_visit_cond_stmt (stmt, taken_edge_p);
+ else if (TREE_CODE (stmt) == SWITCH_EXPR)
+ return vrp_visit_switch_stmt (stmt, taken_edge_p);
/* All other statements produce nothing of interest for VRP, so mark
their outputs varying and prevent further simulation. */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp38.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp38.c 2008-03-20 14:56:22.000000000 +0100
***************
*** 0 ****
--- 1,18 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+ int f(int a) {
+ switch (a & 1) {
+ case 0:
+ case 1: return 3;
+ case 2: return 5;
+ case 3: return 7;
+ case 4: return 11;
+ case 5: return 13;
+ case 6: return 17;
+ case 7: return 19;
+ }
+ }
+
+ /* { dg-final { scan-tree-dump "return 3;" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */