llvm dev - Aug 2017 - [ScalarEvolution][SCEV] no-wrap flags dependent on order of getSCEV() calls

Hi Geoff,

On Wed, Aug 9, 2017 at 8:58 AM, Geoff Berry <gberry at codeaurora.org>
wrote:
> On 8/8/2017 8:38 PM, Sanjoy Das wrote:
>>
>> Hi,
>>
>> On Tue, Aug 8, 2017 at 12:58 PM, Friedman, Eli <efriedma at
codeaurora.org>
>> wrote:
>>>
>>> Oh, I see... yes, we do stupid things involving mutating NoWrap
flags
>>> after
>>> a SCEV is created.  (grep for setNoWrapFlags in
ScalarEvolution.cpp.)
>>
>>
>> That's really a compile time hack -- we defer some expensive tricks
to
>> prove nsw/nuw on an add recurrences to when we've been asked to
>> sign/zero extend said add recurrence.
>
>
> If that is the case, preserving SCEV analysis where we didn't before
should
> only
> result in later passes seeing more nsw/nuw flags, which should
theoretically
> be
> beneficial?
There are downsides to preserving SCEV for "too long" though -- if you
simplified a loop in a way that SCEV can compute its trip count when
it couldn't before (or it could compute a trip count before, but now
it can compute a more precise trip count) then invalidating the cache
can be an improvement.  However, in this case judicious use of
forgetLoop() (as opposed to re-constructing the whole of SCEV) will
also do the job.

-- Sanjoy
>> I would be okay if you wanted to expose those tricks via a helper in
>> SCEV that could be called independently of creating zero or sign
>> extensions.  That way SCEV clients could trade-off compile time for>
more
>> precise information in a granular way.
>
>
> I'm not concerned with getting better SCEV results at the moment, I
just
> want to
> make sure that changing these passes to preserve SCEV analysis is behaving
> as
> expected (which it sounds like it is).
>
>>
>> -- Sanjoy
>>
>>>
>>> -Eli
>>>
>>> --
>>> Employee of Qualcomm Innovation Center, Inc.
>>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
a
>>> Linux
>>> Foundation Collaborative Project
>>>
>
> --
> Geoff Berry
> Employee of Qualcomm Datacenter Technologies, Inc.
>  Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm
> Technologies, Inc.  Qualcomm Technologies, Inc. is a member of the Code
> Aurora Forum, a Linux Foundation Collaborative Project.

Hi Sanjoy,

[adding Adam since I believe he added the original FIXME to preserve SCEV
in LoopDataPrefetch]

On 8/14/2017 1:36 AM, Sanjoy Das wrote:
> Hi Geoff,
> 
> On Wed, Aug 9, 2017 at 8:58 AM, Geoff Berry <gberry at
codeaurora.org> wrote:
>> On 8/8/2017 8:38 PM, Sanjoy Das wrote:
>>>
>>> Hi,
>>>
>>> On Tue, Aug 8, 2017 at 12:58 PM, Friedman, Eli <efriedma at
codeaurora.org>
>>> wrote:
>>>>
>>>> Oh, I see... yes, we do stupid things involving mutating NoWrap
flags
>>>> after
>>>> a SCEV is created.  (grep for setNoWrapFlags in
ScalarEvolution.cpp.)
>>>
>>>
>>> That's really a compile time hack -- we defer some expensive
tricks to
>>> prove nsw/nuw on an add recurrences to when we've been asked to
>>> sign/zero extend said add recurrence.
>>
>>
>> If that is the case, preserving SCEV analysis where we didn't
before should
>> only
>> result in later passes seeing more nsw/nuw flags, which should
theoretically
>> be
>> beneficial?
> 
> There are downsides to preserving SCEV for "too long" though --
if you
> simplified a loop in a way that SCEV can compute its trip count when
> it couldn't before (or it could compute a trip count before, but now
> it can compute a more precise trip count) then invalidating the cache
> can be an improvement.  However, in this case judicious use of
> forgetLoop() (as opposed to re-constructing the whole of SCEV) will
> also do the job.
In this particular case, neither of the passes that I'm marking as newly
preserving SCEV modify any loop structure or any instructions that should
impact any of the existing SCEV values.  All they do is add prefetch
instructions (and some new instructions to compute the addresses to
prefetch) and annotate some load instructions with metadata.  That's why
I was surprised to see changes in generated code from marking them as
preserving SCEV.

I've done some performance testing and didn't see any significant
changes
in performance due to these minor SCEV changes, so I think I'm going to
post a patch to enable SCEV preservation in these passes and move on.
  
