From patchwork Wed Aug 3 04:00:21 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 655250 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 3s3zrN0F7Xz9sXx for ; Wed, 3 Aug 2016 14:00:51 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=tjBbv4x+; 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:from :to:cc:subject:date:message-id; q=dns; s=default; b=x9TMPhxa3cqT j4KiaKfx3wSw47P9XQTtwfr1YHl4kge1g3Pu8egIc/lW08T64GVv6a+jJMIZsJZv +g7hYE7W0MbM8AnX1pEfjPdEJV7W+8OlVsKZQhxp3FJTw+ggUoDRLLQS/Q2gQebD 854S+gwN3jrA/if8oXkD/e3kTRaBJtY= 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 :to:cc:subject:date:message-id; s=default; bh=nNv5BZequhDjesADCO O4DAqFSzc=; b=tjBbv4x+MvVdcST7TLUqlhBd+Tjupikf2nlK713O0c4zRc2BoV s4R2uevfxsRTIKk4Z2jJSOFBzIG8uPdsmN6YFOuj448AJrAeOz+8mzeMPM3ujdZL zoyXUbDg9OrHMK/9VZuFx1zfWlcCOX3Vmfa5v0Dx7vXO3IVZhHd9Kh8hU= Received: (qmail 109293 invoked by alias); 3 Aug 2016 04:00: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 109257 invoked by uid 89); 3 Aug 2016 04:00:41 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.5 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.2 spammy=redundancy, rare, 78, complements X-HELO: mail-qt0-f193.google.com Received: from mail-qt0-f193.google.com (HELO mail-qt0-f193.google.com) (209.85.216.193) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Wed, 03 Aug 2016 04:00:31 +0000 Received: by mail-qt0-f193.google.com with SMTP id q11so10493035qtb.2 for ; Tue, 02 Aug 2016 21:00:31 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id; bh=mudvAtvsyS7VxfStzNIovsZeF9Pm6xiWiydK8XCkw+c=; b=fLPyeEPps8JKsNMlYeFqcWKAXl+Ce7Ze7Z825rwHBZyTqYJcwAnBdw5qcV2oANp+Eg OfJoCvLimBgFYmHUx+QBu3NP0zzfLREOiUAAfyll4Zo0kRQarkrwhiI1mRicUpomYUDb kqcDyo5hFkZUOiIgrlJJ1UPyHlvAaNUrE/BGQ+mjE0NMn2hYMoqyjjVSD2acfHmBa+Zn 7ZFcFtilmMDuedSGdEhCJDIGqQziBITrbvzkSnhoG1GUdrh+gMhvanCp0VpYa/d4ywMk 7kUTbHtPx2nl/uDEQ/92dbRxzBpTGHwzdUxFTu3Pvt87eOvmDKbDBKnbAckG8u/6ruZ+ /ToQ== X-Gm-Message-State: AEkoouvrFIftXR7JMqGxO0KOmkl0n/yeZTyANNM3HpIH4cRDfTyrWBO+lKVrVUmTBwHBYw== X-Received: by 10.200.52.182 with SMTP id w51mr104813208qtb.90.1470196828871; Tue, 02 Aug 2016 21:00:28 -0700 (PDT) Received: from localhost.localdomain (ool-4353abbc.dyn.optonline.net. [67.83.171.188]) by smtp.gmail.com with ESMTPSA id l32sm3202197qta.23.2016.08.02.21.00.27 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 02 Aug 2016 21:00:28 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: Patrick Palka Subject: [PATCH] Teach VRP to truncate the case ranges of a switch Date: Wed, 3 Aug 2016 00:00:21 -0400 Message-Id: <20160803040021.11430-1-patrick@parcs.ath.cx> VRP currently has functionality to eliminate case labels that lie completely outside of the switch operand's value range. This patch complements this functionality by teaching VRP to also truncate the case label ranges that partially overlap with the operand's value range. Bootstrapped and regtested on x86_64-pc-linux-gnu. Does this look like a reasonable optimization? Admittedly, its effect will almost always be negligible except in cases where a case label range spans a large number of values which is a pretty rare thing. The optimization triggered about 250 times during bootstrap. gcc/ChangeLog: * tree-vrp.c (simplify_switch_using_ranges): Try to truncate the case label ranges that partially overlap with OP's value range. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/vrp107.c: New test. * gcc.dg/tree-ssa/vrp108.c: New test. * gcc.dg/tree-ssa/vrp109.c: New test. --- gcc/testsuite/gcc.dg/tree-ssa/vrp107.c | 25 +++++++++++ gcc/testsuite/gcc.dg/tree-ssa/vrp108.c | 25 +++++++++++ gcc/testsuite/gcc.dg/tree-ssa/vrp109.c | 65 +++++++++++++++++++++++++++ gcc/tree-vrp.c | 80 +++++++++++++++++++++++++++++++++- 4 files changed, 194 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp107.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp108.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp109.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c new file mode 100644 index 0000000..b74f031 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c @@ -0,0 +1,25 @@ +/* { dg-options "-O2 -fdump-tree-vrp1" } */ +/* { dg-final { scan-tree-dump "case 2:" "vrp1" } } */ +/* { dg-final { scan-tree-dump "case 7 ... 8:" "vrp1" } } */ + +extern void foo (void); +extern void bar (void); +extern void baz (void); + +void +test (int i) +{ + if (i >= 2 && i <= 8) + switch (i) + { + case 1: /* Redundant label. */ + case 2: + bar (); + break; + case 7: + case 8: + case 9: /* Redundant label. */ + baz (); + break; + } +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c new file mode 100644 index 0000000..49dbfb5 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c @@ -0,0 +1,25 @@ +/* { dg-options "-O2 -fdump-tree-vrp1" } */ +/* { dg-final { scan-tree-dump "case 1:" "vrp1" } } */ +/* { dg-final { scan-tree-dump "case 9:" "vrp1" } } */ + +extern void foo (void); +extern void bar (void); +extern void baz (void); + +void +test (int i) +{ + if (i < 2 || i > 8) + switch (i) + { + case 1: + case 2: /* Redundant label. */ + bar (); + break; + case 7: /* Redundant label. */ + case 8: /* Redundant label. */ + case 9: + baz (); + break; + } +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c new file mode 100644 index 0000000..86299a9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c @@ -0,0 +1,65 @@ +/* { dg-options "-O2 -fdump-tree-vrp1" } */ +/* { dg-final { scan-tree-dump "case 9 ... 10:" "vrp1" } } */ +/* { dg-final { scan-tree-dump "case 17 ... 18:" "vrp1" } } */ +/* { dg-final { scan-tree-dump "case 27 ... 30:" "vrp1" } } */ + +extern void foo (void); +extern void bar (void); + +void +test1 (int i) +{ + if (i != 7 && i != 8) + switch (i) + { + case 1: + case 2: + foo (); + break; + case 7: /* Redundant label. */ + case 8: /* Redundant label. */ + case 9: + case 10: + bar (); + break; + } +} + +void +test3 (int i) +{ + if (i != 19 && i != 20) + switch (i) + { + case 1: + case 2: + foo (); + break; + case 17: + case 18: + case 19: /* Redundant label. */ + case 20: /* Redundant label. */ + bar (); + break; + } +} + +void +test2 (int i) +{ + if (i != 28 && i != 29) + switch (i) + { + case 1: + case 2: + foo (); + break; + /* No redundancy. */ + case 27: + case 28: + case 29: + case 30: + bar (); + break; + } +} diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index cb316b0..b654b1b 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -9586,7 +9586,7 @@ static bool simplify_switch_using_ranges (gswitch *stmt) { tree op = gimple_switch_index (stmt); - value_range *vr; + value_range *vr = NULL; bool take_default; edge e; edge_iterator ei; @@ -9626,6 +9626,84 @@ simplify_switch_using_ranges (gswitch *stmt) n = gimple_switch_num_labels (stmt); + /* We can truncate the case label ranges that partially overlap with OP's + value range. */ + size_t min_idx = 1, max_idx = 0; + if (vr != NULL) + find_case_label_range (stmt, vr->min, vr->max, &min_idx, &max_idx); + if (min_idx <= max_idx) + { + tree min_label = gimple_switch_label (stmt, min_idx); + tree max_label = gimple_switch_label (stmt, max_idx); + + if (vr->type == VR_RANGE) + { + /* If OP's value range is [2,8] and the low label range is + 0 ... 3, truncate the label's range to 2 .. 3. */ + if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0 + && CASE_HIGH (min_label) != NULL_TREE + && tree_int_cst_compare (CASE_HIGH (min_label), vr->min) >= 0) + CASE_LOW (min_label) = vr->min; + + /* If OP's value range is [2,8] and the high label range is + 7 ... 10, truncate the label's range to 7 .. 8. */ + if (tree_int_cst_compare (CASE_LOW (max_label), vr->max) <= 0 + && CASE_HIGH (max_label) != NULL_TREE + && tree_int_cst_compare (CASE_HIGH (max_label), vr->max) > 0) + CASE_HIGH (max_label) = vr->max; + } + else if (vr->type == VR_ANTI_RANGE) + { + tree one_cst = build_one_cst (TREE_TYPE (op)); + + if (min_label == max_label) + { + /* If OP's value range is ~[7,8] and the label's range is + 7 ... 10, truncate the label's range to 9 ... 10. */ + if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) == 0 + && CASE_HIGH (min_label) != NULL_TREE + && tree_int_cst_compare (CASE_HIGH (min_label), vr->max) > 0) + CASE_LOW (min_label) + = int_const_binop (PLUS_EXPR, vr->max, one_cst); + + /* If OP's value range is ~[7,8] and the label's range is + 5 ... 8, truncate the label's range to 5 ... 6. */ + if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0 + && CASE_HIGH (min_label) != NULL_TREE + && tree_int_cst_compare (CASE_HIGH (min_label), vr->max) == 0) + CASE_HIGH (min_label) + = int_const_binop (MINUS_EXPR, vr->min, one_cst); + } + else + { + /* If OP's value range is ~[2,8] and the low label range is + 0 ... 3, truncate the label's range to 0 ... 1. */ + if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0 + && CASE_HIGH (min_label) != NULL_TREE + && tree_int_cst_compare (CASE_HIGH (min_label), vr->min) >= 0) + CASE_HIGH (min_label) + = int_const_binop (MINUS_EXPR, vr->min, one_cst); + + /* If OP's value range is ~[2,8] and the high label range is + 7 ... 10, truncate the label's range to 9 ... 10. */ + if (tree_int_cst_compare (CASE_LOW (max_label), vr->max) <= 0 + && CASE_HIGH (max_label) != NULL_TREE + && tree_int_cst_compare (CASE_HIGH (max_label), vr->max) > 0) + CASE_LOW (max_label) + = int_const_binop (PLUS_EXPR, vr->max, one_cst); + } + } + + /* Canonicalize singleton case ranges. */ + if (tree_int_cst_equal (CASE_LOW (min_label), CASE_HIGH (min_label))) + CASE_HIGH (min_label) = NULL_TREE; + if (tree_int_cst_equal (CASE_LOW (max_label), CASE_HIGH (max_label))) + CASE_HIGH (max_label) = NULL_TREE; + } + + /* We can also eliminate case labels that lie completely outside OP's value + range. */ + /* Bail out if this is just all edges taken. */ if (i == 1 && j == n - 1