From patchwork Sat Jul 23 03:25:26 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 651811 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 3rxCb66M5Cz9t1L for ; Sat, 23 Jul 2016 13:25:52 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=Tw39Dhau; 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 :date:to:cc:subject:in-reply-to:message-id:references :mime-version:content-type; q=dns; s=default; b=ZOsGEGrOCXI3aDnb Pv8uYtOqh2tSs4OkGRG54O+FWYUz1eNrpKz7BD9yP9Vf+4IbhG7b01cPnFJJles5 FQl6pZklwSAvAoPPFx226sQTtnpXRn7UcGTwYNFbll5dnd8TS346GnUAIpW8uglw PfdaorRm9KwFGVTTMBrMUjpUx6o= 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 :date:to:cc:subject:in-reply-to:message-id:references :mime-version:content-type; s=default; bh=6qrIsLzgnrAB1zFZKqpOGt sNFlE=; b=Tw39DhauViN878JaN1HflQyG0gOOaKbS0ZR2XVQaocNXQWaKcLZw1m SSUDhvlNUPse0haW8VVt61bo2AZrduDKyzb4Um0bJZII58D5A3rnxTACiuU5tyB9 V3M9yTxf5Yka1P2EEi2mwWOXTYTzEcZ8xk/N5SilRvWbuTP6DciZE= Received: (qmail 31728 invoked by alias); 23 Jul 2016 03:25: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 31716 invoked by uid 89); 23 Jul 2016 03:25:41 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.4 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.2 spammy=resort, registering, Resort, LAST 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; Sat, 23 Jul 2016 03:25:30 +0000 Received: by mail-qt0-f193.google.com with SMTP id j37so6045534qta.0 for ; Fri, 22 Jul 2016 20:25:30 -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:date:to:cc:subject:in-reply-to:message-id :references:user-agent:mime-version; bh=voL4/TJjpY3RPsFDatX1kmC8plCsdIQhvoPReT+hWMY=; b=YmjlXQzbd3Ubow2J+3znEvnttH7Bs3u1tZX6Ec3H08tiqDNZs69WzkxskYDmq4I+Tw 04EpKQfGrrs5zlyGSaThn7MdaSWvXryyPvR+Xx44aMp7uw6C21ePPw6q86bDcOvN28/D mtD8wRzwNKndyxbwARdwvDKbIoVtg9j8vvVGcSo9S8nqOL8Q+zjuMeHUDWaf3YJT0DxA cobKjREje6IDzjEd9lyUvw+VJpcI68bsXck5AetxwYxzHAXtTsjZ2fc+BJjsJz1a+1ja bpu363+uU+e5kOHneg6+/+ehW6uTv0sPK6akY8Z1GGKoftYLct/mCfn4r7xITwPR9j1l Kf9A== X-Gm-Message-State: AEkooutg2WDPL7nbimBngPt9KPw7xCE3E/kKpfuIamD1FSvglESfSNb7WEiBIH3GNAGsAg== X-Received: by 10.200.43.47 with SMTP id 44mr11431049qtu.66.1469244328229; Fri, 22 Jul 2016 20:25:28 -0700 (PDT) Received: from [192.168.1.130] (ool-4353abbc.dyn.optonline.net. [67.83.171.188]) by smtp.gmail.com with ESMTPSA id e7sm9076998qtb.9.2016.07.22.20.25.27 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 22 Jul 2016 20:25:27 -0700 (PDT) From: Patrick Palka X-Google-Original-From: Patrick Palka Date: Fri, 22 Jul 2016 23:25:26 -0400 (EDT) To: Patrick Palka cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH] Teach VRP to register assertions along default switch labels (PR 18046) In-Reply-To: Message-ID: References: <20160722192630.23771-1-patrick@parcs.ath.cx> User-Agent: Alpine 2.20.13 (DEB 116 2015-12-14) MIME-Version: 1.0 On Fri, 22 Jul 2016, Patrick Palka wrote: > On Fri, 22 Jul 2016, Patrick Palka wrote: > > > This patch teaches VRP to register along a default switch label > > assertions that corresponds to the anti range of each case label. > > > > Does this look OK to commit after bootstrap + regtest on > > x86_64-pc-linux-gnu? > > Forgot the changelog: > > gcc/ChangeLog: > > PR tree-optimization/18046 > * tree-vrp.c (find_switch_asserts): Register edge assertions > for the default label which correspond to the anti-ranges > of each non-case label. > > gcc/testsuite/ChangeLog: > > PR tree-optimization/18046 > * gcc.dg/tree-ssa/ssa-dom-thread-6.c: Bump FSM count to 5. > * gcc.dg/tree-ssa/vrp103.c: New test. > * gcc.dg/tree-ssa/vrp104.c: New test. > The patch failed to bootstrap due to a number -Warray-bounds warnings getting emitted for the autogenerated header file insn-modes.h: In file included from /home/patrick/code/gcc/gcc/machmode.h:24:0, from /home/patrick/code/gcc/gcc/coretypes.h:391, from /home/patrick/code/gcc/gcc/lto-streamer-out.c:25: ./insn-modes.h: In function ‘void produce_asm_for_decls()’: ./insn-modes.h:638:36: warning: array subscript is outside array bounds [-Warray-bounds] default: return mode_inner[mode]; ~~~~~~~~~~~~~~~^ These new warnings seem legitimate. From what I can tell, this array access along the default switch label will always be out of bounds. The code it's warning about basically looks like this: enum A { a, b, c }; int foo (A i) { int array[3]; switch (i) { case a: return x; case b: return y; case c: return z; default: return array[i]; } } and while the switch does exhaust every possible enumeration value of A, there's nothing stopping the user from passing an arbitrary int to foo() thus triggering the default case. So this patch suppresses these warnings by making genemit emit an assertion that verifies that mode is within the bounds of the array. This assertion won't affect performance because the mode_*_inline functions are always called with constant arguments. This version of the patch has the following changes: 1. Fixes the bootstrap failure as mentioned above. 2. Checks if the switch operand is live along the default edge before registering assertions. 3. Combines contiguous case ranges to reduce the number of assert expressions to insert. Bootstrap + regtesting in progress on x86_64-pc-linux-gnu. gcc/ChangeLog: PR tree-optimization/18046 * genmodes.c (emit_mode_size_inline): Emit an assert that verifies that mode is a valid array index. (emit_mode_nuinits_inline): Likewise. (emit_mode_inner_inline): Likewise. (emit_mode_unit_size_inline): Likewise. (emit_mode_unit_precision_inline): Likewise. * tree-vrp.c (compare_case_label_values): New qsort callback. (find_switch_asserts): Register edge assertions for the default label, which correspond to the anti-range of each non-case label. gcc/testsuite/ChangeLog: PR tree-optimization/18046 * gcc.dg/tree-ssa/ssa-dom-thread-6.c: Bump FSM count to 5. * gcc.dg/tree-ssa/vrp103.c: New test. * gcc.dg/tree-ssa/vrp104.c: New test. --- gcc/genmodes.c | 5 ++ gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c | 2 +- gcc/testsuite/gcc.dg/tree-ssa/vrp103.c | 30 +++++++++ gcc/testsuite/gcc.dg/tree-ssa/vrp104.c | 32 +++++++++ gcc/tree-vrp.c | 85 +++++++++++++++++++++++- 5 files changed, 151 insertions(+), 3 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp103.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c diff --git a/gcc/genmodes.c b/gcc/genmodes.c index 097cc80..1170d4f 100644 --- a/gcc/genmodes.c +++ b/gcc/genmodes.c @@ -976,6 +976,7 @@ unsigned char\n\ mode_size_inline (machine_mode mode)\n\ {\n\ extern %sunsigned char mode_size[NUM_MACHINE_MODES];\n\ + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ switch (mode)\n\ {\n", adj_bytesize ? "" : "const "); @@ -1006,6 +1007,7 @@ unsigned char\n\ mode_nunits_inline (machine_mode mode)\n\ {\n\ extern const unsigned char mode_nunits[NUM_MACHINE_MODES];\n\ + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ switch (mode)\n\ {"); @@ -1035,6 +1037,7 @@ unsigned char\n\ mode_inner_inline (machine_mode mode)\n\ {\n\ extern const unsigned char mode_inner[NUM_MACHINE_MODES];\n\ + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ switch (mode)\n\ {"); @@ -1067,6 +1070,7 @@ mode_unit_size_inline (machine_mode mode)\n\ {\n\ extern CONST_MODE_UNIT_SIZE unsigned char mode_unit_size[NUM_MACHINE_MODES];\ \n\ + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ switch (mode)\n\ {"); @@ -1103,6 +1107,7 @@ unsigned short\n\ mode_unit_precision_inline (machine_mode mode)\n\ {\n\ extern const unsigned short mode_unit_precision[NUM_MACHINE_MODES];\n\ + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ switch (mode)\n\ {"); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c index 5ec4687..551fbac 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c @@ -1,7 +1,7 @@ /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-thread1-details -fdump-tree-thread2-details" } */ /* { dg-final { scan-tree-dump-times "FSM" 3 "thread1" } } */ -/* { dg-final { scan-tree-dump-times "FSM" 4 "thread2" } } */ +/* { dg-final { scan-tree-dump-times "FSM" 5 "thread2" } } */ int sum0, sum1, sum2, sum3; int foo (char *s, char **ret) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c new file mode 100644 index 0000000..eea98bb --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c @@ -0,0 +1,30 @@ +/* PR tree-optimization/18046 */ +/* { dg-options "-O2 -fdump-tree-vrp" } */ +/* { dg-final { scan-tree-dump-times "baz \\(0\\);" 4 "vrp1" } } */ + +void foo (); +void bar (); +void baz (int); + +void +test (int i) +{ + switch (i) + { + case 1: + case 2: + case 3: + foo (); + break; + case 5: + bar (); + break; + default: + /* These tests should be folded to 0, resulting in 4 calls to bar (0). */ + baz (i == 1); + baz (i == 2); + baz (i == 3); + baz (i == 5); + break; + } +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c new file mode 100644 index 0000000..6410847 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c @@ -0,0 +1,32 @@ +/* PR tree-optimization/18046 */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-times "switch" 1 "optimized" } } */ + +void foo (); +void bar (); + +void +test (int i) +{ + switch (i) + { + case 1: + foo (); + break; + case 2: + bar (); + break; + default: + break; + } + + /* This switch should be gone after threading/VRP. */ + switch (i) + { + case 1: + foo (); + break; + default: + break; + } +} diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 06364b7..a3068ec 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -5882,6 +5882,24 @@ compare_case_labels (const void *p1, const void *p2) return 1; } +/* Compare two case labels sorting only by the case value. */ + +static int +compare_case_label_values (const void *p1, const void *p2) +{ + const struct case_info *ci1 = (const struct case_info *) p1; + const struct case_info *ci2 = (const struct case_info *) p2; + + /* Make sure the default label is first. */ + if (!CASE_LOW (ci1->expr)) + return -1; + else if (!CASE_LOW (ci2->expr)) + return 1; + else + return tree_int_cst_compare (CASE_LOW (ci1->expr), + CASE_LOW (ci2->expr)); +} + /* Determine whether the outgoing edges of BB should receive an ASSERT_EXPR for each of the operands of BB's LAST statement. The last statement of BB must be a SWITCH_EXPR. @@ -5917,6 +5935,7 @@ find_switch_asserts (basic_block bb, gswitch *last) ci[idx].expr = gimple_switch_label (last, idx); ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr)); } + edge default_edge = find_edge (bb, ci[0].bb); qsort (ci, n, sizeof (struct case_info), compare_case_labels); for (idx = 0; idx < n; ++idx) @@ -5945,8 +5964,8 @@ find_switch_asserts (basic_block bb, gswitch *last) max = CASE_LOW (ci[idx].expr); } - /* Nothing to do if the range includes the default label until we - can register anti-ranges. */ + /* Can't extract a useful assertion out of a range that includes the + default label. */ if (min == NULL_TREE) continue; @@ -5963,6 +5982,68 @@ find_switch_asserts (basic_block bb, gswitch *last) fold_convert (TREE_TYPE (op), max)); } + if (live_on_edge (default_edge, op)) + { + /* Re-sort the vector by just the case values so that we can easily + combine contiguous case ranges below. */ + qsort (ci, n, sizeof (struct case_info), compare_case_label_values); + gcc_assert (CASE_LOW (ci[0].expr) == NULL_TREE); + + /* Register along the default label assertions that correspond to the + anti-range of each label. */ + for (idx = 1; idx < n; idx++) + { + tree min, max; + tree cl = ci[idx].expr; + + min = CASE_LOW (cl); + max = CASE_HIGH (cl); + + /* Combine contiguous case range to reduce the number of assertions + to insert. */ + for (idx = idx + 1; idx < n; idx++) + { + tree next_min, next_max; + tree next_cl = ci[idx].expr; + + next_min = CASE_LOW (next_cl); + next_max = CASE_HIGH (next_cl); + + tree difference + = int_const_binop (MINUS_EXPR, next_min, max ? max : min); + if (integer_onep (difference)) + max = next_max ? next_max : next_min; + else + { + gcc_assert (tree_int_cst_sgn (difference) > 0); + break; + } + } + idx--; + + if (max == NULL_TREE) + { + /* Register the assertion OP != MIN. */ + min = fold_convert (TREE_TYPE (op), min); + register_edge_assert_for (op, default_edge, bsi, + NE_EXPR, op, min); + } + else + { + /* Register the assertion (unsigned)OP - MIN > (MAX - MIN), + which will give OP the anti-range ~[MIN,MAX]. */ + tree uop = fold_convert (unsigned_type_for (TREE_TYPE (op)), op); + min = fold_convert (TREE_TYPE (uop), min); + max = fold_convert (TREE_TYPE (uop), max); + + tree lhs = fold_build2 (MINUS_EXPR, TREE_TYPE (uop), uop, min); + tree rhs = int_const_binop (MINUS_EXPR, max, min); + register_new_assert_for (op, lhs, GT_EXPR, rhs, + NULL, default_edge, bsi); + } + } + } + XDELETEVEC (ci); }