[llvm-dev] Late setting of SCEV NoWrap flags does bad with cache

[Maxim Kazantsev via llvm-dev]

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>