llvm dev - Jan 2018 - Late setting of SCEV NoWrap flags does bad with cache

Hi,

I think these two patches are related to the topic:

https://reviews.llvm.org/D41578 “[SCEV] Do not cache S -> V if S is not
equivalent of V”

  *   It’s committed. It can cause generation of redundant instructions. We’ve
got regressions due to it. The biggest one is 7.31% regression in Spec2k6
401.bzip2 on Cortex-A57(AArch64).

https://reviews.llvm.org/D42290 “[SCEV] Clear poison flags during expansion of
SCEV”

  *   This patch tries to fix regressions due to the D41578 patch.

Thanks,
Evgeny Astigeevich

From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Maxim
Kazantsev via llvm-dev <llvm-dev at lists.llvm.org>
Reply-To: Maxim Kazantsev <max.kazantsev at azul.com>
Date: Thursday, 25 January 2018 at 06:03
To: "llvm-dev at lists.llvm.org" <llvm-dev at lists.llvm.org>
Subject: [llvm-dev] Late setting of SCEV NoWrap flags does bad with cache

Hello Everyone,

I want to raise a discussion about reasonability of late setting of nsw/nuw/nw
flags to SCEV AddRecs through setNoWrapFlags method. A discussion about this
have already happened in August last year, there was a concern about different
no-wrap flags that come from different sequences of SCEV flags invocations. It
was mentioned there that late setting of flags is actually a hack to save some
compile time.

Recently I've stumbled over a different problem related to this late flag
setting. The problem is that current SCEV implementation caches a lot of data
about SCEVs. In particular, information about ranges and loop backedge taken
counts. A side effect of that is that if we had an AddRec like {1,+,1} and
cached its range as [MIN_INT, MAX_INT+1), and then later found out that this
recurrency provably has <nsw>, its cached range doesn't get updated.
As well as ranges of all other SCEVs that depend on that. As result, we have a
very weird behavior of SCEV that is unable to prove that
sext({1,+,1}<nsw>) is a positive value just because it has outdated cached
ranges.

In fact, I don't see any point in having <nsw>/<nuw> for AddRecs
if they are not used to prove useful facts about these recs (such as
non-negativeness or positiveness). We will only be able to do it if we
accidentally call forgetMemoizedResults for all SCEV that depend on that AddRec
(which is very unlikely to ever happen in practice). I tried to clean up cache
selectively, but in fact it takes full traversal through all cached SCEVs at
least to identify the ones that depend on the updated AddRec, and this
completely ruins the idea of saving compile time.

You may find the example of such behavior if you re-enable the assertion from
patch https://reviews.llvm.org/rL323309 . The test that was added with this
patch fails on this assert with exactly this problem.

My question is: do we still want to have this hack with late setting of nsw/nuw
given that this flag does not give us any benefits in many real situations? What
would you think?

Best regards,
Max

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180125/fb53d2b5/attachment.html>

Hi Evgeny,

Thanks for reaching out! These patches related to expander are not specifically
about what I was implying. As far as I'm aware, they fix a functional
problem (and sometimes there is some inefficiency in the result of their
operation because we lack a clenup pass after). In my case, there is no
functional bug. But there is unavility of SCEV to prove some trivial fact due to
outdated memoized data.

I was talking about different caches (in fact, SCEV has a plenty of them).
Specifically, I imply maps "SignedRanges", "UnsignedRanges"
and other maps that get touched by method "forgetMemoizedResults".

Thanks,
Max

From: Evgeny Astigeevich [mailto:Evgeny.Astigeevich at arm.com]
Sent: Thursday, January 25, 2018 6:31 PM
To: llvm-dev at lists.llvm.org
Cc: nd <nd at arm.com>; Maxim Kazantsev <max.kazantsev at azul.com>
Subject: Re: [llvm-dev] Late setting of SCEV NoWrap flags does bad with cache

Hi,

I think these two patches are related to the topic:

https://reviews.llvm.org/D41578 “[SCEV] Do not cache S -> V if S is not
equivalent of V”
-          It’s committed. It can cause generation of redundant instructions.
We’ve got regressions due to it. The biggest one is 7.31% regression in Spec2k6
401.bzip2 on Cortex-A57(AArch64).

https://reviews.llvm.org/D42290 “[SCEV] Clear poison flags during expansion of
SCEV”
-          This patch tries to fix regressions due to the D41578 patch.

Thanks,
Evgeny Astigeevich

From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces
at lists.llvm.org>> on behalf of Maxim Kazantsev via llvm-dev <llvm-dev
at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Reply-To: Maxim Kazantsev <max.kazantsev at azul.com<mailto:max.kazantsev
at azul.com>>
Date: Thursday, 25 January 2018 at 06:03
To: "llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>" <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Subject: [llvm-dev] Late setting of SCEV NoWrap flags does bad with cache

Hello Everyone,

I want to raise a discussion about reasonability of late setting of nsw/nuw/nw
flags to SCEV AddRecs through setNoWrapFlags method. A discussion about this
have already happened in August last year, there was a concern about different
no-wrap flags that come from different sequences of SCEV flags invocations. It
was mentioned there that late setting of flags is actually a hack to save some
compile time.

Recently I've stumbled over a different problem related to this late flag
setting. The problem is that current SCEV implementation caches a lot of data
about SCEVs. In particular, information about ranges and loop backedge taken
counts. A side effect of that is that if we had an AddRec like {1,+,1} and
cached its range as [MIN_INT, MAX_INT+1), and then later found out that this
recurrency provably has <nsw>, its cached range doesn't get updated.
As well as ranges of all other SCEVs that depend on that. As result, we have a
very weird behavior of SCEV that is unable to prove that
sext({1,+,1}<nsw>) is a positive value just because it has outdated cached
ranges.

In fact, I don't see any point in having <nsw>/<nuw> for AddRecs
if they are not used to prove useful facts about these recs (such as
non-negativeness or positiveness). We will only be able to do it if we
accidentally call forgetMemoizedResults for all SCEV that depend on that AddRec
(which is very unlikely to ever happen in practice). I tried to clean up cache
selectively, but in fact it takes full traversal through all cached SCEVs at
least to identify the ones that depend on the updated AddRec, and this
completely ruins the idea of saving compile time.

You may find the example of such behavior if you re-enable the assertion from
patch https://reviews.llvm.org/rL323309 . The test that was added with this
patch fails on this assert with exactly this problem.

My question is: do we still want to have this hack with late setting of nsw/nuw
given that this flag does not give us any benefits in many real situations? What
would you think?

Best regards,
Max

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180125/9f89babb/attachment.html>