[PATCH] Make VRP simulate only executable edges out of SWITCH_STMTs
Richard Guenther
rguenther@suse.de
Mon Apr 16 15:30:00 GMT 2007
This patch (series) makes VRP figure which edges out of a SWITCH_EXPR are
actually executable and communicates this to the propagator engine. The
engine is updated to take a VEC of edges as a result of visit_stmt for
this reason. This allows the propagator to do less work and possibly
iterate less times as well as propagating some ranges ignoring the
non-executable edges (see the testcase).
Here are actually three patches (because I developed them in this order
and tested them in this sequence). The first teaches VRP to tell if
there is only one executable edge out of the SWITCH_EXPR - this is what
the propagator currently handles. The second change changes the
propagator and its users to use a VEC as result for visit_stmt. And the
third one finally updates VRP to make use of the extended interface.
All three patches have been bootstrapped and tested on
x86_64-unknown-linux-gnu. A fourth patch removing never taken case
labels is in development, but adding another worker messing with the CFG
in VRP proves tricky.
Ok for mainline?
Thanks,
Richard.
2007-04-13 Richard Guenther <rguenther@suse.de>
* 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/vrp35.c: New testcase.
2007-04-13 Richard Guenther <rguenther@suse.de>
* tree-ssa-propagate.h (ssa_prop_visit_stmt_fn): Adjust prototype.
* tree-ssa-propagate.c (simulate_stmt): Pass a VEC of edges
as return slot to allow multiple taken edges.
* tree-complex.c (complex_visit_stmt): Adjust prototype.
* tree-ssa-ccp.c (visit_cond_stmt): Adjust for prototype change.
(ccp_visit_stmt): Adjust prototype.
* tree-ssa-copy.c (copy_prop_visit_cond_stmt): Adjust for
prototype change.
(copy_prop_visit_stmt): Adjust prototype.
2007-04-16 Richard Guenther <rguenther@suse.de>
* tree-vrp.c (vrp_visit_switch_stmt): Find and return the
set of edges taken.
Index: tree-vrp.c
===================================================================
*** tree-vrp.c (revision 123778)
--- tree-vrp.c (working copy)
*************** vrp_visit_cond_stmt (tree stmt, edge *ta
*** 4886,4896 ****
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))
--- 4886,4891 ----
*************** vrp_visit_cond_stmt (tree stmt, edge *ta
*** 4984,4989 ****
--- 4979,5125 ----
}
+ /* 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
*** 5022,5029 ****
|| 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. */
--- 5158,5167 ----
|| 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: testsuite/gcc.dg/tree-ssa/vrp35.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/vrp35.c (revision 0)
--- testsuite/gcc.dg/tree-ssa/vrp35.c (revision 0)
***************
*** 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" } } */
2007-04-13 Richard Guenther <rguenther@suse.de>
* tree-ssa-propagate.h (ssa_prop_visit_stmt_fn): Adjust prototype.
* tree-ssa-propagate.c (simulate_stmt): Pass a VEC of edges
as return slot to allow multiple taken edges.
* tree-complex.c (complex_visit_stmt): Adjust prototype.
* tree-ssa-ccp.c (visit_cond_stmt): Adjust for prototype change.
(ccp_visit_stmt): Adjust prototype.
* tree-ssa-copy.c (copy_prop_visit_cond_stmt): Adjust for
prototype change.
(copy_prop_visit_stmt): Adjust prototype.
Index: gcc/tree-complex.c
===================================================================
*** gcc.orig/tree-complex.c 2007-03-11 12:43:47.000000000 +0100
--- gcc/tree-complex.c 2007-04-13 16:20:21.000000000 +0200
*************** init_dont_simulate_again (void)
*** 260,266 ****
/* Evaluate statement STMT against the complex lattice defined above. */
static enum ssa_prop_result
! complex_visit_stmt (tree stmt, edge *taken_edge_p ATTRIBUTE_UNUSED,
tree *result_p)
{
complex_lattice_t new_l, old_l, op1_l, op2_l;
--- 260,266 ----
/* Evaluate statement STMT against the complex lattice defined above. */
static enum ssa_prop_result
! complex_visit_stmt (tree stmt, VEC(edge,heap) **taken_edge_p ATTRIBUTE_UNUSED,
tree *result_p)
{
complex_lattice_t new_l, old_l, op1_l, op2_l;
Index: gcc/tree-ssa-ccp.c
===================================================================
*** gcc.orig/tree-ssa-ccp.c 2007-04-11 12:07:58.000000000 +0200
--- gcc/tree-ssa-ccp.c 2007-04-13 16:22:03.000000000 +0200
*************** visit_assignment (tree stmt, tree *outpu
*** 1328,1337 ****
SSA_PROP_VARYING. */
static enum ssa_prop_result
! visit_cond_stmt (tree stmt, edge *taken_edge_p)
{
prop_value_t val;
basic_block block;
block = bb_for_stmt (stmt);
val = evaluate_stmt (stmt);
--- 1328,1338 ----
SSA_PROP_VARYING. */
static enum ssa_prop_result
! visit_cond_stmt (tree stmt, VEC(edge,heap) **taken_edge_p)
{
prop_value_t val;
basic_block block;
+ edge e;
block = bb_for_stmt (stmt);
val = evaluate_stmt (stmt);
*************** visit_cond_stmt (tree stmt, edge *taken_
*** 1340,1348 ****
to the worklist. If no single edge can be determined statically,
return SSA_PROP_VARYING to feed all the outgoing edges to the
propagation engine. */
! *taken_edge_p = val.value ? find_taken_edge (block, val.value) : 0;
! if (*taken_edge_p)
! return SSA_PROP_INTERESTING;
else
return SSA_PROP_VARYING;
}
--- 1341,1353 ----
to the worklist. If no single edge can be determined statically,
return SSA_PROP_VARYING to feed all the outgoing edges to the
propagation engine. */
! e = val.value ? find_taken_edge (block, val.value) : 0;
! if (e)
! {
! *taken_edge_p = VEC_alloc(edge, heap, 1);
! VEC_quick_push(edge, *taken_edge_p, e);
! return SSA_PROP_INTERESTING;
! }
else
return SSA_PROP_VARYING;
}
*************** visit_cond_stmt (tree stmt, edge *taken_
*** 1358,1364 ****
value, return SSA_PROP_VARYING. */
static enum ssa_prop_result
! ccp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
{
tree def;
ssa_op_iter iter;
--- 1363,1369 ----
value, return SSA_PROP_VARYING. */
static enum ssa_prop_result
! ccp_visit_stmt (tree stmt, VEC(edge,heap) **taken_edge_p, tree *output_p)
{
tree def;
ssa_op_iter iter;
Index: gcc/tree-ssa-copy.c
===================================================================
*** gcc.orig/tree-ssa-copy.c 2007-04-12 11:11:05.000000000 +0200
--- gcc/tree-ssa-copy.c 2007-04-13 16:19:21.000000000 +0200
*************** copy_prop_visit_assignment (tree stmt, t
*** 649,658 ****
SSA_PROP_VARYING. */
static enum ssa_prop_result
! copy_prop_visit_cond_stmt (tree stmt, edge *taken_edge_p)
{
enum ssa_prop_result retval;
tree cond;
cond = COND_EXPR_COND (stmt);
retval = SSA_PROP_VARYING;
--- 649,659 ----
SSA_PROP_VARYING. */
static enum ssa_prop_result
! copy_prop_visit_cond_stmt (tree stmt, VEC(edge,heap) **taken_edge_p)
{
enum ssa_prop_result retval;
tree cond;
+ edge e = NULL;
cond = COND_EXPR_COND (stmt);
retval = SSA_PROP_VARYING;
*************** copy_prop_visit_cond_stmt (tree stmt, ed
*** 683,698 ****
if (folded_cond)
{
basic_block bb = bb_for_stmt (stmt);
! *taken_edge_p = find_taken_edge (bb, folded_cond);
! if (*taken_edge_p)
! retval = SSA_PROP_INTERESTING;
}
}
}
! if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
! (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
return retval;
}
--- 684,703 ----
if (folded_cond)
{
basic_block bb = bb_for_stmt (stmt);
! e = find_taken_edge (bb, folded_cond);
! if (e)
! {
! *taken_edge_p = VEC_alloc(edge, heap, 1);
! VEC_quick_push(edge, *taken_edge_p, e);
! retval = SSA_PROP_INTERESTING;
! }
}
}
}
! if (dump_file && (dump_flags & TDF_DETAILS) && e)
fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
! e->src->index, e->dest->index);
return retval;
}
*************** copy_prop_visit_cond_stmt (tree stmt, ed
*** 709,715 ****
SSA_PROP_VARYING. */
static enum ssa_prop_result
! copy_prop_visit_stmt (tree stmt, edge *taken_edge_p, tree *result_p)
{
enum ssa_prop_result retval;
--- 714,720 ----
SSA_PROP_VARYING. */
static enum ssa_prop_result
! copy_prop_visit_stmt (tree stmt, VEC(edge,heap) **taken_edge_p, tree *result_p)
{
enum ssa_prop_result retval;
Index: gcc/tree-ssa-propagate.c
===================================================================
*** gcc.orig/tree-ssa-propagate.c 2007-03-09 11:51:30.000000000 +0100
--- gcc/tree-ssa-propagate.c 2007-04-13 16:23:24.000000000 +0200
*************** static void
*** 289,295 ****
simulate_stmt (tree stmt)
{
enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
! edge taken_edge = NULL;
tree output_name = NULL_TREE;
/* Don't bother visiting statements that are already
--- 289,295 ----
simulate_stmt (tree stmt)
{
enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
! VEC(edge,heap) *taken_edge = NULL;
tree output_name = NULL_TREE;
/* Don't bother visiting statements that are already
*************** simulate_stmt (tree stmt)
*** 335,341 ****
/* If we know which edge is going to be taken out of this block,
add it to the CFG work list. */
if (taken_edge)
! add_control_edge (taken_edge);
}
}
--- 335,349 ----
/* If we know which edge is going to be taken out of this block,
add it to the CFG work list. */
if (taken_edge)
! {
! int i;
! edge e;
!
! for (i = 0; VEC_iterate (edge, taken_edge, i, e); ++i)
! add_control_edge (e);
!
! VEC_free(edge, heap, taken_edge);
! }
}
}
Index: gcc/tree-ssa-propagate.h
===================================================================
*** gcc.orig/tree-ssa-propagate.h 2007-01-18 14:25:00.000000000 +0100
--- gcc/tree-ssa-propagate.h 2007-04-13 16:19:36.000000000 +0200
*************** typedef struct value_range_d value_range
*** 107,113 ****
/* Call-back functions used by the value propagation engine. */
! typedef enum ssa_prop_result (*ssa_prop_visit_stmt_fn) (tree, edge *, tree *);
typedef enum ssa_prop_result (*ssa_prop_visit_phi_fn) (tree);
--- 107,114 ----
/* Call-back functions used by the value propagation engine. */
! typedef enum ssa_prop_result (*ssa_prop_visit_stmt_fn) (tree, VEC(edge,heap) **,
! tree *);
typedef enum ssa_prop_result (*ssa_prop_visit_phi_fn) (tree);
Index: gcc/tree-vrp.c
===================================================================
*** gcc.orig/tree-vrp.c 2007-04-13 15:47:37.000000000 +0200
--- gcc/tree-vrp.c 2007-04-13 16:28:06.000000000 +0200
*************** vrp_evaluate_conditional (tree cond, tre
*** 4880,4891 ****
SSA_PROP_VARYING. */
static enum ssa_prop_result
! vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
{
tree cond, val;
bool sop;
- *taken_edge_p = NULL;
cond = COND_EXPR_COND (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
--- 4880,4890 ----
SSA_PROP_VARYING. */
static enum ssa_prop_result
! vrp_visit_cond_stmt (tree stmt, VEC(edge,heap) **taken_edge_p)
{
tree cond, val;
bool sop;
cond = COND_EXPR_COND (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
*************** vrp_visit_cond_stmt (tree stmt, edge *ta
*** 4955,4961 ****
if (val)
{
if (!sop)
! *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
--- 4954,4967 ----
if (val)
{
if (!sop)
! {
! edge e = find_taken_edge (bb_for_stmt (stmt), val);
! if (e)
! {
! *taken_edge_p = VEC_alloc(edge, heap, 1);
! VEC_quick_push(edge, *taken_edge_p, e);
! }
! }
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
*************** vrp_visit_cond_stmt (tree stmt, edge *ta
*** 4975,4981 ****
print_generic_stmt (dump_file, val, 0);
}
! return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
}
--- 4981,4987 ----
print_generic_stmt (dump_file, val, 0);
}
! return *taken_edge_p ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
}
*************** find_case_label_index (tree vec, size_t
*** 5037,5043 ****
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;
--- 5043,5049 ----
SSA_PROP_VARYING. */
static enum ssa_prop_result
! vrp_visit_switch_stmt (tree stmt, VEC(edge,heap) **taken_edge_p)
{
tree op, val;
value_range_t *vr;
*************** vrp_visit_switch_stmt (tree stmt, edge *
*** 5045,5051 ****
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;
--- 5051,5056 ----
*************** vrp_visit_switch_stmt (tree stmt, edge *
*** 5107,5114 ****
}
}
! *taken_edge_p = find_edge (bb_for_stmt (stmt),
! label_to_block (CASE_LABEL (val)));
if (dump_file && (dump_flags & TDF_DETAILS))
{
--- 5112,5121 ----
}
}
! *taken_edge_p = VEC_alloc(edge, heap, 1);
! VEC_quick_push(edge, *taken_edge_p,
! find_edge (bb_for_stmt (stmt),
! label_to_block (CASE_LABEL (val))));
if (dump_file && (dump_flags & TDF_DETAILS))
{
*************** vrp_visit_switch_stmt (tree stmt, edge *
*** 5130,5136 ****
If STMT produces a varying value, return SSA_PROP_VARYING. */
static enum ssa_prop_result
! vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
{
tree def;
ssa_op_iter iter;
--- 5137,5143 ----
If STMT produces a varying value, return SSA_PROP_VARYING. */
static enum ssa_prop_result
! vrp_visit_stmt (tree stmt, VEC(edge,heap) **taken_edge_p, tree *output_p)
{
tree def;
ssa_op_iter iter;
2007-04-16 Richard Guenther <rguenther@suse.de>
* tree-vrp.c (vrp_visit_switch_stmt): Find and return the
set of edges taken.
Index: gcc/tree-vrp.c
===================================================================
*** gcc.orig/tree-vrp.c 2007-04-13 16:28:06.000000000 +0200
--- gcc/tree-vrp.c 2007-04-16 14:11:21.000000000 +0200
*************** vrp_visit_switch_stmt (tree stmt, VEC(ed
*** 5047,5055 ****
{
tree op, val;
value_range_t *vr;
! size_t i = 0, j = 0, n;
! tree vec;
! bool min_take_default, max_take_default;
op = TREE_OPERAND (stmt, 0);
if (TREE_CODE (op) != SSA_NAME)
--- 5047,5055 ----
{
tree op, val;
value_range_t *vr;
! size_t i = 0, j = 0, n, n2;
! tree vec, vec2;
! bool take_default;
op = TREE_OPERAND (stmt, 0);
if (TREE_CODE (op) != SSA_NAME)
*************** vrp_visit_switch_stmt (tree stmt, VEC(ed
*** 5065,5128 ****
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 = VEC_alloc(edge, heap, 1);
VEC_quick_push(edge, *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;
}
--- 5065,5123 ----
fprintf (dump_file, "\n");
}
+ /* We only can handle integer ranges. */
if (vr->type != VR_RANGE
|| symbolic_range_p (vr))
return SSA_PROP_VARYING;
! /* 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);
+ /* The following is just conservative. */
+ take_default |= j > 1;
+
+ /* Bail out if this is just all edges taken. */
+ if (i == 0
+ && j == n - 2
+ && take_default)
+ return SSA_PROP_VARYING;
! *taken_edge_p = VEC_alloc(edge, heap, EDGE_COUNT (bb_for_stmt (stmt)->succs));
! /* Add all outgoing edges reached by case labels i to j. To avoid
! duplicate edges we need to sort after case label. */
! 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);
! qsort (&TREE_VEC_ELT (vec2, 0), n2, sizeof (tree), compare_case_labels);
!
! val = TREE_VEC_ELT (vec2, 0);
VEC_quick_push(edge, *taken_edge_p,
find_edge (bb_for_stmt (stmt),
label_to_block (CASE_LABEL (val))));
! for (i = 1; i < n2; ++i)
{
! /* Quickly skip over duplicates. */
! if (CASE_LABEL (TREE_VEC_ELT (vec2, i)) == CASE_LABEL (val))
! continue;
! val = TREE_VEC_ELT (vec2, i);
! VEC_quick_push(edge, *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, " %d out of %d edges are executable\n",
+ VEC_length(edge, *taken_edge_p),
+ EDGE_COUNT (bb_for_stmt (stmt)->succs));
+
return SSA_PROP_INTERESTING;
}
More information about the Gcc-patches
mailing list