From patchwork Sat Apr 15 07:41:37 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 83650 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:b0ea:0:b0:3b6:4342:cba0 with SMTP id b10csp904627vqo; Sat, 15 Apr 2023 01:30:26 -0700 (PDT) X-Google-Smtp-Source: AKy350Z9M4Ko3sUwE1o10uAMLPg2HCj5sYKWEgDVsOig7sxpmzSw+BvWqMArrno6Qp3W8L4g2O0G X-Received: by 2002:a17:906:82c5:b0:94a:8e19:6aba with SMTP id a5-20020a17090682c500b0094a8e196abamr1557726ejy.21.1681547426027; Sat, 15 Apr 2023 01:30:26 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1681547426; cv=none; d=google.com; s=arc-20160816; b=uPF8uEX4HKuhe6YckGJ2q2LOJue1AcqVkUSFTUtyj/QPIf2+PwbbIX3JZVKeoIjLuW rQlAOYFZ/n7XW1cAW1oagNEMb1FjiriQWZCixWu7gpn34oTRH/FaM5iQjtb97rkf+6f3 JsH72t4h1GecSUBZLwotPdkxeyqKl/D+DW4XPRjXlTorEYzWbbHJNADXYOe5hxDnpSwd aEKXB4s8o/D5NUgs+cN8KoQQHOn2TNJKGuNk4tawsw76waXDW2qjEp6tMxE6Vqbx2EKZ ssQgiXHbfe3X6YpRSSpsOXIlw8d9voUAIFIre4j8/Ck8BQRn16bLQDUZF9wPNFQ8b2n3 8oZQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-disposition:mime-version:message-id:subject:cc:to:date :resent-to:resent-message-id:resent-date:resent-from:dmarc-filter :delivered-to:dkim-signature:dkim-filter; bh=7CQwxSwUCQmg1sl47Vz2SmY6oMc1W1dVh8doNC0EHUw=; b=JXCLFw3ZPFDkLPAkxmwL2wJ9bvYeBF5np0KE3S5O1ud87Ykcy/ZcHNKHpr2Qa0cwLr JpVjitcHRR/sb+C6gtpZQrwbU1nZUks/oUsyW47ogi6o6yj0rZF3lsLTLVWkwnGQM4W6 I+AFYKx4GS45O1N1052zpxyeYJatzfKRei02DjQfAAQeT39H1p6d1Iw5HUoiem1TXz0L ZTriDABFT1BxqYxmxKSa03swsGZkykFeTP7e3xFtxdO50mHDFhn1bwq309JgdPwVj87i GRf3vs4vF6rjMNcDA9vp/P/8OjVWOcsqenGVc2B111/NeruDbwaJnyD2v+lBE64KCpfi vzUA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=vg6BFZ1S; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id fr37-20020a170906892500b0094f1e8845ccsi738572ejc.676.2023.04.15.01.30.25 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 15 Apr 2023 01:30:26 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=vg6BFZ1S; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id CB725385735A for ; Sat, 15 Apr 2023 08:30:24 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org CB725385735A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1681547424; bh=7CQwxSwUCQmg1sl47Vz2SmY6oMc1W1dVh8doNC0EHUw=; h=Resent-From:Resent-Date:Resent-To:Date:To:Cc:Subject:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=vg6BFZ1Shmd6X/PGzR0DSyx/amoRK9XSTOOfxbNpAJJgz/UM+OAtIxTOMkF+dHgYP aE0B4DJ/z2Ea70gQiAL16aIGC5DssJWn21BxrOPY15zfpJZJBsJZ3FMM4PW6cABemb 6W5aVBG+w5inw4zwCzAYF8Lk1f+f2mpe1Yh1M2II= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id A74EB385772C for ; Sat, 15 Apr 2023 08:29:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org A74EB385772C Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-78-SdPgGdb9OXCSqKE6wzzXuA-1; Sat, 15 Apr 2023 04:29:22 -0400 X-MC-Unique: SdPgGdb9OXCSqKE6wzzXuA-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.rdu2.redhat.com [10.11.54.1]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 6B7AC855300; Sat, 15 Apr 2023 08:29:22 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.192.16]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 2797740B3ED9; Sat, 15 Apr 2023 08:29:22 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.17.1/8.17.1) with ESMTPS id 33F8TJvk2195261 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Sat, 15 Apr 2023 10:29:19 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.17.1/8.17.1/Submit) id 33F8TDXO2195256; Sat, 15 Apr 2023 10:29:13 +0200 Resent-From: Jakub Jelinek Resent-Date: Sat, 15 Apr 2023 10:29:13 +0200 Resent-Message-ID: Resent-To: Richard Biener , gcc-patches@gcc.gnu.org Date: Sat, 15 Apr 2023 09:41:37 +0200 To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] if-conv: Small improvement for expansion of complex PHIs [PR109154] Message-ID: MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.1 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Disposition: inline X-Spam-Status: No, score=-3.3 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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: , X-Patchwork-Original-From: Jakub Jelinek via Gcc-patches From: Jakub Jelinek Reply-To: Jakub Jelinek Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1763230273690000226?= X-GMAIL-MSGID: =?utf-8?q?1763230273690000226?= Hi! The following patch is just a dumb improvement, gets rid of 2 unnecessary instructions on both the PR's original testcase and on the two reduced ones, both on -mcpu=neoverse-v1 and -mavx512f. The thing is, if we have args_len (args_len >= 2) unique PHI arguments, we need only args_len - 1 COND_EXPRs to expand the PHI, because first COND_EXPR can merge 2 unique arguments and all the following ones merge another unique argument with the previously merged arguments, while the code for mysterious reasons was always emitting args_len COND_EXPRs, where the first COND_EXPR merged the first and second unique arguments, the second COND_EXPR merged the second unique argument with result of merging the first and second unique arguments and the rest was already expectable, nth COND_EXPR for n > 2 merged the nth unique argument with result of merging the previous unique arguments. Now, in my understanding, the bb_predicate for bb's predecessor need to form a disjunct set which together creates the successor's bb_predicate, so I don't see why we'd need to check all the bb_predicates, if we check all but one then when all those other ones are false the last bb_predicate is necessarily true. Given that the code attempts to sort argument with most occurrences (so likely most complex combined predicate) last, I chose not to test that last argument's predicate. So e.g. on the testcase from comment 47 in the PR: void foo (int *f, int d, int e) { for (int i = 0; i < 1024; i++) { int a = f[i]; int t; if (a < 0) t = 1; else if (a < e) t = 1 - a * d; else t = 0; f[i] = t; } } we used to emit: _7 = a_10 < 0; _21 = a_10 >= 0; _22 = a_10 < e_11(D); _23 = _21 & _22; _26 = a_10 >= e_11(D); _27 = _21 & _26; _ifc__42 = _7 ? 1 : t_13; _ifc__43 = _23 ? t_13 : _ifc__42; t_6 = _27 ? 0 : _ifc__43; while the following patch changes it to: _7 = a_10 < 0; _21 = a_10 >= 0; _22 = a_10 < e_11(D); _23 = _21 & _22; _ifc__42 = _23 ? t_13 : 0; t_6 = _7 ? 1 : _ifc__42; which I believe should be sufficient for a PHI <1, t_13, 0>. I've gathered some statistics and on x86_64-linux and i686-linux bootstraps/regtests, this code triggers: 92 4 4 112 2 4 141 3 4 4046 3 3 (where 2nd number is args_len and 3rd argument EDGE_COUNT (bb->preds) and first argument count of those from sort | uniq -c | sort -n). In all these cases the patch should squeze one extra COND_EXPR and its associated predicate (the latter only if it wasn't used elsewhere). Incrementally, I think we should try to perform some analysis on which predicates depend on inverses of other predicates and if possible try to sort the arguments better and omit testing unnecessary predicates. So essentially for the above testcase deconstruct it back to: _7 = a_10 < 0; _22 = a_10 < e_11(D); _ifc__42 = _22 ? t_13 : 0; t_6 = _7 ? 1 : _ifc__42; which is like what this patch produces, but with the & a_10 >= 0 part removed, because the last predicate is a_10 < 0 and so testing a_10 >= 0 on what appears on the false branch doesn't make sense. But I'm afraid that will take more work than is doable in stage4 right now. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2023-04-15 Jakub Jelinek PR tree-optimization/109154 * tree-if-conv.cc (predicate_scalar_phi): For complex PHIs, emit just args_len - 1 COND_EXPRs rather than args_len. Formatting fix. Jakub --- gcc/tree-if-conv.cc.jj 2023-04-12 08:53:58.264496474 +0200 +++ gcc/tree-if-conv.cc 2023-04-14 21:02:42.403826690 +0200 @@ -2071,7 +2071,7 @@ predicate_scalar_phi (gphi *phi, gimple_ } /* Put element with max number of occurences to the end of ARGS. */ - if (max_ind != -1 && max_ind +1 != (int) args_len) + if (max_ind != -1 && max_ind + 1 != (int) args_len) std::swap (args[args_len - 1], args[max_ind]); /* Handle one special case when number of arguments with different values @@ -2116,12 +2116,12 @@ predicate_scalar_phi (gphi *phi, gimple_ vec *indexes; tree type = TREE_TYPE (gimple_phi_result (phi)); tree lhs; - arg1 = args[1]; - for (i = 0; i < args_len; i++) + arg1 = args[args_len - 1]; + for (i = args_len - 1; i > 0; i--) { - arg0 = args[i]; - indexes = phi_arg_map.get (args[i]); - if (i != args_len - 1) + arg0 = args[i - 1]; + indexes = phi_arg_map.get (args[i - 1]); + if (i != 1) lhs = make_temp_ssa_name (type, NULL, "_ifc_"); else lhs = res;