This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Teach VRP to derive ranges from SWITCH_EXPR (fix PR21258)
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 12 Apr 2007 16:35:51 +0200 (CEST)
- Subject: [PATCH] Teach VRP to derive ranges from SWITCH_EXPR (fix PR21258)
This adds the ability to VRP to derive ranges from SWITCH_EXPRs, namely
insert ASSERT_EXPRs on the edges like so:
switch (x_1)
{
case 2:
x_2 = ASSERT_EXPR <x_1, x_1 == 2>
...
case 5:
case 9:
case 11:
x_3 = ASSERT_EXPR <x_1, x_1 >= 5>
x_4 = ASSERT_EXPR <x_3, x_3 <= 11>
...
case 12:
default:
...
}
this alone shrinks (checking enabled) tree.o from
text data bss dec hex filename
148023 4 72 148099 24283 tree.o.noopt
to
text data bss dec hex filename
147623 4 72 147699 240f3 tree.o.opt
as it notices that all the tree check macros do not trigger inside
switch arms. As soon as PR30318 is fixed it will be able to do more
simplifications - currently we can only throw our hands in the air if we
see
switch (code)
{
case 5:
if (code < 5 || code > 6)
abort();
as this is written as
case 5:
unsigned tmp = code + 65137;
if (code > 1)
abort();
and on the code + 65137 unsigned overflow our VRP abilities are too weak
and we punt. But we can at least substitute 5 to code in this case
so later passes will clean it up. We miss
case 5:
case 6:
unsigned tmp = code + 65137;
if (code > 1)
abort();
though, as there's nothing to const-prop. To be fixed with PR30318.
Bootstrapped and tested on x86_64-unknown-linux-gnu. I will apply
this to mainline tomorrow.
Richard.
2007-04-11 Richard Guenther <rguenther@suse.de>
PR tree-optimization/21258
* tree-vrp.c (compare_case_labels): New helper.
(find_switch_asserts): New function.
(find_assert_locations): Call it for SWITCH_EXPRs.
* gcc.dg/tree-ssa/vrp34.c: New testcase.
Index: testsuite/gcc.dg/tree-ssa/vrp34.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/vrp34.c (revision 0)
--- testsuite/gcc.dg/tree-ssa/vrp34.c (revision 0)
***************
*** 0 ****
--- 1,20 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+ void bar (void);
+
+ void
+ foo (int a)
+ {
+ switch (a)
+ {
+ case 4:
+ if (a >= 3)
+ if (a <= 5)
+ bar ();
+ }
+ }
+
+ /* { dg-final { scan-tree-dump "Folding predicate a_. > 2 to 1" "vrp1" } } */
+ /* { dg-final { scan-tree-dump "Folding predicate a_. <= 5 to 1" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: tree-vrp.c
===================================================================
*** tree-vrp.c (revision 123735)
--- tree-vrp.c (working copy)
*************** static bool find_assert_locations (basic
*** 3593,3599 ****
/* Determine whether the outgoing edges of BB should receive an
ASSERT_EXPR for each of the operands of BB's LAST statement.
! The last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
If any of the sub-graphs rooted at BB have an interesting use of
the predicate operands, an assert location node is added to the
--- 3593,3599 ----
/* Determine whether the outgoing edges of BB should receive an
ASSERT_EXPR for each of the operands of BB's LAST statement.
! The last statement of BB must be a COND_EXPR.
If any of the sub-graphs rooted at BB have an interesting use of
the predicate operands, an assert location node is added to the
*************** find_conditional_asserts (basic_block bb
*** 3666,3671 ****
--- 3666,3796 ----
return need_assert;
}
+ /* Compare two case labels sorting first by the destination label uid
+ and then by the case value. */
+
+ static int
+ compare_case_labels (const void *p1, const void *p2)
+ {
+ tree case1 = *(tree *)p1;
+ tree case2 = *(tree *)p2;
+ unsigned int uid1 = DECL_UID (CASE_LABEL (case1));
+ unsigned int uid2 = DECL_UID (CASE_LABEL (case2));
+
+ if (uid1 < uid2)
+ return -1;
+ else if (uid1 == uid2)
+ {
+ /* Make sure the default label is first in a group. */
+ if (!CASE_LOW (case1))
+ return -1;
+ else if (!CASE_LOW (case2))
+ return 1;
+ else
+ return tree_int_cst_compare (CASE_LOW (case1), CASE_LOW (case2));
+ }
+ else
+ return 1;
+ }
+
+ /* Determine whether the outgoing edges of BB should receive an
+ ASSERT_EXPR for each of the operands of BB's LAST statement.
+ The last statement of BB must be a SWITCH_EXPR.
+
+ If any of the sub-graphs rooted at BB have an interesting use of
+ the predicate operands, an assert location node is added to the
+ list of assertions for the corresponding operands. */
+
+ static bool
+ find_switch_asserts (basic_block bb, tree last)
+ {
+ bool need_assert;
+ block_stmt_iterator bsi;
+ tree op, cond;
+ edge e;
+ tree vec = SWITCH_LABELS (last), vec2;
+ size_t n = TREE_VEC_LENGTH (vec);
+ unsigned int idx;
+
+ need_assert = false;
+ bsi = bsi_for_stmt (last);
+ op = TREE_OPERAND (last, 0);
+ if (TREE_CODE (op) != SSA_NAME)
+ return false;
+
+ /* Build a vector of case labels sorted by destination label. */
+ vec2 = make_tree_vec (n);
+ for (idx = 0; idx < n; ++idx)
+ TREE_VEC_ELT (vec2, idx) = TREE_VEC_ELT (vec, idx);
+ qsort (&TREE_VEC_ELT (vec2, 0), n, sizeof (tree), compare_case_labels);
+
+ for (idx = 0; idx < n; ++idx)
+ {
+ tree min, max;
+ tree cl = TREE_VEC_ELT (vec2, idx);
+
+ min = CASE_LOW (cl);
+ max = CASE_HIGH (cl);
+
+ /* If there are multiple case labels with the same destination
+ we need to combine them to a single value range for the edge. */
+ if (idx + 1 < n
+ && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx + 1)))
+ {
+ /* Skip labels until the last of the group. */
+ do {
+ ++idx;
+ } while (idx < n
+ && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx)));
+ --idx;
+
+ /* Pick up the maximum of the case label range. */
+ if (CASE_HIGH (TREE_VEC_ELT (vec2, idx)))
+ max = CASE_HIGH (TREE_VEC_ELT (vec2, idx));
+ else
+ max = CASE_LOW (TREE_VEC_ELT (vec2, idx));
+ }
+
+ /* Nothing to do if the range includes the default label until we
+ can register anti-ranges. */
+ if (min == NULL_TREE)
+ continue;
+
+ /* Find the edge to register the assert expr on. */
+ e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
+
+ /* Remove the SWITCH_EXPR operand from the FOUND_IN_SUBGRAPH bitmap.
+ Otherwise, when we finish traversing each of the sub-graphs, we
+ won't know whether the variables were found in the sub-graphs or
+ if they had been found in a block upstream from BB. */
+ RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
+
+ /* Traverse the strictly dominated sub-graph rooted at E->DEST
+ to determine if any of the operands in the conditional
+ predicate are used. */
+ if (e->dest != bb)
+ need_assert |= find_assert_locations (e->dest);
+
+ /* Register the necessary assertions for the operand in the
+ SWITCH_EXPR. */
+ cond = build2 (max ? GE_EXPR : EQ_EXPR, boolean_type_node,
+ op, fold_convert (TREE_TYPE (op), min));
+ need_assert |= register_edge_assert_for (op, e, bsi, cond);
+ if (max)
+ {
+ cond = build2 (LE_EXPR, boolean_type_node,
+ op, fold_convert (TREE_TYPE (op), max));
+ need_assert |= register_edge_assert_for (op, e, bsi, cond);
+ }
+ }
+
+ /* Finally, indicate that we have found the operand in the
+ SWITCH_EXPR. */
+ SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
+
+ return need_assert;
+ }
+
/* Traverse all the statements in block BB looking for statements that
may generate useful assertions for the SSA names in their operand.
*************** find_conditional_asserts (basic_block bb
*** 3728,3736 ****
If this function returns true, then it means that there are names
for which we need to generate ASSERT_EXPRs. Those assertions are
! inserted by process_assert_insertions.
!
! TODO. Handle SWITCH_EXPR. */
static bool
find_assert_locations (basic_block bb)
--- 3853,3859 ----
If this function returns true, then it means that there are names
for which we need to generate ASSERT_EXPRs. Those assertions are
! inserted by process_assert_insertions. */
static bool
find_assert_locations (basic_block bb)
*************** find_assert_locations (basic_block bb)
*** 3853,3858 ****
--- 3976,3986 ----
&& !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
need_assert |= find_conditional_asserts (bb, last);
+ if (last
+ && TREE_CODE (last) == SWITCH_EXPR
+ && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
+ need_assert |= find_switch_asserts (bb, last);
+
/* Recurse into the dominator children of BB. */
for (son = first_dom_son (CDI_DOMINATORS, bb);
son;
*************** vrp_visit_cond_stmt (tree stmt, edge *ta
*** 4759,4766 ****
*taken_edge_p = NULL;
! /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
! add ASSERT_EXPRs for them. */
if (TREE_CODE (stmt) == SWITCH_EXPR)
return SSA_PROP_VARYING;
--- 4887,4893 ----
*taken_edge_p = NULL;
! /* FIXME. Handle SWITCH_EXPRs. */
if (TREE_CODE (stmt) == SWITCH_EXPR)
return SSA_PROP_VARYING;