From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 B1B253858CDA for ; Tue, 4 Oct 2022 14:30:22 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org B1B253858CDA Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1664893822; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=JN7sRlFWYn07nOMqtGukXB+bFGfW2RHvynzUVXRo4Bc=; b=gmsw8aY1tLOJJ39EHKVN9A9sNZRzepCGbjuh/NrcF5rCRy9aVGuOeKSomudSscGrwWhhdn tSOpeVGnRNlWwFUpBE/upOhci5hvDx2JvVOIjOZ4Rg2xQewSMPvSXp10X7GXJxd8maSFiG Dv5zmG6qI6+VN+XzsrAza2tfLmNRGuw= Received: from mail-oi1-f198.google.com (mail-oi1-f198.google.com [209.85.167.198]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-142-d9b5pqSQN-2iso2GT6Slyw-1; Tue, 04 Oct 2022 10:30:21 -0400 X-MC-Unique: d9b5pqSQN-2iso2GT6Slyw-1 Received: by mail-oi1-f198.google.com with SMTP id t37-20020a05680815a500b0034fdd9124d9so5280504oiw.3 for ; Tue, 04 Oct 2022 07:30:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date; bh=JN7sRlFWYn07nOMqtGukXB+bFGfW2RHvynzUVXRo4Bc=; b=DKohXjs6N6UjYF6nN65xrdTikHuUSsR3xxmjMGkuoO0F7dJowv1vSQ06FiO/mTzxmk T/fD+hsV6cj/VwQgZvnxNUltpERvrNuUXXwgJn8EEE7OIQdikZwKUFcr19rSx+fvaoKd 9jMfrg0eNlx2psEs16S4e6Hpj1nZyfpMnYT4SPRlY/MfffVa89hBKi2I85xnWHy7aCmV i/KBRFHeFt/UkUY+n5dwKpN90UOSSEvOs2JJqgSROxp6RUG0XdbiXjWmrzkLrOjZQ8Su 79SROGsC9hVseuunlJFw1d43uFvd5E62GMnUoeZxMpLDNfyGCcE+LzfGhUhZ7Pm7hbHm nexQ== X-Gm-Message-State: ACrzQf0Ocah0GG+H20D6We9hp1dWVe3u9IUHZf/zshHzZ9RWrsuHj7yj by6TlYUb8QfRgCd3eyjUhfx3PHjfkqYXFumrtC3xnWjXnqRMC4HZkhZwSvzoRu6mbxG+dm+giV+ rl2uW96AckjZQUbGPM/bvpwZQqtvrhVf7Ww== X-Received: by 2002:a05:6808:650:b0:34f:b81f:960 with SMTP id z16-20020a056808065000b0034fb81f0960mr43785oih.36.1664893820648; Tue, 04 Oct 2022 07:30:20 -0700 (PDT) X-Google-Smtp-Source: AMsMyM5QDQySIZ8oTmLAbCs82/zNu7PrDl9TrHbDFAtEp7foWDEKzr6BPkoMzaHGDKAj+hkDQf3AbkqSmaTcPY2NUZw= X-Received: by 2002:a05:6808:650:b0:34f:b81f:960 with SMTP id z16-20020a056808065000b0034fb81f0960mr43776oih.36.1664893820395; Tue, 04 Oct 2022 07:30:20 -0700 (PDT) MIME-Version: 1.0 References: <20221004073530.1461390-1-aldyh@redhat.com> <55c5aebd-6b51-982b-3dc7-73513c727f58@redhat.com> In-Reply-To: <55c5aebd-6b51-982b-3dc7-73513c727f58@redhat.com> From: Aldy Hernandez Date: Tue, 4 Oct 2022 16:30:09 +0200 Message-ID: Subject: Re: [COMMITTED] Convert nonzero mask in irange to wide_int. To: Andrew MacLeod Cc: Richard Biener , GCC patches X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-5.7 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,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 List-Id: On Tue, Oct 4, 2022 at 3:27 PM Andrew MacLeod wrote: > > > On 10/4/22 08:13, Aldy Hernandez via Gcc-patches wrote: > > On Tue, Oct 4, 2022, 13:28 Aldy Hernandez wrote: > > > >> On Tue, Oct 4, 2022 at 9:55 AM Richard Biener > >> wrote: > >>> > >>> Am 04.10.2022 um 09:36 schrieb Aldy Hernandez via Gcc-patches < > >> gcc-patches@gcc.gnu.org>: > >>>> =EF=BB=BFThe reason the nonzero mask was kept in a tree was basicall= y inertia, > >>>> as everything in irange is a tree. However, there's no need to keep > >>>> it in a tree, as the conversions to and from wide ints are very > >>>> annoying. That, plus special casing NULL masks to be -1 is prone > >>>> to error. > >>>> > >>>> I have not only rewritten all the uses to assume a wide int, but > >>>> have corrected a few places where we weren't propagating the masks, = or > >>>> rather pessimizing them to -1. This will become more important in > >>>> upcoming patches where we make better use of the masks. > >>>> > >>>> Performance testing shows a trivial improvement in VRP, as things li= ke > >>>> irange::contains_p() are tied to a tree. Ughh, can't wait for trees= in > >>>> iranges to go away. > >>> You want trailing wide int storage though. A wide_int is quite large= . > >> Absolutely, this is only for short term storage. Any time we need > >> long term storage, say global ranges in SSA_NAME_RANGE_INFO, we go > >> through vrange_storage which will stream things in a more memory > >> efficient manner. For irange, vrange_storage will stream all the > >> sub-ranges, including the nonzero bitmask which is the first entry in > >> such storage, as trailing_wide_ints. > >> > >> See irange_storage_slot to see how it lives in GC memory. > >> > > That being said, the ranger's internal cache uses iranges, albeit with = a > > squished down number of subranges (the minimum amount to represent the > > range). So each cache entry will now be bigger by the difference betwe= en > > one tree and one wide int. > > > > I wonder if we should change the cache to use vrange_storage. If not no= w, > > then when we convert all the subranges to wide ints. > > > > Of course, the memory pressure of the cache is not nearly as problemati= c as > > SSA_NAME_RANGE_INFO. The cache only stores names it cares about. > > Rangers cache can be a memory bottleneck in pathological cases.. > Certainly not as bad as it use to be, but I'm sure it can still be > problematic. Its suppose to be a memory efficient representation > because of that. The cache can have an entry for any live ssa-name > (which means all of them at some point in the IL) multiplied by a factor > involving the number of dominator blocks and outgoing edges ranges are > calculated on. So while SSA_NAME_RANGE_INFO is a linear thing, the > cache lies somewhere between a logarithmic and exponential factor based > on the CFG size. Hmmm, perhaps the ultimate goal here should be to convert the cache to use vrange_storage, which uses trailing wide ints for all of the end points plus the masks (known_ones included for the next release). > > if you are growing the common cases of 1 to 2 endpoints to more than > double in size (and most of the time not be needed), that would not be > very appealing :-P If we have any wide-ints, they would need to be a > memory efficient version. The Cache uses an irange_allocator, which is > suppose to provide a memory efficient objects.. hence why it trims the > number of ranges down to only what is needed. It seems like a trailing > wide-Int might be in order based on that.. > > Andrew > > > PS. which will be more problematic if you eventually introduce a > known_ones wide_int. I thought the mask tracking was/could be > something simple like HOST_WIDE_INT.. then you only tracks masks in > types up to the size of a HOST_WIDE_INT. then storage and masking is > all trivial without going thru a wide_int. Is that not so/possible? That's certainly easy and cheaper to do. The hard part was fixing all the places where we weren't keeping the masks up to date, and that's done (sans any bugs ;-)). Can we get consensus here on only tracking masks for type sizes less than HOST_WIDE_INT? I'd hate to do all the work only to realize we need to track 512 bit masks on a 32-bit host cross :-). Aldy