This patch is the second attempt to fix PR51513, namely the generation of
wild branches due to switch case statements that only contain calls to
__builtin_unreachable(). With the first attempt:
https://gcc.gnu.org/ml/gcc-patches/2016-04/msg01915.html
richi said he preferred if we just eliminated the range check for
default case statements that contained __builtin_unreachable().
This patch implements that idea. It also removes normal case
statement blocks that are marked as unreachable, but in those cases,
we just use a dummy label in the jump table for them.
This passed bootstrap and regtesting with no regressions on powerpc64-linux
and x86_64-linux. Ok for trunk now or trunk during stage1?
Peter
gcc/
* tree-cfg.c (gimple_unreachable_bb_p): New function.
(assert_unreachable_fallthru_edge_p): Use it.
* 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 and unreachable cases.
Remove edges to unreachable blocks.
(expand_case): Test for unreachable default case statement and
remove its edge. Set default_label accordingly.
(emit_case_nodes): Only emit branch to default_label if it
exists.
gcc/testsuite/
* gcc.target/powerpc/pr51513.c: New test.
Index: gcc/stmt.c
===================================================================
--- gcc/stmt.c (revision 246661)
+++ 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"
@@ -989,6 +991,14 @@ emit_case_dispatch_table (tree index_exp
labelvec = XALLOCAVEC (rtx, ncases);
memset (labelvec, 0, ncases * sizeof (rtx));
+ /* The dispatch table may contain gaps and labels of unreachable case
+ statements. Gaps can exist at the beginning of the table if we tried
+ to avoid the minval subtraction. We fill the dispatch table slots
+ associated with the gaps and unreachable case blocks with the default
+ case label. However, in the event the default case itself is unreachable,
+ we then use any label from one of the reachable case statements. */
+ rtx gap_label = (default_label) ? default_label : fallback_label;
+
for (n = case_list; n; n = n->right)
{
/* Compute the low and high bounds relative to the minimum
@@ -1000,42 +1010,51 @@ emit_case_dispatch_table (tree index_exp
HOST_WIDE_INT i_high
= tree_to_uhwi (fold_build2 (MINUS_EXPR, index_type,
n->high, minval));
- HOST_WIDE_INT i;
+ basic_block case_bb = label_to_block (n->code_label);
+ rtx case_label;
+ if (gimple_unreachable_bb_p (case_bb))
+ {
+ /* We have an unreachable case statement, so replace its label
+ with a dummy label and remove the edge to the unreachable block.
+ The block itself will be automatically removed later. */
+ case_label = gap_label;
+ remove_edge (find_edge (stmt_bb, case_bb));
+ }
+ else
+ case_label = label_rtx (n->code_label);
+
+ HOST_WIDE_INT i;
for (i = i_low; i <= i_high; i ++)
- labelvec[i]
- = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
+ labelvec[i] = gen_rtx_LABEL_REF (Pmode, case_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;
+ /* Now fill in the dispatch table gaps. */
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)
- {
- /* There is at least one entry in the jump table that jumps
- to default label. The default label can either be reached
- through the indirect jump or the direct conditional jump
- before that. Split the probability of reaching the
- default label among these two jumps. */
- new_default_prob = conditional_probability (default_prob/2,
- base);
- default_prob /= 2;
- base -= default_prob;
- }
- else
+ if (default_label)
{
- base -= default_prob;
- default_prob = 0;
+ if (has_gaps)
+ {
+ /* There is at least one entry in the jump table that jumps
+ to default label. The default label can either be reached
+ through the indirect jump or the direct conditional jump
+ before that. Split the probability of reaching the
+ default label among these two jumps. */
+ new_default_prob = conditional_probability (default_prob/2, base);
+ default_prob /= 2;
+ base -= default_prob;
+ }
+ else
+ {
+ base -= default_prob;
+ default_prob = 0;
+ }
}
if (default_edge)
@@ -1115,7 +1134,8 @@ 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;
+ int default_prob;
unsigned int count, uniq;
int i;
int ncases = gimple_switch_num_labels (stmt);
@@ -1139,15 +1159,24 @@ expand_case (gswitch *stmt)
/* cleanup_tree_cfg removes all SWITCH_EXPR with their index
expressions being INTEGER_CST. */
gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
-
do_pending_stack_adjust ();
/* Find the default case target label. */
- default_label = jump_target_rtx
- (CASE_LABEL (gimple_switch_default_label (stmt)));
- edge default_edge = EDGE_SUCC (bb, 0);
- int default_prob = default_edge->probability;
+ tree default_tree = CASE_LABEL (gimple_switch_default_label (stmt));
+ basic_block default_bb = label_to_block (default_tree);
+ if (gimple_unreachable_bb_p (default_bb))
+ {
+ default_label = NULL;
+ default_prob = 0;
+ remove_edge (find_edge (bb, default_bb));
+ }
+ else
+ {
+ default_label = jump_target_rtx (default_tree);
+ edge default_edge = EDGE_SUCC (bb, 0);
+ default_prob = default_edge->probability;
+ }
/* Get upper and lower bounds of case values. */
elt = gimple_switch_label (stmt, 1);
@@ -1725,7 +1754,7 @@ emit_case_nodes (rtx index, case_node_pt
if (node->right->right || node->right->left
|| !tree_int_cst_equal (node->right->low, node->right->high))
{
- if (!node_has_low_bound (node, index_type))
+ if (default_label && !node_has_low_bound (node, index_type))
{
probability = conditional_probability (
default_prob/2,
@@ -1767,7 +1796,7 @@ emit_case_nodes (rtx index, case_node_pt
if (node->left->left || node->left->right
|| !tree_int_cst_equal (node->left->low, node->left->high))
{
- if (!node_has_high_bound (node, index_type))
+ if (default_label && !node_has_high_bound (node, index_type))
{
probability = conditional_probability (
default_prob/2,
@@ -1891,7 +1920,7 @@ emit_case_nodes (rtx index, case_node_pt
{
/* Deal with values to the left of this node,
if they are possible. */
- if (!node_has_low_bound (node, index_type))
+ if (default_label && !node_has_low_bound (node, index_type))
{
probability = conditional_probability (
default_prob/2,
@@ -1928,7 +1957,7 @@ emit_case_nodes (rtx index, case_node_pt
{
/* Deal with values to the right of this node,
if they are possible. */
- if (!node_has_high_bound (node, index_type))
+ if (default_label && !node_has_high_bound (node, index_type))
{
probability = conditional_probability (
default_prob/2,
@@ -1969,7 +1998,7 @@ emit_case_nodes (rtx index, case_node_pt
int high_bound = node_has_high_bound (node, index_type);
int low_bound = node_has_low_bound (node, index_type);
- if (!high_bound && low_bound)
+ if (default_label && !high_bound && low_bound)
{
probability = conditional_probability (
default_prob,
@@ -1984,7 +2013,7 @@ emit_case_nodes (rtx index, case_node_pt
probability);
}
- else if (!low_bound && high_bound)
+ else if (default_label && !low_bound && high_bound)
{
probability = conditional_probability (
default_prob,
@@ -1998,7 +2027,7 @@ emit_case_nodes (rtx index, case_node_pt
default_label,
probability);
}
- else if (!low_bound && !high_bound)
+ else if (default_label && !low_bound && !high_bound)
{
/* Widen LOW and HIGH to the same width as INDEX. */
tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
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/tree-cfg.c
===================================================================
--- gcc/tree-cfg.c (revision 246661)
+++ 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,28 +506,11 @@ 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;
}
-
/* Initialize GF_CALL_CTRL_ALTERING flag, which indicates the call
could alter control flow except via eh. We initialize the flag at
CFG build time and only ever clear it later. */
Index: gcc/tree-cfg.h
===================================================================
--- gcc/tree-cfg.h (revision 246661)
+++ 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);
