[PATCH] Fix PR tree-optimization/51513
Richard Biener
richard.guenther@gmail.com
Fri Apr 29 09:56:00 GMT 2016
On Fri, Apr 29, 2016 at 1:35 AM, Peter Bergner <bergner@vnet.ibm.com> wrote:
> This patch fixes PR tree-optimization/51513, namely the generation of
> wild branches due to switch case statements that only contain calls to
> __builtin_unreachable(). For example, compiling using -O2 -fjump-tables
> --param case-values-threshold=1 (to easily expose the bug), we see:
>
> switch (which)
> {
> case 0:
> return v0;
> case 1:
> return v1;
> case 2:
> return v2;
> default:
> __builtin_unreachable( );
> }
Your testcase passes '2' where it passes just fine. If I pass 3 as which
I indeed get an abort () but you can't reasonably expect it to return 13 then.
A __builtin_unreachable () marks the path leading to it as invoking undefined
behavior whenever you would enter it at runtime - this is exactly what happens,
you get a branch "somewhere".
So I fail to see the actual bug you are fixing and I wonder why you do stuff
at the GIMPLE level when we only remove the unreachable blocks at RTL
level CFG cleanup. Iff then the "fix" should be there.
But as said, the behavior is expected - in fact the jump-table code should
be optimized for a unreachable default case to simply omit the range
check! That would be a better fix (also avoiding the wild branch).
Richard.
> we currently generate for powerpc64le-linux:
>
> cmpldi 7,3,2
> bgt 7,.L2 <- Invalid branch
> ...
> .L3:
> mr 3,4
> blr
> .p2align 4,,15
> .L2: <- Invalid branch target
> .long 0
> .byte 0,0,0,0,0,0,0,0
> .size bug,.-bug
>
> ...and for x86_64-linux:
>
> bug:
> .LFB0:
> .cfi_startproc
> cmpq $2, %rdi
> ja .L2 <- Invalid branch
> jmp *.L4(,%rdi,8)
> ...
> .L3:
> movq %rsi, %rax
> ret
> .p2align 4,,10
> .p2align 3
> .L2: <- Invalid branch target
> .cfi_endproc
> .LFE0:
> .size bug, .-bug
>
> The bug is that we end up deleting the unreachable block(s) from the CFG,
> but we never remove the label(s) for the block(s) in the switch jump table.
> We fix this by removing the case labels and their associated edges for
> unreachable blocks. Normal CFG cleanup removes the unreachable blocks.
>
> This has passed bootstrap and regtesting on powerpc64le-linux and x86_64-linux
> with no regressions. Ok for trunk?
>
> Peter
>
>
> gcc/
> PR tree-optimization/51513
> * tree-cfg.c (gimple_unreachable_bb_p): New function.
> (assert_unreachable_fallthru_edge_p): Use it.
> (compress_case_label_vector): New function.
> (group_case_labels_stmt): Use it.
> (cleanup_dead_labels): Call gimple_unreachable_bb_p() and
> compress_case_label_vector(). Remove labels and edges leading
> to unreachable blocks.
>
> gcc/testsuite/
> PR tree-optimization/51513
> * gcc.c-torture/execute/pr51513.c: New test.
>
>
> Index: gcc/tree-cfg.c
> ===================================================================
> --- gcc/tree-cfg.c (revision 235531)
> +++ gcc/tree-cfg.c (working copy)
> @@ -408,6 +408,33 @@ computed_goto_p (gimple *t)
> && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL);
> }
>
> +/* Returns true if the basic block BB has no successors and only contains
> + a call to __builtin_unreachable (). */
> +
> +static bool
> +gimple_unreachable_bb_p (basic_block bb)
> +{
> + gimple_stmt_iterator gsi;
> + gimple *stmt;
> +
> + if (EDGE_COUNT (bb->succs) != 0)
> + return false;
> +
> + gsi = gsi_after_labels (bb);
> + if (gsi_end_p (gsi))
> + return false;
> +
> + stmt = gsi_stmt (gsi);
> + while (is_gimple_debug (stmt) || gimple_clobber_p (stmt))
> + {
> + gsi_next (&gsi);
> + if (gsi_end_p (gsi))
> + return false;
> + stmt = gsi_stmt (gsi);
> + }
> + return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE);
> +}
> +
> /* Returns true for edge E where e->src ends with a GIMPLE_COND and
> the other edge points to a bb with just __builtin_unreachable ().
> I.e. return true for C->M edge in:
> @@ -431,23 +458,7 @@ assert_unreachable_fallthru_edge_p (edge
> basic_block other_bb = EDGE_SUCC (pred_bb, 0)->dest;
> if (other_bb == e->dest)
> other_bb = EDGE_SUCC (pred_bb, 1)->dest;
> - if (EDGE_COUNT (other_bb->succs) == 0)
> - {
> - gimple_stmt_iterator gsi = gsi_after_labels (other_bb);
> - gimple *stmt;
> -
> - if (gsi_end_p (gsi))
> - return false;
> - stmt = gsi_stmt (gsi);
> - while (is_gimple_debug (stmt) || gimple_clobber_p (stmt))
> - {
> - gsi_next (&gsi);
> - if (gsi_end_p (gsi))
> - return false;
> - stmt = gsi_stmt (gsi);
> - }
> - return gimple_call_builtin_p (stmt, BUILT_IN_UNREACHABLE);
> - }
> + return gimple_unreachable_bb_p (other_bb);
> }
> return false;
> }
> @@ -1401,6 +1412,26 @@ cleanup_dead_labels_eh (void)
> }
> }
>
> +/* Compress the case labels in the label vector to remove NULL labels,
> + and adjust the length of the vector. */
> +
> +void
> +compress_case_label_vector (gswitch *stmt, size_t new_size, size_t old_size)
> +{
> + size_t i, j;
> +
> + gcc_assert (new_size <= old_size);
> +
> + for (i = 0, j = 0; i < new_size; i++)
> + {
> + while (!gimple_switch_label (stmt, j))
> + j++;
> + gimple_switch_set_label (stmt, i,
> + gimple_switch_label (stmt, j++));
> + }
> +
> + gimple_switch_set_num_labels (stmt, new_size);
> +}
>
> /* Cleanup redundant labels. This is a three-step process:
> 1) Find the leading label for each block.
> @@ -1485,17 +1516,81 @@ cleanup_dead_labels (void)
> case GIMPLE_SWITCH:
> {
> gswitch *switch_stmt = as_a <gswitch *> (stmt);
> - size_t i, n = gimple_switch_num_labels (switch_stmt);
> -
> - /* Replace all destination labels. */
> - for (i = 0; i < n; ++i)
> + size_t i, old_size = gimple_switch_num_labels (switch_stmt);
> + size_t new_size = old_size;
> + basic_block prev_bb = NULL;
> + bool prev_bb_empty = false;
> +
> + /* Replace all destination labels that do not lead to unreachable
> + blocks. Remove any unreachable blocks. */
> + for (i = 0; i < old_size; i++)
> {
> tree case_label = gimple_switch_label (switch_stmt, i);
> label = CASE_LABEL (case_label);
> - new_label = main_block_label (label);
> - if (new_label != label)
> - CASE_LABEL (case_label) = new_label;
> + basic_block case_bb = label_to_block (label);
> +
> + /* The call to gimple_unreachable_bb_p() can be expensive, so
> + we cache the previous blocks's results to catch the case
> + where multiple labels all branch to the same block.
> + See gcc.c-torture/compile/limits-caselabels.c for an
> + extreme case where this caching helps a lot. */
> + if ((case_bb == prev_bb && prev_bb_empty)
> + || (case_bb != prev_bb && gimple_unreachable_bb_p (case_bb)))
> + {
> + /* Clear the unreachable case label from the switch's jump
> + table and remove its edge in the CFG. */
> + gimple_switch_set_label (switch_stmt, i, NULL_TREE);
> + if (case_bb != prev_bb)
> + {
> + edge e = find_edge (bb, case_bb);
> + if (e != NULL)
> + remove_edge_and_dominated_blocks (e);
> + }
> + prev_bb = case_bb;
> + prev_bb_empty = true;
> + new_size--;
> + }
> + else
> + {
> + new_label = main_block_label (label);
> + if (new_label != label)
> + CASE_LABEL (case_label) = new_label;
> + prev_bb = case_bb;
> + prev_bb_empty = false;
> + }
> + }
> +
> + /* If every case statement is unreachable, then remove the switch
> + statement itself. The jump table will be cleaned up below. */
> + if (new_size == 0)
> + {
> + gimple_stmt_iterator gsi = gsi_last_bb (bb);
> + gsi_remove (&gsi, true);
> + }
> + else if (gimple_switch_label (switch_stmt, 0) == NULL_TREE)
> + {
> + /* If we deleted the default case block because it was
> + unreachable, then add a new dummy default case label
> + pointing at one of the other cases. */
> + tree default_label = NULL_TREE;
> + for (i = 1; i < old_size; i++)
> + {
> + default_label = gimple_switch_label (switch_stmt, old_size - i);
> + if (default_label != NULL_TREE)
> + {
> + default_label = CASE_LABEL (default_label);
> + break;
> + }
> + }
> + gcc_assert (default_label != NULL_TREE);
> + tree default_case = build_case_label (NULL_TREE, NULL_TREE,
> + default_label);
> + gimple_switch_set_default_label (switch_stmt, default_case);
> + new_size++;
> }
> +
> + if (new_size < old_size)
> + compress_case_label_vector (switch_stmt, new_size, old_size);
> break;
> }
>
> @@ -1610,7 +1705,7 @@ void
> group_case_labels_stmt (gswitch *stmt)
> {
> int old_size = gimple_switch_num_labels (stmt);
> - int i, j, new_size = old_size;
> + int i, new_size = old_size;
> basic_block default_bb = NULL;
>
> default_bb = label_to_block (CASE_LABEL (gimple_switch_default_label (stmt)));
> @@ -1668,18 +1763,7 @@ group_case_labels_stmt (gswitch *stmt)
> }
> }
>
> - /* Compress the case labels in the label vector, and adjust the
> - length of the vector. */
> - for (i = 0, j = 0; i < new_size; i++)
> - {
> - while (! gimple_switch_label (stmt, j))
> - j++;
> - gimple_switch_set_label (stmt, i,
> - gimple_switch_label (stmt, j++));
> - }
> -
> - gcc_assert (new_size <= old_size);
> - gimple_switch_set_num_labels (stmt, new_size);
> + compress_case_label_vector (stmt, new_size, old_size);
> }
>
> /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH),
> Index: gcc/testsuite/gcc.c-torture/execute/pr51513.c
> ===================================================================
> --- gcc/testsuite/gcc.c-torture/execute/pr51513.c (revision 0)
> +++ gcc/testsuite/gcc.c-torture/execute/pr51513.c (working copy)
> @@ -0,0 +1,36 @@
> +/* PR tree-optimization/51513 */
> +
> +/* { dg-do run } */
> +/* { dg-options "-fjump-tables --param case-values-threshold=1" } */
> +
> +long
> +__attribute__ ((__noinline__))
> +bug (long which, long v0, long v1, long v2)
> +{
> + switch (which)
> + {
> + case 0:
> + return v0;
> + case 1:
> + return v1;
> + case 2:
> + return v2;
> + default:
> + __builtin_unreachable( );
> + }
> + __builtin_abort ();
> +}
> +
> +int
> +main (void)
> +{
> + /* Purposely call bug() with an argument that will target the
> + switch's "unreachable" default case statement, to test whether
> + we generated a wild branch or not. */
> + long ret = bug (2, 13, 13, 13);
> +
> + if (ret != 13)
> + __builtin_abort ();
> +
> + return 0;
> +}
>
More information about the Gcc-patches
mailing list