From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 121477 invoked by alias); 31 May 2019 20:27:06 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 121469 invoked by uid 89); 31 May 2019 20:27:06 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-3.1 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS autolearn=ham version=3.3.1 spammy=frequently, H*i:sk:a4de104, H*f:sk:a4de104 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 31 May 2019 20:27:04 +0000 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id CCB0C30832CE; Fri, 31 May 2019 20:26:57 +0000 (UTC) Received: from [10.10.124.16] (ovpn-124-16.rdu2.redhat.com [10.10.124.16]) by smtp.corp.redhat.com (Postfix) with ESMTP id 84BED1000322; Fri, 31 May 2019 20:26:55 +0000 (UTC) Subject: Re: On-Demand range technology [2/5] - Major Components : How it works To: Jeff Law , Richard Biener Cc: GCC , Aldy Hernandez References: <908dbc60-b7b9-c609-f999-cc7264af0c6e@redhat.com> <91bfd08e-1431-d8ba-f9b5-e8822aaf62e2@redhat.com> From: Andrew MacLeod Message-ID: <507e5167-2e56-7559-fc63-526e1fe4130a@redhat.com> Date: Fri, 31 May 2019 20:27:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.3.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit X-IsSubscribed: yes X-SW-Source: 2019-05/txt/msg00284.txt.bz2 On 5/31/19 2:16 PM, Jeff Law wrote: > On 5/31/19 9:40 AM, Andrew MacLeod wrote: >> On 5/29/19 7:15 AM, Richard Biener wrote: >>> On Tue, May 28, 2019 at 4:17 PM Andrew MacLeod >>> wrote: >>>> On 5/27/19 9:02 AM, Richard Biener wrote: >>>>> On Fri, May 24, 2019 at 5:50 PM Andrew MacLeod >>>>> wrote: >>>>>>> The above suggests that iff this is done at all it is not in GORI >>>>>>> because >>>>>>> those are not conditional stmts or ranges from feeding those.  The >>>>>>> machinery doing the use-def walking from stmt context also cannot >>>>>>> come along these so I have the suspicion that Ranger cannot handle >>>>>>> telling us that for the stmt following above, for example >>>>>>> >>>>>>>     if (_5 != 0) >>>>>>> >>>>>>> that _5 is not zero? >>>>>>> >>>>>>> Can you clarify? >>>>>> So there are 2 aspects to this.    the range-ops code for DIV_EXPR, if >>>>>> asked for the range of op2 () would return ~[0,0] for _5. >>>>>> But you are also correct in that the walk backwards would not find >>>>>> this. >>>>>> >>>>>> This is similar functionality to how null_derefs are currently >>>>>> handled, >>>>>> and in fact could probably be done simultaneously using the same code >>>>>> base.   I didn't bring null derefs up, but this is a good time :-) >>>>>> >>>>>> There is a separate class used by the gori-cache which tracks the >>>>>> non-nullness property at the block level.    It has a single API: >>>>>> non_null_deref_p (name, bb)    which determines whether the is a >>>>>> dereference in any BB for NAME, which indicates whether the range >>>>>> has an >>>>>> implicit ~[0,0] range in that basic block or not. >>>>> So when we then have >>>>> >>>>>    _1 = *_2; // after this _2 is non-NULL >>>>>    _3 = _1 + 1; // _3 is non-NULL >>>>>    _4 = *_3; >>>>> ... >>>>> >>>>> when a on-demand user asks whether _3 is non-NULL at the >>>>> point of _4 = *_3 we don't have this information?  Since the >>>>> per-BB caching will only say _1 is non-NULL after the BB. >>>>> I'm also not sure whether _3 ever gets non-NULL during >>>>> non-NULL processing of the block since walking immediate uses >>>>> doesn't really help here? >>>> presumably _3 is globally non-null due to the definition being (pointer >>>> + x)  ... ie, _3 has a global range o f ~[0,0] ? >>> No, _3 is ~[0, 0] because it is derived from _1 which is ~[0, 0] and >>> you cannot arrive at NULL by pointer arithmetic from a non-NULL pointer. >> I'm confused. >> >> _1 was loaded from _2 (thus asserting _2 is non-NULL).  but we have no >> idea what the range of _1 is, so  how do you assert _1 is [~0,0] ? >> The only way I see to determine _3 is non-NULL  is through the _4 = *_3 >> statement. > Likewise. I don't see how we get ~[0,0] for _1, except at the point > after the dereference of _3. > > >>>>> So this seems to be a fundamental limitation [to the caching scheme], >>>>> not sure if it is bad in practice. >>>>> >>>>> Or am I missing something? >>>>> >>>> Not missing anything  The non-nullness property is maintains globally at >>>> the basic block level.  both _1 and _3 are flagged as being non-null in >>>> the block.  Upon exit, its a bit check.   If the global information does >>>> not have the non-nullness property, then when a request is made for >>>> non-nullness  and the def and the use are both within the same block, >>>> and its flagged as being non-null in that block, then the request is >>>> forced back to a quick walk between the def and the use to see if there >>>> is any non-nulless introduced in between.   Yes, that makes it a linear >>>> walk, but its infrequent, and often short.  to the best of our knowledge >>>> at this point anyway :-) >>> So with the clarification above do we ever see that _3 is non-NULL? >>> I suppose the worker processing _3 = _1 + 1 would ask for >>> _1 non-nullness but we do not record any non-NULL-ness of _1 in >>> this basic-block (but only at its end).  Consider stmts >>> >>>   _4 = (uintptr_t) _2; >>>   _5 = _6 / _4; >>>   _1 = *_2; >>> ... >>> >>> here at _1 we know _2 is not NULL.  But if we ask for non-NULLness >>> of _2 at the definition of _4 we may not compute ~[0, 0] and thus >>> conclude that _6 / _4 does not trap. >> EVRP must look backwards to figure this out since the forward walk will >> process _5 = _6 / _4 before it sees the dereference to _2... so how does >> it know that _4 is non-zero without looking backwards at things after it >> sees the dereference??  Does it actually do this? > During the forward walk we process the assignment to _5, which is _6 / > _4. We can infer that _4 is nonzero because division by zero is > undefined behavior. But I'm not sure how EVRP would go back and then > make a determination about _4 unless it's doing so via an equivalence. > > > >>> stmt-level tracking of ranges are sometimes important.  This is >>> something the machinery cannot provide - correct?  At least not >>> optimistically enough with ranges derived about uses. >> Maybe I'm the one missing something, but in the absence of statement >> level exception throwing via 'can_throw_non_call_exceptions' being true, >> any assertion made anywhere in the block to an ssa_name applies to the >> entire block does it not?   ie it doesn't matter if the deference >> happens first thing in the block or last thing, its not going to change >> its value within the block.. its going to be non-null throughout the >> entire block. > No, I don't think it can hold for the entire block. > > Consider > > x = p ? 10 : 20; > foo (x) > *p = whatever > > We don't know p is non-null because foo might not return. If by way of > the dereference we were to assert p is non-null for the entire block, > then we'd pass the wrong value to foo(). > > Jeff > Interesting.  I started wondering about calls when I was talking about non-call exceptions, but couldn't think of an example off the top of my head. OK, so the statement holds true for any section of code without calls in it.  If the block is marked as having a non-null deref in it, I need to look at statement in between the relevant def and use to see if there is an impact rather than just checking the flag.  If the flag is false, we need to do nothing else. I don't think any example above affects this. if we adjust the first example to be _1 = *_2; // after this _2 is non-NULL    _3 = _2 + 1; // _3 is non-NULL    _4 = *_3; then  when we are stepping back and evaluating   _3 = _2 + 1,  if _2 has a range of varying, and the "non-null_in_block" flag is set, it would have to trigger a walk up the block looking to see if we find a *_2. The walk terminates when we see   a)  a call, resulting in  _2 = varying   b) the start of the block, resulting in _2 = varying  or   c) *_2  resulting in _2 = ~[0,0] now, this only triggers when there is *both* a dereference and a 'normal' use in the same block.  If both conditions aren't met, then no walk is required. There may also be a better approach, but  Id wait until we measured and saw some problem with this. If it turns out to be some sort of real issue, then we could always fall back to having the engine recognize that "oh, this block has both a deref and a use, lets evaluate the entire block before answering the question".  The results are all cached, and any additional queries for that block are then already a calculated. I wonder how frequently it comes up. maybe I'll try some measurements.     Best case, we do the minimum like we do today, worst case, we end up evaluating everything in every block  (if every block has this situation).   But we'd be doing that without the on-demand approach anyway, so it'd just be break even in that case. Andrew