[PATCH, v3] Fix PR51513, switch statement with default case containing __builtin_unreachable leads to wild branch
Peter Bergner
bergner@vnet.ibm.com
Thu Apr 27 05:08:00 GMT 2017
On 4/20/17 8:26 AM, Peter Bergner wrote:
> On 4/20/17 2:37 AM, Richard Biener wrote:
>> Ok, so I think we should ensure that we remove the regular cases
>> with unreachable destination, like in
>>
>> switch (i)
>> {
>> case 0:
>> __builtin_unreachable ();
>> default:;
>> }
>>
>> and handle default with __builtin_unreachable () from switch
>> expansion by omitting the range check for the jump table
>> indexing (and choose a non-default case label for gaps).
>
> Ok, I'll modify optimize_unreachable() to remove the unreachable
> case statements, and leave the unreachable default case statement
> for switch expansion so we can eliminate the range check. Thanks.
Ok, I lied. :-) It ended up being a fair amount of code to remove
the unreachable case statements within optimize_unreachable().
Instead, I hooked into group_case_labels_stmt() which is much
simpler! That code eliminates all case statements that have the
same destination as the default case statement. With the patch,
we also eliminate case statements that are unreachable, thus
treating them like default cases. This has the added benefit of
being able to reduce the size of the dispatch table, if those cases
were at the end of the dispatch table entries.
One difference from the last patch is that I am no longer setting
default_label to NULL when we emit a decision tree. I noticed that
the decision tree code seemed to generate slightly better code for
some of my unit tests if I left it alone. This simplified the
patch somewhat by removing the changes to emit_case_nodes().
This passed bootstrap and regtesting on powerpc64le-linux and
x86_64-linux. Is this ok for trunk now? If so, I can hold off
committing it until GCC 7 has been released if that helps.
Peter
gcc/
* tree-cfg.c (gimple_unreachable_bb_p): New function.
(assert_unreachable_fallthru_edge_p): Use it.
(group_case_labels_stmt): Likewise.
* tree-cfg.h: Prototype it.
* stmt.c: Include cfghooks.h and tree-cfg.h.
(emit_case_dispatch_table) <gap_label>: New local variable.
Use it to fill dispatch table gaps.
Test for default_label before updating probabilities.
(expand_case) <default_label>: Remove unneeded initialization.
Test for unreachable default case statement and remove its edge.
Set default_label accordingly.
* gcc/tree-ssa-ccp.c (optimize_unreachable): Update comment.
gcc/testsuite/
* gcc.target/powerpc/pr51513.c: New test.
* gcc.dg/predict-13.c: Replace __builtin_unreachable() with
__builtin_abort().
* gcc.dg/predict-14.c: Likewise.
Index: gcc/tree-cfg.c
===================================================================
--- gcc/tree-cfg.c (revision 247291)
+++ gcc/tree-cfg.c (working copy)
@@ -452,6 +452,37 @@ 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 (). */
+
+bool
+gimple_unreachable_bb_p (basic_block bb)
+{
+ gimple_stmt_iterator gsi;
+ gimple_seq stmts = bb_seq (bb);
+ gimple *stmt;
+
+ if (EDGE_COUNT (bb->succs) != 0)
+ return false;
+
+ gsi = gsi_start (stmts);
+ while (!gsi_end_p (gsi) && gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
+ gsi_next (&gsi);
+
+ 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:
@@ -475,23 +506,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;
}
@@ -1668,9 +1683,10 @@ group_case_labels_stmt (gswitch *stmt)
gcc_assert (base_case);
base_bb = label_to_block (CASE_LABEL (base_case));
- /* Discard cases that have the same destination as the
- default case. */
- if (base_bb == default_bb)
+ /* Discard cases that have the same destination as the default case
+ or if their destination block is unreachable. */
+ if (base_bb == default_bb
+ || gimple_unreachable_bb_p (base_bb))
{
gimple_switch_set_label (stmt, i, NULL_TREE);
i++;
Index: gcc/tree-cfg.h
===================================================================
--- gcc/tree-cfg.h (revision 247291)
+++ gcc/tree-cfg.h (working copy)
@@ -56,6 +56,7 @@ extern bool is_ctrl_stmt (gimple *);
extern bool is_ctrl_altering_stmt (gimple *);
extern bool simple_goto_p (gimple *);
extern bool stmt_ends_bb_p (gimple *);
+extern bool gimple_unreachable_bb_p (basic_block);
extern bool assert_unreachable_fallthru_edge_p (edge);
extern void delete_tree_cfg_annotations (function *);
extern gphi *get_virtual_phi (basic_block);
Index: gcc/stmt.c
===================================================================
--- gcc/stmt.c (revision 247291)
+++ gcc/stmt.c (working copy)
@@ -30,6 +30,7 @@ along with GCC; see the file COPYING3.
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
+#include "cfghooks.h"
#include "predict.h"
#include "alloc-pool.h"
#include "memmodel.h"
@@ -49,6 +50,7 @@ along with GCC; see the file COPYING3.
#include "expr.h"
#include "langhooks.h"
#include "cfganal.h"
+#include "tree-cfg.h"
#include "params.h"
#include "dumpfile.h"
#include "builtins.h"
@@ -1007,20 +1009,21 @@ emit_case_dispatch_table (tree index_exp
= gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
}
- /* Fill in the gaps with the default. We may have gaps at
- the beginning if we tried to avoid the minval subtraction,
- so substitute some label even if the default label was
- deemed unreachable. */
- if (!default_label)
- default_label = fallback_label;
+ /* The dispatch table may contain gaps, including at the beginning of
+ the table if we tried to avoid the minval subtraction. We fill the
+ dispatch table slots associated with the gaps with the default case label.
+ However, in the event the default case is unreachable, we then use
+ any label from one of the case statements. */
+ rtx gap_label = (default_label) ? default_label : fallback_label;
+
for (i = 0; i < ncases; i++)
if (labelvec[i] == 0)
{
- has_gaps = true;
- labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
+ has_gaps = true;
+ labelvec[i] = gen_rtx_LABEL_REF (Pmode, gap_label);
}
- if (has_gaps)
+ if (has_gaps && default_label)
{
/* There is at least one entry in the jump table that jumps
to default label. The default label can either be reached
@@ -1115,7 +1118,7 @@ void
expand_case (gswitch *stmt)
{
tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
- rtx_code_label *default_label = NULL;
+ rtx_code_label *default_label;
unsigned int count, uniq;
int i;
int ncases = gimple_switch_num_labels (stmt);
@@ -1232,9 +1235,20 @@ expand_case (gswitch *stmt)
case_list, default_label,
default_prob);
else
- emit_case_dispatch_table (index_expr, index_type,
- case_list, default_label,
- minval, maxval, range, bb);
+ {
+ /* If the default case is unreachable, then set default_label to NULL
+ so that we omit the range check when generating the dispatch table.
+ We also remove the edge to the unreachable default case. The block
+ itself will be automatically removed later. */
+ if (gimple_unreachable_bb_p (default_edge->dest))
+ {
+ default_label = NULL;
+ remove_edge (default_edge);
+ }
+ emit_case_dispatch_table (index_expr, index_type,
+ case_list, default_label,
+ minval, maxval, range, bb);
+ }
reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case);
Index: gcc/tree-ssa-ccp.c
===================================================================
--- gcc/tree-ssa-ccp.c (revision 247291)
+++ gcc/tree-ssa-ccp.c (working copy)
@@ -2715,7 +2715,8 @@ optimize_unreachable (gimple_stmt_iterat
}
else
{
- /* Todo: handle other cases, f.i. switch statement. */
+ /* Todo: handle other cases. Note that unreachable switch case
+ statements have already been removed. */
continue;
}
Index: gcc/testsuite/gcc.target/powerpc/pr51513.c
===================================================================
--- gcc/testsuite/gcc.target/powerpc/pr51513.c (nonexistent)
+++ gcc/testsuite/gcc.target/powerpc/pr51513.c (working copy)
@@ -0,0 +1,25 @@
+/* { dg-do compile { target { powerpc*-*-linux* } } } */
+/* { dg-options "-O2 -fjump-tables --param case-values-threshold=1" } */
+/* Verify we created a jump table. */
+/* { dg-final { scan-assembler-times "mtctr " 1 } } */
+/* { dg-final { scan-assembler-times "bctr" 1 } } */
+/* Verify we eliminated the range check. */
+/* { dg-final { scan-assembler-not "cmpldi" } } */
+/* { dg-final { scan-assembler-not "cmplwi" } } */
+
+long
+bug (long cond, long v0, long v1, long v2)
+{
+ switch (cond)
+ {
+ case 0:
+ return v0;
+ case 1:
+ return v1;
+ case 2:
+ return v2;
+ default:
+ __builtin_unreachable ();
+ }
+ __builtin_abort ();
+}
Index: gcc/testsuite/gcc.dg/predict-13.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-13.c (revision 247291)
+++ gcc/testsuite/gcc.dg/predict-13.c (working copy)
@@ -10,9 +10,9 @@ int main(int argc, char **argv)
case 2:
return 2;
case 3:
- __builtin_unreachable();
+ __builtin_abort();
case 4:
- __builtin_unreachable();
+ __builtin_abort();
default:
return 5;
}
Index: gcc/testsuite/gcc.dg/predict-14.c
===================================================================
--- gcc/testsuite/gcc.dg/predict-14.c (revision 247291)
+++ gcc/testsuite/gcc.dg/predict-14.c (working copy)
@@ -6,11 +6,11 @@ int main(int argc, char **argv)
switch (argc)
{
case 1:
- __builtin_unreachable();
+ __builtin_abort();
case 4:
- __builtin_unreachable();
+ __builtin_abort();
default:
- __builtin_unreachable();
+ __builtin_abort();
}
return 10;
More information about the Gcc-patches
mailing list