From patchwork Wed May 10 02:54:20 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peter Bergner X-Patchwork-Id: 760396 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3wN16v3tPHz9ryb for ; Wed, 10 May 2017 12:54:46 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="y73oEguq"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to:cc :from:subject:date:mime-version:content-type :content-transfer-encoding:message-id; q=dns; s=default; b=nAQXs a2sB8fE29LJAsdy/3Jj4PiZgx2b3HrLMaCvWMjOOYS8gk7+cS8E/JYHFTlc3gCdF bozXBC2Iz4h9H9heRZV0WGtQ1g0qIUAa7sRuOIhgSX1U6A5HCdP6ddIl4rgUZfDW NTvNbrxhnYNB0pQRQT+ZgNfYDAxyV8PgtnEClo= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to:cc :from:subject:date:mime-version:content-type :content-transfer-encoding:message-id; s=default; bh=MI8x7++XBr6 wYl6FG8AA495fRZM=; b=y73oEguqktZbEoOmyPLtRQsVZieNG/J0G42LjsKjQUj NpI2Vni+hdxViTAEA3jQpJ0KyU0axQGkaYJpuVIq57ArDqMKsu3p6b/kE7NiLHJh N2fg5mE2omvaq9+Q6/EKSlQkmCc7cafs13fxFZNZessGOvFbP3h4cYhaYLJEfSac = Received: (qmail 81045 invoked by alias); 10 May 2017 02:54:27 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 81026 invoked by uid 89); 10 May 2017 02:54:26 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.8 required=5.0 tests=BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mx0a-001b2d01.pphosted.com Received: from mx0b-001b2d01.pphosted.com (HELO mx0a-001b2d01.pphosted.com) (148.163.158.5) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 10 May 2017 02:54:24 +0000 Received: from pps.filterd (m0098419.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.20/8.16.0.20) with SMTP id v4A2s0OR085546 for ; Tue, 9 May 2017 22:54:25 -0400 Received: from e15.ny.us.ibm.com (e15.ny.us.ibm.com [129.33.205.205]) by mx0b-001b2d01.pphosted.com with ESMTP id 2abhaxbhmm-1 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=NOT) for ; Tue, 09 May 2017 22:54:24 -0400 Received: from localhost by e15.ny.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Tue, 9 May 2017 22:54:24 -0400 Received: from b01cxnp22033.gho.pok.ibm.com (9.57.198.23) by e15.ny.us.ibm.com (146.89.104.202) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; Tue, 9 May 2017 22:54:21 -0400 Received: from b01ledav005.gho.pok.ibm.com (b01ledav005.gho.pok.ibm.com [9.57.199.110]) by b01cxnp22033.gho.pok.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id v4A2sLrm42008714; Wed, 10 May 2017 02:54:21 GMT Received: from b01ledav005.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id BA69CAE043; Tue, 9 May 2017 22:54:09 -0400 (EDT) Received: from otta.local (unknown [9.80.215.2]) by b01ledav005.gho.pok.ibm.com (Postfix) with ESMTP id 46A4EAE034; Tue, 9 May 2017 22:54:09 -0400 (EDT) To: Richard Biener Cc: GCC Patches , Jakub Jelinek , Bill Schmidt From: Peter Bergner Subject: [PATCH, v4] Fix PR51513, switch statement with default case containing __builtin_unreachable leads to wild branch Date: Tue, 9 May 2017 21:54:20 -0500 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:52.0) Gecko/20100101 Thunderbird/52.1.0 MIME-Version: 1.0 X-TM-AS-GCONF: 00 x-cbid: 17051002-0036-0000-0000-00000200DA10 X-IBM-SpamModules-Scores: X-IBM-SpamModules-Versions: BY=3.00007041; HX=3.00000240; KW=3.00000007; PH=3.00000004; SC=3.00000209; SDB=6.00858471; UDB=6.00425364; IPR=6.00637935; BA=6.00005339; NDR=6.00000001; ZLA=6.00000005; ZF=6.00000009; ZB=6.00000000; ZP=6.00000000; ZH=6.00000000; ZU=6.00000002; MB=3.00015386; XFM=3.00000015; UTC=2017-05-10 02:54:23 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 17051002-0037-0000-0000-000040472568 Message-Id: <851d1590-6ef5-45f2-5bc0-77de42671254@vnet.ibm.com> X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2017-05-10_01:, , signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 suspectscore=0 malwarescore=0 phishscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1703280000 definitions=main-1705100021 X-IsSubscribed: yes Here is the updated patch to use gimple_seq_unreachable_p() which scans the sequence backwards so it bails out earlier in the common case (ie, no call to __builtin_unreachable). As discussed in the previous thread, we remove case statement labels from the jump table that lead to unreachable blocks, which leads to fewer compare/branches in the decision tree case and possibly a smaller jump table in the jump table case. Unreachable default case statements are only handled here when generating a jump table, since the current code for decision trees seems to prefer the status quo. We can revisit this later if someone finds a test case that would benefit from handling it for decision trees too. This passes bootstrap and regtesting on powerpc64le-linux and x86_64-linux with no regressions. Ok for trunk now? Peter gcc/ * tree-cfg.c (gimple_seq_unreachable_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) : New local variable. Use it to fill dispatch table gaps. Test for default_label before updating probabilities. (expand_case) : Remove unneeded initialization. Test for unreachable default case statement and remove its edge. Set default_label accordingly. * 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,31 @@ computed_goto_p (gimple *t) && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL); } +/* Returns true if the sequence of statements STMTS only contains + a call to __builtin_unreachable (). */ + +bool +gimple_seq_unreachable_p (gimple_seq stmts) +{ + if (stmts == NULL) + return false; + + gimple_stmt_iterator gsi = gsi_last (stmts); + + if (!gimple_call_builtin_p (gsi_stmt (gsi), BUILT_IN_UNREACHABLE)) + return false; + + for (gsi_prev (&gsi); !gsi_end_p (gsi); gsi_prev (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + if (gimple_code (stmt) != GIMPLE_LABEL + && !is_gimple_debug (stmt) + && !gimple_clobber_p (stmt)) + return false; + } + return true; +} + /* 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: @@ -476,22 +501,7 @@ assert_unreachable_fallthru_edge_p (edge 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_seq_unreachable_p (bb_seq (other_bb)); } return false; } @@ -1668,9 +1678,11 @@ 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 + || (EDGE_COUNT (base_bb->succs) == 0 + && gimple_seq_unreachable_p (bb_seq (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_seq_unreachable_p (gimple_seq); 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,21 @@ 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 (EDGE_COUNT (default_edge->dest->succs) == 0 + && gimple_seq_unreachable_p (bb_seq (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;