From patchwork Sun Nov 6 16:14:20 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 16157 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp1567099wru; Sun, 6 Nov 2022 08:15:20 -0800 (PST) X-Google-Smtp-Source: AA0mqf4fKmUYZjA9NrEdkAjI7z4G+jVMAOgw6aCAtFIXD9gGYqvgn/+wPgucuckSYrHJ7Y55q17f X-Received: by 2002:a17:906:3ada:b0:7ae:566e:3a1c with SMTP id z26-20020a1709063ada00b007ae566e3a1cmr5699118ejd.223.1667751320752; Sun, 06 Nov 2022 08:15:20 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1667751320; cv=none; d=google.com; s=arc-20160816; b=uqG4LRCBhngeS9bBypAmuCxLAMjq6skt+eg2ZN6RdNdm/ZLIOB4I0cWH7boxLGji2R QLJO9xp7GRZOiGtS8M4EmvcuYMp9t6lgWGjoaBW/Yn7p4TDMpBFVGfVBlgwHNXqLUt6w xD0NKMduWNxpzS46XrCubmI3zCPuPM1PPSPL21gEIUWHES/Lgv+uuwNmbIbhR0sOUmXz 9R1WHIB7K/x3TfTZBJFcg9HlkkUA3ipTUVyhSDMZBU8qnrXy+6ja5i6IasqvJkXiPvpE 3cG4O04jLDvoseMClNZ7bStCfiED2xADRzmw/BgCWQpynxqZ0Xgq9tvKjEeMdbOH94LA lJOg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:cc:reply-to:from:list-subscribe:list-help :list-post:list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:message-id:date:subject:to :dmarc-filter:delivered-to:dkim-signature:dkim-filter; bh=5e/RYt1uMG+KDgPN1jYlFakKuvb3AbcrrlgqVM3eMzw=; b=RW3cikXQtBT28rzoXBLdOTXtDbKz3MkvhAQkiqdQR/piZ+pkXIcDNZ6WJi3oOvCCn1 2eM8oupTS3AvtDXtEYDBpC8TOLq7RvpUr9OwReFNQvAvLG3DzqeCT7EyccQwOWYMX+vc WwRdxwVlhZ+G+82kglSNEYWwC770VMjL+QfwDWWCYad8srRRXCVu66yLKZmsW0ljKiLn JMLwxqTQNjEQPAJ3A5Z+ts37z/pMGbfEZB8b1SwVNTDyXjcTWz+jUYR0AeOAvndG2MwM hB4NPoaC6WWtmOkHbNzrYT/CAqu+yC51LHMyUkpQONber6RVUNw08xuDzNIOQuVuqw/t /HUg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=cPVtkphT; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id eb14-20020a0564020d0e00b004632b914eb5si8113094edb.351.2022.11.06.08.15.20 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 06 Nov 2022 08:15:20 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=cPVtkphT; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c 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 67A34385E00A for ; Sun, 6 Nov 2022 16:15:19 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 67A34385E00A DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1667751319; bh=5e/RYt1uMG+KDgPN1jYlFakKuvb3AbcrrlgqVM3eMzw=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=cPVtkphTgeJd4CT1pydYZKBUufxfpQygedy6k3gIxk+9TPB9dFEAChmSlxr0Necou RDrVH3lBe/Iun/7WhUCZqmp5pejXYR6xGj3yJERwEZe6QOeaYm7sIMFQhPL61dEc7D uNrC+zE+TrBoJ2zQqzzqXGff+we435bTr8hu6dxM= 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.129.124]) by sourceware.org (Postfix) with ESMTPS id A5278385AC1F for ; Sun, 6 Nov 2022 16:14:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A5278385AC1F Received: from mimecast-mx02.redhat.com (mx3-rdu2.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-625-tDBU4uyqNnCKWJHAb4qYMw-1; Sun, 06 Nov 2022 11:14:30 -0500 X-MC-Unique: tDBU4uyqNnCKWJHAb4qYMw-1 Received: from smtp.corp.redhat.com (int-mx10.intmail.prod.int.rdu2.redhat.com [10.11.54.10]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id C921A3803921; Sun, 6 Nov 2022 16:14:29 +0000 (UTC) Received: from abulafia.quesejoda.com (unknown [10.39.192.2]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 72BCB492B0B; Sun, 6 Nov 2022 16:14:29 +0000 (UTC) Received: from abulafia.quesejoda.com (localhost [127.0.0.1]) by abulafia.quesejoda.com (8.17.1/8.17.1) with ESMTPS id 2A6GEQ4V522617 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Sun, 6 Nov 2022 17:14:27 +0100 Received: (from aldyh@localhost) by abulafia.quesejoda.com (8.17.1/8.17.1/Submit) id 2A6GEQHY522616; Sun, 6 Nov 2022 17:14:26 +0100 To: GCC patches Subject: [PATCH] Use bit-CCP in range-ops. Date: Sun, 6 Nov 2022 17:14:20 +0100 Message-Id: <20221106161420.522485-1-aldyh@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.10 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, 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: Aldy Hernandez via Gcc-patches From: Aldy Hernandez Reply-To: Aldy Hernandez Cc: 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?1748764009227101048?= X-GMAIL-MSGID: =?utf-8?q?1748764009227101048?= After Jakub and Richi's suggestion of using the same representation for tracking known bits as we do in CCP, I took a peek at the code and realized there's a plethora of bit-tracking code there that we could be sharing with range-ops. For example, the multiplication optimizations are way better than what I had cobbled together. For that matter, our maybe nonzero tracking as a whole has a lot of room for improvement. Being the lazy ass that I am, I think we should just use one code base (CCP's). This patch provides a thin wrapper for converting the irange maybe nonzero bits to what CCP requires, and uses that to call into bit_value_binop(). I have so far converted the MULT_EXPR range-op entry to use it, as the DIV_EXPR entry we have gets a case CCP doesn't get so I'd like to contribute the enhancement to CCP before converting over. I'd like to use this approach with the dozen or so tree_code's that are handled in CCP, thus saving us from having to implement any of them :). Early next season I'd like to change irange's internal representation to a pair of value / mask, and start tracking all known bits. This ties in nicely with our plan for tracking known set bits. Perhaps if the stars align, we could merge the bit twiddling in CCP into range-ops and have a central repository for it. That is, once we make the switch to wide-ints, and assuming there are no performance issues. Note that range-ops is our lowest level abstraction. i.e. it's just the math, there's no GORI or ranger, or even the concept of a symbolic or SSA. I'd love to hear comments and ideas, and if no one objects push this. Please let me know if I missed anything. Tested on x86-64 Linux. gcc/ChangeLog: * range-op.cc (irange_to_masked_value): New. (update_known_bitmask): New. (operator_mult::fold_range): Call update_known_bitmask. --- gcc/range-op.cc | 63 +++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 50 insertions(+), 13 deletions(-) diff --git a/gcc/range-op.cc b/gcc/range-op.cc index 25c004d8287..6d9914d8d12 100644 --- a/gcc/range-op.cc +++ b/gcc/range-op.cc @@ -46,6 +46,54 @@ along with GCC; see the file COPYING3. If not see #include "wide-int.h" #include "value-relation.h" #include "range-op.h" +#include "tree-ssa-ccp.h" + +// Convert irange bitmasks into a VALUE MASK pair suitable for calling CCP. + +static void +irange_to_masked_value (const irange &r, widest_int &value, widest_int &mask) +{ + if (r.singleton_p ()) + { + mask = 0; + value = widest_int::from (r.lower_bound (), TYPE_SIGN (r.type ())); + } + else + { + mask = widest_int::from (r.get_nonzero_bits (), TYPE_SIGN (r.type ())); + value = 0; + } +} + +// Update the known bitmasks in R when applying the operation CODE to +// LH and RH. + +static void +update_known_bitmask (irange &r, tree_code code, + const irange &lh, const irange &rh) +{ + if (r.undefined_p ()) + return; + + widest_int value, mask, lh_mask, rh_mask, lh_value, rh_value; + tree type = r.type (); + signop sign = TYPE_SIGN (type); + int prec = TYPE_PRECISION (type); + signop lh_sign = TYPE_SIGN (lh.type ()); + signop rh_sign = TYPE_SIGN (rh.type ()); + int lh_prec = TYPE_PRECISION (lh.type ()); + int rh_prec = TYPE_PRECISION (rh.type ()); + + irange_to_masked_value (lh, lh_value, lh_mask); + irange_to_masked_value (rh, rh_value, rh_mask); + bit_value_binop (code, sign, prec, &value, &mask, + lh_sign, lh_prec, lh_value, lh_mask, + rh_sign, rh_prec, rh_value, rh_mask); + + int_range<2> tmp (type); + tmp.set_nonzero_bits (value | mask); + r.intersect (tmp); +} // Return the upper limit for a type. @@ -1774,21 +1822,10 @@ operator_mult::fold_range (irange &r, tree type, if (!cross_product_operator::fold_range (r, type, lh, rh, trio)) return false; - if (lh.undefined_p ()) + if (lh.undefined_p () || rh.undefined_p ()) return true; - tree t; - if (rh.singleton_p (&t)) - { - wide_int w = wi::to_wide (t); - int shift = wi::exact_log2 (w); - if (shift != -1) - { - wide_int nz = lh.get_nonzero_bits (); - nz = wi::lshift (nz, shift); - r.set_nonzero_bits (nz); - } - } + update_known_bitmask (r, MULT_EXPR, lh, rh); return true; }