> -- Sanjoy
> 
>>> I would be okay if you wanted to expose those tricks via a helper
in
>>> SCEV that could be called independently of creating zero or sign
>>> extensions.  That way SCEV clients could trade-off compile time
for> more
>>> precise information in a granular way.
>>
>>
>> I'm not concerned with getting better SCEV results at the moment, I
just
>> want to
>> make sure that changing these passes to preserve SCEV analysis is
behaving
>> as
>> expected (which it sounds like it is).
>>
>>>
>>> -- Sanjoy
>>>
>>>>
>>>> -Eli
>>>>
>>>> --
>>>> Employee of Qualcomm Innovation Center, Inc.
>>>> Qualcomm Innovation Center, Inc. is a member of Code Aurora
Forum, a
>>>> Linux
>>>> Foundation Collaborative Project
>>>>
>>
>> --
>> Geoff Berry
>> Employee of Qualcomm Datacenter Technologies, Inc.
>>   Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm
>> Technologies, Inc.  Qualcomm Technologies, Inc. is a member of the Code
>> Aurora Forum, a Linux Foundation Collaborative Project.
-- 
Geoff Berry
Employee of Qualcomm Datacenter Technologies, Inc.
  Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm
Technologies, Inc.  Qualcomm Technologies, Inc. is a member of the Code Aurora
Forum, a Linux Foundation Collaborative Project.

> On Aug 14, 2017, at 7:35 AM, Geoff Berry <gberry at codeaurora.org>
wrote:
> 
> Hi Sanjoy,
> 
> [adding Adam since I believe he added the original FIXME to preserve SCEV
> in LoopDataPrefetch]
For record, that wasn’t me.  It was there from the beginning when Hal added the
PPC-specific pass.

Adam
> 
> On 8/14/2017 1:36 AM, Sanjoy Das wrote:
>> Hi Geoff,
>> On Wed, Aug 9, 2017 at 8:58 AM, Geoff Berry <gberry at
codeaurora.org> wrote:
>>> On 8/8/2017 8:38 PM, Sanjoy Das wrote:
>>>> 
>>>> Hi,
>>>> 
>>>> On Tue, Aug 8, 2017 at 12:58 PM, Friedman, Eli <efriedma at
codeaurora.org>
>>>> wrote:
>>>>> 
>>>>> Oh, I see... yes, we do stupid things involving mutating
NoWrap flags
>>>>> after
>>>>> a SCEV is created.  (grep for setNoWrapFlags in
ScalarEvolution.cpp.)
>>>> 
>>>> 
>>>> That's really a compile time hack -- we defer some
expensive tricks to
>>>> prove nsw/nuw on an add recurrences to when we've been
asked to
>>>> sign/zero extend said add recurrence.
>>> 
>>> 
>>> If that is the case, preserving SCEV analysis where we didn't
before should
>>> only
>>> result in later passes seeing more nsw/nuw flags, which should
theoretically
>>> be
>>> beneficial?
>> There are downsides to preserving SCEV for "too long" though
-- if you
>> simplified a loop in a way that SCEV can compute its trip count when
>> it couldn't before (or it could compute a trip count before, but
now
>> it can compute a more precise trip count) then invalidating the cache
>> can be an improvement.  However, in this case judicious use of
>> forgetLoop() (as opposed to re-constructing the whole of SCEV) will
>> also do the job.
> 
> In this particular case, neither of the passes that I'm marking as
newly
> preserving SCEV modify any loop structure or any instructions that should
> impact any of the existing SCEV values.  All they do is add prefetch
> instructions (and some new instructions to compute the addresses to
> prefetch) and annotate some load instructions with metadata.  That's
why
> I was surprised to see changes in generated code from marking them as
> preserving SCEV.
> 
> I've done some performance testing and didn't see any significant
changes
> in performance due to these minor SCEV changes, so I think I'm going to
> post a patch to enable SCEV preservation in these passes and move on.
> 
>> -- Sanjoy
>>>> I would be okay if you wanted to expose those tricks via a
helper in
>>>> SCEV that could be called independently of creating zero or
sign
>>>> extensions.  That way SCEV clients could trade-off compile time
for> more
>>>> precise information in a granular way.
>>> 
>>> 
>>> I'm not concerned with getting better SCEV results at the
moment, I just
>>> want to
>>> make sure that changing these passes to preserve SCEV analysis is
behaving
>>> as
>>> expected (which it sounds like it is).
>>> 
>>>> 
>>>> -- Sanjoy
>>>> 
>>>>> 
>>>>> -Eli
>>>>> 
>>>>> --
>>>>> Employee of Qualcomm Innovation Center, Inc.
>>>>> Qualcomm Innovation Center, Inc. is a member of Code Aurora
Forum, a
>>>>> Linux
>>>>> Foundation Collaborative Project
>>>>> 
>>> 
>>> --
>>> Geoff Berry
>>> Employee of Qualcomm Datacenter Technologies, Inc.
>>>  Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm
>>> Technologies, Inc.  Qualcomm Technologies, Inc. is a member of the
Code
>>> Aurora Forum, a Linux Foundation Collaborative Project.
> 
> -- 
> Geoff Berry
> Employee of Qualcomm Datacenter Technologies, Inc.
> Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm
Technologies, Inc.  Qualcomm Technologies, Inc. is a member of the Code Aurora
Forum, a Linux Foundation Collaborative Project.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170814/51c582a5/attachment.html>