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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 4D5443959E42 for ; Tue, 8 Jun 2021 14:31:53 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4D5443959E42 Received: from mail-qt1-f198.google.com (mail-qt1-f198.google.com [209.85.160.198]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-169-AmYeKqWONFGWcF2zXnkhMQ-1; Tue, 08 Jun 2021 10:31:52 -0400 X-MC-Unique: AmYeKqWONFGWcF2zXnkhMQ-1 Received: by mail-qt1-f198.google.com with SMTP id f17-20020ac87f110000b02901e117339ea7so9464244qtk.16 for ; Tue, 08 Jun 2021 07:31:52 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=4YGSihR8SdfqGOXP0CLm6+sReBpTbztpAkGse/j4BUs=; b=W+Zep8btY579WFHWrY+CfNjpnYh6DbFcOK50vmYL87/+lbitl35IV3Mg/3w/U3zQsk N9jZhh8DqNtEoO1PLjeKGeTKWcBV7ahYeLLGi6O4smPGbpA9NppXxrueycBN7s1siWDI 7TWfzmSMllIYhgDfDpPg8Ii9BzwrdWy/8WWDU695qloF0mPB8qqs2dXJqx6NsUJr2kB0 PxREIedc/HucRIYZEkqo04kbgnfMNL5WQhI6yTPeXKMptvOi+6b81It5ywAgWte7BKyn 2HqglseKUglPk/9hVppEJamwj5LdSomNYEfXJ4HkbLSfm17hmfacoQdNu+m/0+tnYGCn VSXA== X-Gm-Message-State: AOAM531+qj7dlRitIIqhQFhHaU2eD2tBDxRd7GimANwd11JcO1D5/8I8 JrfRBqafaieleQKb6StRNcx9df0PbZ6VUDl/BMrU5MCG6wJWge65KQQENDgzGQVl5REWFIEPhIU D/KU4Sp0ASWhnwWprg1h9ikHIXayu3tbwJM2gUCpwlEn7K7A2swWiPP4zSozsP/fytCWa0Q== X-Received: by 2002:a0c:9ccc:: with SMTP id j12mr325162qvf.30.1623162711156; Tue, 08 Jun 2021 07:31:51 -0700 (PDT) X-Google-Smtp-Source: ABdhPJzq8ddnDYiELTJgS0jr0RwL3IfIl6nZLIEjbtm7lsvvDypgZgzNKvUpx4uhdu7aAOSvG2op1Q== X-Received: by 2002:a0c:9ccc:: with SMTP id j12mr325094qvf.30.1623162710537; Tue, 08 Jun 2021 07:31:50 -0700 (PDT) Received: from ?IPv6:2607:fea8:a25d:e700::1b2a? ([2607:fea8:a25d:e700::1b2a]) by smtp.gmail.com with ESMTPSA id a12sm846282qtw.15.2021.06.08.07.31.49 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 08 Jun 2021 07:31:50 -0700 (PDT) Subject: Re: [PATCH] Implement a context aware points-to analyzer for use in evrp. To: Richard Biener Cc: Aldy Hernandez , GCC patches References: <20210607101003.615929-1-aldyh@redhat.com> <981fd233-3815-5e12-bb34-69fcd4fbadf9@redhat.com> From: Andrew MacLeod Message-ID: <88ad3315-aa75-ca31-93f3-975c72ab5d6f@redhat.com> Date: Tue, 8 Jun 2021 10:31:48 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.10.0 MIME-Version: 1.0 In-Reply-To: X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-CA X-Spam-Status: No, score=-5.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, 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: , X-List-Received-Date: Tue, 08 Jun 2021 14:31:55 -0000 On 6/8/21 3:26 AM, Richard Biener wrote: > On Mon, Jun 7, 2021 at 9:20 PM Andrew MacLeod wrote: >> >> I don't think this is actually doing the propagation though... It tracks >> that a_2 currently points to &foo.. and returns that to either >> simplifier or folder thru value_of_expr(). Presumably it is up to them >> to determine whether the tree expression passed back is safe to >> propagate. Is there any attempt in EVRP to NOT set the range of >> something to [&foo, &foo] under some conditions? This is what the >> change amounts to. Ranger would just return a range of [1, +INF], and >> value_of_expr would therefore return NULL. This allows value_of to >> return &foo in these conditions. Aldy, did you see any other checks in >> the vr-values code? >> >> Things like if (var1_2 == var2_3) deal with just ssa-names and will be >> handled by an ssa_name relation oracle. It just treats equivalencies >> like a a slightly special kind of relation. Im just about to bring that >> forward this week. > Ah, great - I'm looking forward to this. Currently both DOM and VN The initial code will be a bit basic, but it can be educated as we go along :-) Its currently tied into ranger just because as ranger processes statements it registers any relations it sees.. the oracle organizes these and can answer questions on anything it has seen. It is otherwise independent of ranger. It is dominance based, and there is no reason relations cant be queried and registered by any pass doing a DOM walk without ranger.  It benefits from ranger in that sometime relations are refined when we know ranges  (ie for unsigned math)     a_2 = b_4 + 6 if we know the range of b_4 will not cause an overflow, then we could set a_2 > b_4.. otherwise we cant..  Wiring it with ranger also removes the dependency on a DOM walk as ranger sorts the ordering out as needed. It is driven by data provided by range-ops and is more of a data propagation/lookup mechanism than anything. There are a number of cases we don't currently register relations simply because we have not flushed out the various tree code instructions.   We'll get to those eventually. I expect a number of the PRs will eventually be fixed primarily by adding code to range-ops . It also only does first order relations so far...  I'll get to transitives and other things as well. > do a very simplistic thing when trying to simplify downstream conditions > based on earlier ones, abusing their known-expressions hash tables > by, for example, registering (a < b) == 1, (a > b) == 0, (a == b) == 0, > (a != b) == 1 for an earlier a < b condition on the true edge. So I wonder > if this relation code can be somehow used there. In VN there's the > extra complication that it iterates, but DOM is just a DOM-walk and > the VN code also has a non-iterating mode (but not a DOM walk). I don't think the iteration is an issue,  ranger iterates to some degree as well, and some statement are registered multiple times. I believe it intersects with any known relation, so if an iteration causes a relation to become "better" it should be updated. The API is for registering is pretty straightforward:   void register_relation (gimple *stmt, relation_kind k, tree op1, tree op2);   void register_relation (edge e, relation_kind k, tree op1, tree op2); so all you'd have to do when a < b is encountered is to register  (a LT_EXPR b) on the true edge, and (a GE_EXPR b) on the false edge.  Then any queries downstream should be reflected. > Of course the code is also used to simplify > > if (a > b) > c = a != b; > > but the relation oracle should be able to handle that as well I guess. > yeah, so a GT_EXPR B is registered on the true edge.  Then when processing c = a != b,  you can determine that a NE_EXPR b intersected with a GT_EXPR b result in  a GT_EXPR b... which folds to a 1. This is all also available with the range-op API additions such that you can simply call : rangerop->fold_range (stmt(c = a != b), range_of_a, range_of_b, GT_EXPR (relation of a to b)  and the range returned will be [1,1]. The actual ranges in this case are irrelevant, but arent for some other kinds of stmts. Likewise, simply asking ranger for the range of c will likewise return [1,1], the relation processing is all integrated behind the scenes in ranger.. As we start using the code more, we may find we want/need a few more wrappers around some of this so that you can transparently ask what the RHS folds to without any ranger present, just with relations.  Those'll be fairly trivial to add... The relation oracle is going to be directly accessible from the get_range_query(cfun) range_query class.  I'll do a big writeup when i submit it and we should be able to make it usable in any of those places. Andrew