From patchwork Thu Jun 25 11:07:08 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Botcazou X-Patchwork-Id: 1316837 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=adacore.com Authentication-Results: ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=adacore-com.20150623.gappssmtp.com header.i=@adacore-com.20150623.gappssmtp.com header.a=rsa-sha256 header.s=20150623 header.b=FU14aL5K; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 49sy060GWcz9sPF for ; Thu, 25 Jun 2020 21:07:18 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 207473851C26; Thu, 25 Jun 2020 11:07:16 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-wm1-x333.google.com (mail-wm1-x333.google.com [IPv6:2a00:1450:4864:20::333]) by sourceware.org (Postfix) with ESMTPS id 73E393851C11 for ; Thu, 25 Jun 2020 11:07:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 73E393851C11 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=adacore.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=botcazou@adacore.com Received: by mail-wm1-x333.google.com with SMTP id f18so5492981wml.3 for ; Thu, 25 Jun 2020 04:07:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=adacore-com.20150623.gappssmtp.com; s=20150623; h=from:to:subject:date:message-id:mime-version :content-transfer-encoding; bh=9338EtVzkJSn+V44f81OVZwyvOSZYCqItR3g1tOuWx4=; b=FU14aL5KB/EGmf5ySA+BVJ4AVEZRd9RvMRJ0knc4vb5w3XfPqaAiIoT52p8W53H5z6 t5kTSlBoyYOcVAd0CiGb8vbunu8AuX6T4QUd37SFoQrB91ll76aNj67a+DxffQbT9tCk 1dG91QcPwxwyHkJVYy2gT+fHJ5c1H1o7wGNGYJg67jD63+f/JStdfAdX9E3ouSDpfhya YSWRnnEsWn+RN3GuKWbZUi8Z7FvvytS736B1dLl6jBHagkBgpzBS26TMFDEgne08t7Fb CW43LzSy3/XpjkjoaU7lY1cFz1ukX38jYM/Oak1whhSFpVYftR8a1inI0FPse9PP3a1o MFBA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:subject:date:message-id:mime-version :content-transfer-encoding; bh=9338EtVzkJSn+V44f81OVZwyvOSZYCqItR3g1tOuWx4=; b=I1LvOgqm/uaQLq35FU94C+d2icT6VRNz+9tBNClLNz1Cxp2nuWmE3ery3DywAiKxX1 g7PsBJo7H1GomLgw9rYUWQEgW6eyveWYGeTDJVRU/MpDWpR9lg89Ni7BK1nJkt+FNbM6 zvCqJyxTDlxZAtkJxe9dGrRNS298ZO7Cxh5GqyJHdWENTzxBZ3l8BKjp2Cb1IN/usqI+ nhbYMXMHOVHRH9jSl5wIPkX/jaSHXaR92K5bWHi5aG1f/B2JdS/NmCgwJ5l/+tc7Xj9l gwOgo6N5+7UXwEKB5WLNR9eSCgaCKSEK4T5sOZC4Iwg2q3RUitRPRe25sKDt98Wi+Wfx bE6g== X-Gm-Message-State: AOAM531U6KFU4d17NDT1nCDozTGvdV8OmZKCgxqvO6hrpGbTGwELSkla x/T8pRpYdSGJkfEm71SLDKPx/WBAwcqNFw== X-Google-Smtp-Source: ABdhPJxGAMinU44BHZ3XEB5ijRnV7j0Xwkoo96crEEftzPyKrhCslhKqJ8DSWxoYe8jdEERRTwzJmA== X-Received: by 2002:a1c:7717:: with SMTP id t23mr2734307wmi.75.1593083231017; Thu, 25 Jun 2020 04:07:11 -0700 (PDT) Received: from polaris.localnet ([2a01:e0a:41b:9230:1a03:73ff:fe45:373a]) by smtp.gmail.com with ESMTPSA id c66sm12699848wma.20.2020.06.25.04.07.09 for (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Thu, 25 Jun 2020 04:07:10 -0700 (PDT) From: Eric Botcazou X-Google-Original-From: Eric Botcazou To: gcc-patches@gcc.gnu.org Subject: [patch] Take into account range info to optimize range tests Date: Thu, 25 Jun 2020 13:07:08 +0200 Message-ID: <20170629.OGsMIjx87P@polaris> MIME-Version: 1.0 X-Spam-Status: No, score=-11.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, JMQ_SPF_NEUTRAL, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces@gcc.gnu.org Sender: "Gcc-patches" Hi, ...into bit tests, as done by optimize_range_tests_to_bit_test of the reassoc pass. The patch is aimed at addressing the following two issues: 1. In order to protect the shift operation from undefinedness, the new bit test is guarded with a new test, but this new test uses the range of the bit test values, not that of the shift operation so, if the input is in the range of the shift operation but not of the bit test values, then the subsequent VRP pass cannot eliminate the new test. Moreover changing the new test to use the range of the shift operation, instead of that of the bit test values, in the general case would pessimize the cases which are in between. 2. If the new test can be eliminated, then it becomes profitable to do the optimization into a bit test for one fewer comparison in the source code. Therefore the patch changes optimize_range_tests_to_bit_test to use the range info of the input in order to eliminate the new test if possible. Tested on x86-64/Linux, OK for the mainline? 2020-06-25 Eric Botcazou * tree-ssa-reassoc.c (dump_range_entry): New function. (debug_range_entry): New debug function. (update_range_test): Invoke dump_range_entry for dumping. (optimize_range_tests_to_bit_test): Merge the entry test in the bit test when possible and lower the profitability threshold in this case. 2020-06-25 Eric Botcazou * exp_ch4.adb (Expand_Set_Membership): Expand the membership test using left associativity instead of right associativity. 2020-06-25 Eric Botcazou * gnat.dg/opt86_pkg.ads: New helper. * gnat.dg/opt86a.adb: New test. * gnat.dg/opt86b.adb: Likewise. * gnat.dg/opt86c.adb: Likewise. diff --git a/gcc/ada/exp_ch4.adb b/gcc/ada/exp_ch4.adb index 2adebb6f54c..88dcb52349d 100644 --- a/gcc/ada/exp_ch4.adb +++ b/gcc/ada/exp_ch4.adb @@ -12879,16 +12879,19 @@ package body Exp_Ch4 is begin Remove_Side_Effects (Lop); - Alt := Last (Alternatives (N)); + Alt := First (Alternatives (N)); Res := Make_Cond (Alt); + Next (Alt); + + -- We use left associativity as in the equivalent boolean case. This + -- kind of canonicalization helps the optimizer of the code generator. - Prev (Alt); while Present (Alt) loop Res := Make_Or_Else (Sloc (Alt), - Left_Opnd => Make_Cond (Alt), - Right_Opnd => Res); - Prev (Alt); + Left_Opnd => Res, + Right_Opnd => Make_Cond (Alt)); + Next (Alt); end loop; Rewrite (N, Res); diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c index 2e67987f6c6..d06b693ec76 100644 --- a/gcc/tree-ssa-reassoc.c +++ b/gcc/tree-ssa-reassoc.c @@ -2416,6 +2416,32 @@ struct range_entry unsigned int idx, next; }; +void dump_range_entry (FILE *file, struct range_entry *r); +void debug_range_entry (struct range_entry *r); + +/* Dump the range entry R to FILE, skipping its expression if SKIP_EXP. */ + +void +dump_range_entry (FILE *file, struct range_entry *r, bool skip_exp) +{ + if (!skip_exp) + print_generic_expr (file, r->exp); + fprintf (file, " %c[", r->in_p ? '+' : '-'); + print_generic_expr (file, r->low); + fputs (", ", file); + print_generic_expr (file, r->high); + fputc (']', file); +} + +/* Dump the range entry R to STDERR. */ + +DEBUG_FUNCTION void +debug_range_entry (struct range_entry *r) +{ + dump_range_entry (stderr, r, false); + fputc ('\n', stderr); +} + /* This is similar to make_range in fold-const.c, but on top of GIMPLE instead of trees. If EXP is non-NULL, it should be an SSA_NAME and STMT argument is ignored, otherwise STMT @@ -2730,12 +2756,7 @@ update_range_test (struct range_entry *range, struct range_entry *otherrange, { struct range_entry *r; fprintf (dump_file, "Optimizing range tests "); - print_generic_expr (dump_file, range->exp); - fprintf (dump_file, " %c[", range->in_p ? '+' : '-'); - print_generic_expr (dump_file, range->low); - fprintf (dump_file, ", "); - print_generic_expr (dump_file, range->high); - fprintf (dump_file, "]"); + dump_range_entry (dump_file, range, false); for (i = 0; i < count; i++) { if (otherrange) @@ -2747,15 +2768,13 @@ update_range_test (struct range_entry *range, struct range_entry *otherrange, && TREE_CODE (r->exp) == SSA_NAME) { fprintf (dump_file, " and "); - print_generic_expr (dump_file, r->exp); + dump_range_entry (dump_file, r, false); } else - fprintf (dump_file, " and"); - fprintf (dump_file, " %c[", r->in_p ? '+' : '-'); - print_generic_expr (dump_file, r->low); - fprintf (dump_file, ", "); - print_generic_expr (dump_file, r->high); - fprintf (dump_file, "]"); + { + fprintf (dump_file, " and"); + dump_range_entry (dump_file, r, true); + } } fprintf (dump_file, "\n into "); print_generic_expr (dump_file, tem); @@ -3121,7 +3140,7 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length, int prec = GET_MODE_BITSIZE (word_mode); auto_vec candidates; - for (i = first; i < length - 2; i++) + for (i = first; i < length - 1; i++) { tree lowi, highi, lowj, highj, type; @@ -3184,8 +3203,32 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length, candidates.safe_push (&ranges[j]); } - /* If we need otherwise 3 or more comparisons, use a bit test. */ - if (candidates.length () >= 2) + /* If every possible relative value of the expression is a valid shift + amount, then we can merge the entry test in the bit test. In this + case, if we would need otherwise 2 or more comparisons, then use + the bit test; in the other cases, the threshold is 3 comparisons. */ + wide_int min, max; + bool entry_test_needed; + if (TREE_CODE (exp) == SSA_NAME + && get_range_info (exp, &min, &max) == VR_RANGE + && wi::leu_p (max - min, prec - 1)) + { + wide_int ilowi = wi::to_wide (lowi); + if (wi::lt_p (min, ilowi, TYPE_SIGN (TREE_TYPE (lowi)))) + { + lowi = wide_int_to_tree (TREE_TYPE (lowi), min); + mask = wi::lshift (mask, ilowi - min); + } + else if (wi::gt_p (min, ilowi, TYPE_SIGN (TREE_TYPE (lowi)))) + { + lowi = wide_int_to_tree (TREE_TYPE (lowi), min); + mask = wi::lrshift (mask, min - ilowi); + } + entry_test_needed = false; + } + else + entry_test_needed = true; + if (candidates.length () >= (entry_test_needed ? 2 : 1)) { tree high = wide_int_to_tree (TREE_TYPE (lowi), wi::to_widest (lowi) @@ -3224,10 +3267,16 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length, } } - tree tem = build_range_check (loc, optype, unshare_expr (exp), - false, lowi, high); - if (tem == NULL_TREE || is_gimple_val (tem)) - continue; + tree tem; + if (entry_test_needed) + { + tem = build_range_check (loc, optype, unshare_expr (exp), + false, lowi, high); + if (tem == NULL_TREE || is_gimple_val (tem)) + continue; + } + else + tem = NULL_TREE; tree etype = unsigned_type_for (TREE_TYPE (exp)); exp = fold_build2_loc (loc, MINUS_EXPR, etype, fold_convert_loc (loc, etype, exp), @@ -3248,27 +3297,34 @@ optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length, split when it is running. So, temporarily emit a code with BIT_IOR_EXPR instead of &&, and fix it up in branch_fixup. */ - gimple_seq seq; - tem = force_gimple_operand (tem, &seq, true, NULL_TREE); - gcc_assert (TREE_CODE (tem) == SSA_NAME); - gimple_set_visited (SSA_NAME_DEF_STMT (tem), true); + gimple_seq seq = NULL; + if (tem) + { + tem = force_gimple_operand (tem, &seq, true, NULL_TREE); + gcc_assert (TREE_CODE (tem) == SSA_NAME); + gimple_set_visited (SSA_NAME_DEF_STMT (tem), true); + } gimple_seq seq2; exp = force_gimple_operand (exp, &seq2, true, NULL_TREE); gimple_seq_add_seq_without_update (&seq, seq2); gcc_assert (TREE_CODE (exp) == SSA_NAME); gimple_set_visited (SSA_NAME_DEF_STMT (exp), true); - gimple *g = gimple_build_assign (make_ssa_name (optype), - BIT_IOR_EXPR, tem, exp); - gimple_set_location (g, loc); - gimple_seq_add_stmt_without_update (&seq, g); - exp = gimple_assign_lhs (g); + if (tem) + { + gimple *g = gimple_build_assign (make_ssa_name (optype), + BIT_IOR_EXPR, tem, exp); + gimple_set_location (g, loc); + gimple_seq_add_stmt_without_update (&seq, g); + exp = gimple_assign_lhs (g); + } tree val = build_zero_cst (optype); if (update_range_test (&ranges[i], NULL, candidates.address (), candidates.length (), opcode, ops, exp, seq, false, val, val, strict_overflow_p)) { any_changes = true; - reassoc_branch_fixups.safe_push (tem); + if (tem) + reassoc_branch_fixups.safe_push (tem); } else gimple_seq_discard (seq);