From patchwork Fri Jun 22 09:23:38 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Martin_Li=C5=A1ka?= X-Patchwork-Id: 933169 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-480266-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="iwu9qKcz"; dkim-atps=neutral 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 41BtRV2xqGz9s3C for ; Fri, 22 Jun 2018 19:23:50 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :subject:to:cc:message-id:date:mime-version:content-type; q=dns; s=default; b=UIh1GczAMn4k3WqTzlU3Oq1EPGgVVSvmD5IQmBvAawAa/JCGPt Qk5GMttSNcaGaM5CMFjupt5jR9L7Epr0w9s5t7w3nV9yyzl/QY/FMnsY2qT1QOjl rahYx3IkyJbF8L4p52kAhKJpIIr9c8x1jfIXY2EpHTm/UkhC45lwxUywM= 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:from :subject:to:cc:message-id:date:mime-version:content-type; s= default; bh=2cmAS8KqE6/HgWJAKwqEhs2pFY4=; b=iwu9qKcz1Ut03nDGKvYh uBQFasCU3X6R9Esqq8ErRBeFWivUlM8PrUL7cM/bjT5rOctFaCYr5eEzIxBykYTE xud3JvkRqDthwXyHDsl564AMMpiZxFhcOf+upKo1wfoVj6ZMUCahgvCRPzRnqF0p swxaeCMWGdHBR303LGyWfdo= Received: (qmail 49828 invoked by alias); 22 Jun 2018 09:23:42 -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 49802 invoked by uid 89); 22 Jun 2018 09:23:42 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, SPF_PASS autolearn=ham version=3.3.2 spammy=100000, 1010, 1012 X-HELO: mx2.suse.de Received: from mx2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 22 Jun 2018 09:23:40 +0000 Received: from relay1.suse.de (charybdis-ext-too.suse.de [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 33E9BAC46; Fri, 22 Jun 2018 09:23:38 +0000 (UTC) From: =?utf-8?q?Martin_Li=C5=A1ka?= Subject: [PATCH] Fix clustering algorithm in switch expansion. To: gcc-patches@gcc.gnu.org Cc: Jeff Law Message-ID: Date: Fri, 22 Jun 2018 11:23:38 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 X-IsSubscribed: yes Hi. For correctness of clustering algorithm: https://www.semanticscholar.org/paper/Short-Communication%3A-Correction-to-'Producing-Good-Kannan-Proebsting/311091fb9fb9d38f7b76e768a603c02acc799fe0 one needs to allow single case clusters as possible. Note that we never end with a jump table, or a bit test handling just a single case. I also add tests for that catch that. Patch can bootstrap on ppc64le-redhat-linux and survives regression tests. Ready to be installed? Martin gcc/ChangeLog: 2018-06-21 Martin Liska * tree-switch-conversion.c (jump_table_cluster::find_jump_tables): Add new checking assert to catch invalid state. (jump_table_cluster::can_be_handled): Handle single case clusters. (jump_table_cluster::is_beneficial): Bail out for such case. (bit_test_cluster::find_bit_tests): Add new checking assert to catch invalid state. (bit_test_cluster::can_be_handled): Handle single case clusters. (bit_test_cluster::is_beneficial): Bail out for such case. (switch_decision_tree::analyze_switch_statement): Fix comment. gcc/testsuite/ChangeLog: 2018-06-21 Martin Liska * gcc.dg/tree-ssa/switch-1.c: New test. --- gcc/testsuite/gcc.dg/tree-ssa/switch-1.c | 110 +++++++++++++++++++++++ gcc/tree-switch-conversion.c | 27 +++++- 2 files changed, 135 insertions(+), 2 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-1.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c new file mode 100644 index 00000000000..149687ca2bb --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-1.c @@ -0,0 +1,110 @@ +/* { dg-do compile { target { { x86_64-*-* aarch64-*-* ia64-*-* powerpc64-*-* } && lp64 } } } */ +/* { dg-options "-O2 -fdump-tree-switchlower1 --param case-values-threshold=4" } */ + +int global; + +int foo (int x) +{ + switch (x) { + case 0: + case 10: + case 1000: + case 1010: + case 1025 ... 1030: + return 1; + default: + return 0; + } +} + +/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: 0 10 BT:1000-1030" "switchlower1" } } */ + +int foo2 (int x) +{ + switch (x) { + case -100: + case 100: + case 1000: + case 10000: + case 100000: + return 1; + default: + return 0; + } +} + +/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: -100 100 1000 10000 100000" "switchlower1" } } */ + +int foo3 (int x) +{ + switch (x) { + case 0: + case 10: + case 20: + global += 1; + return 3; + case 30: + case 33 ... 55: + case 57: + return 4; + case 60 ... 62: + return 1; + default: + return 0; + } +} + +/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: JT:0-62" "switchlower1" } } */ + +int foo4 (int x) +{ + switch (x) { + case -100: + case 10: + case 20: + global += 1; + return 3; + case 30: + case 33 ... 55: + case 57: + return 4; + case 60 ... 62: + return 1; + case 600 ... 700: + return 12; + default: + return 0; + } +} + +/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: -100 JT:10-62 600-700" "switchlower1" } } */ + +int foo5 (int x) +{ + switch (x) { + case 10: + case 20: + global += 1; + return 3; + case 30: + case 33 ... 55: + case 57: + return 4; + case 60 ... 62: + return 1; + case 600 ... 700: + return 12; + case 1000 ... 1010: + case 1012: + return 333; + case 1019: + case 1021: + return 9; + case 111111: + return 3; + default: + return 0; + } +} + +/* { dg-final { scan-tree-dump ";; GIMPLE switch case clusters: JT:10-62 600-700 JT:1000-1021 111111" "switchlower1" } } */ diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c index 62ae8849474..5048a6cb951 100644 --- a/gcc/tree-switch-conversion.c +++ b/gcc/tree-switch-conversion.c @@ -1118,6 +1118,8 @@ jump_table_cluster::find_jump_tables (vec &clusters) && can_be_handled (clusters, j, i - 1)) min[i] = min_cluster_item (min[j].m_count + 1, j, s); } + + gcc_checking_assert (min[i].m_count != INT_MAX); } /* No result. */ @@ -1169,8 +1171,13 @@ jump_table_cluster::can_be_handled (const vec &clusters, if (!flag_jump_tables) return false; - unsigned HOST_WIDE_INT max_ratio = optimize_insn_for_size_p () ? 3 : 8; + /* For algorithm correctness, jump table for a single case must return + true. We bail out in is_beneficial if it's called just for + a single case. */ + if (start == end) + return true; + unsigned HOST_WIDE_INT max_ratio = optimize_insn_for_size_p () ? 3 : 8; unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (), clusters[end]->get_high ()); /* Check overflow. */ @@ -1194,6 +1201,10 @@ bool jump_table_cluster::is_beneficial (const vec &, unsigned start, unsigned end) { + /* Single case bail out. */ + if (start == end) + return false; + return end - start + 1 >= case_values_threshold (); } @@ -1223,6 +1234,8 @@ bit_test_cluster::find_bit_tests (vec &clusters) && can_be_handled (clusters, j, i - 1)) min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX); } + + gcc_checking_assert (min[i].m_count != INT_MAX); } /* No result. */ @@ -1274,6 +1287,12 @@ bool bit_test_cluster::can_be_handled (const vec &clusters, unsigned start, unsigned end) { + /* For algorithm correctness, bit test for a single case must return + true. We bail out in is_beneficial if it's called just for + a single case. */ + if (start == end) + return true; + unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (), clusters[end]->get_high ()); auto_bitmap dest_bbs; @@ -1305,6 +1324,10 @@ bool bit_test_cluster::is_beneficial (const vec &clusters, unsigned start, unsigned end) { + /* Single case bail out. */ + if (start == end) + return false; + auto_bitmap dest_bbs; for (unsigned i = start; i <= end; i++) @@ -1596,7 +1619,7 @@ switch_decision_tree::analyze_switch_statement () /* Find jump table clusters. */ vec output = jump_table_cluster::find_jump_tables (clusters); - /* Find jump table clusters. */ + /* Find bit test clusters. */ vec output2; auto_vec tmp; output2.create (1);