search for: scev

...ome bugs to play with, and I started with http://llvm.org/bugs/show_bug.cgi?id=18606 As I commented there, a loop is unrolled and exhibit this pattern: %mul.1 = mul i32 %mul, %mul %mul.2 = mul i32 %mul.1, %mul.1 .... With an unroll factor of 32, the last multiply has 2^32 terms in its SCEV expression. (I mean I expect it would have those terms if I was patient enough to wait for opt to finish :) ) So I suppose SCEV is lacking some protection, for instance degrading to "unknow" when an expression is above a given threshold, or stop flattening and keeping only a reference...

...i?id=18606 >> >> As I commented there, a loop is unrolled and exhibit this pattern: >> >> %mul.1 = mul i32 %mul, %mul >> %mul.2 = mul i32 %mul.1, %mul.1 >> .... >> >> With an unroll factor of 32, the last multiply has 2^32 terms in its >> SCEV expression. >> (I mean I expect it would have those terms if I was patient enough to >> wait for opt to finish :) ) >> >> So I suppose SCEV is lacking some protection, for instance degrading >> to "unknow" when an expression is above a given threshold, or s...

...is about a project I've been prototyping on-and-off for a while that has finally reached a point where I can claim it to be "potentially viable". I'd like to gather some input from the community before moving too far ahead. # The problem There is a representation issue within SCEV that prevents it from fully using information from nsw/nuw flags present in the IR. This isn't just a theoretical issue, e.g. today LLVM won't unroll this loop: void f(int x, long* arr) { for (int i = x + 1; i < x + 3; i++) arr[i] = 40; } since SCEV is unable to exploit the no-o...

...lt;dberlin at dberlin.org> >> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>, "David Li" <davidxl at google.com> >> Sent: Wednesday, August 24, 2016 5:41:12 PM >> Subject: Re: [llvm-dev] Request suggestions about how to remove redundencies caused by SCEV expansion fundementally >> >> On Wed, Aug 24, 2016 at 3:07 PM, Daniel Berlin <dberlin at dberlin.org> >> wrote: >> > >> > >> > On Fri, Aug 19, 2016 at 3:57 PM, Wei Mi via llvm-dev >> > <llvm-dev at lists.llvm.org> wrote: >> &gt...

...rew Trick <atrick at apple.com>, Dan Gohman <dan433584 at gmail.com>, Hal Finkel <hfinkel at anl.gov>, Chandler Carruth <chandlerc at gmail.com>, David Majnemer <david.majnemer at gmail.com>, Sebastian Pop <sebpop at gmail.com> Subject: [llvm-dev] Improving SCEV's behavior around IR level no-wrap flags Message-ID: <CAMiUf7fs5xDnfaChLEcft+auNoVW_LksqLA48KJnH3rNgcMftQ at mail.gmail.com> Content-Type: text/plain; charset=UTF-8 Hi all, This is about a project I've been prototyping on-and-off for a while that has finally reached a point where...

...here was pushback on this proposal so I did not proceed further. > Are you blocked on this? > > [+CC Andy, who I remember had some objections.] > > — Sanjoy Off the top of my head, my concern is that expression comparison is no longer constant time, which I think is fundamental to SCEV. I may be able to dig through my notes next week, after vacation... -Andy > On Tue, Aug 8, 2017 at 3:06 PM, Chawla, Pankaj <pankaj.chawla at intel.com> wrote: >> Hi Sanjoy, >> >> Any update on this? >> Are there plans to implement this proposal? >> >&g...

...t;> I'm looking into resolving a FIXME in the LoopDataPrefetch (and FalkorMarkStridedAccesses) pass by marking both of these passes as preserving the ScalarEvolution analysis. Unfortunately, when this change is made, LSR will generate different code. One of the root causes seems to be that SCEV will return different nsw/nuw flags for the same Value, depending on what order the SCEVs are computed, due to the fact that the SCEV object unique-ing doesn't take the nsw/nuw flags into account. Since LoopDataPrefetch computes SCEVs in a different order than LSR, the nsw/nuw flags seen by LS...

..., I'm looking into resolving a FIXME in the LoopDataPrefetch (and FalkorMarkStridedAccesses) pass by marking both of these passes as preserving the ScalarEvolution analysis. Unfortunately, when this change is made, LSR will generate different code. One of the root causes seems to be that SCEV will return different nsw/nuw flags for the same Value, depending on what order the SCEVs are computed, due to the fact that the SCEV object unique-ing doesn't take the nsw/nuw flags into account. Since LoopDataPrefetch computes SCEVs in a different order than LSR, the nsw/nuw flags seen b...

...;> that has finally reached a point where I can claim it to be >> "potentially viable". I'd like to gather some input from the >> community before moving too far ahead. >> >> >> # The problem >> >> There is a representation issue within SCEV that prevents it from >> fully using information from nsw/nuw flags present in the IR. This >> isn't just a theoretical issue, e.g. today LLVM won't unroll this >> loop: >> >> void f(int x, long* arr) { >> for (int i = x + 1; i < x + 3; i++) >>...

Hi, I'm new to ScalarEvolution and wanted to explore its capabilities. I have following few questions: 1) How to compare SCEV expressions. I have a situation to compare two SCEV to find the min among them. Found an existing function(getMinFromExprs) in LoopAccessAnalysis which compares two SCEVs. getMinFromExprs function finds the diff between two SCEV's and then checks for the negative value to find the minimum. Whil...

SCEV expansion sometimes generates redundent expr even if there is an available expr which can be reused. The redundent exprs can be a lot different from existing exprs so that existing cleanup passes cannot remove them. https://llvm.org/bugs/show_bug.cgi?id=24920 https://llvm.org/bugs/show_bug.cgi?id=...

...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. > >...

On Wed, Aug 24, 2016 at 3:07 PM, Daniel Berlin <dberlin at dberlin.org> wrote: > > > On Fri, Aug 19, 2016 at 3:57 PM, Wei Mi via llvm-dev > <llvm-dev at lists.llvm.org> wrote: >> >> SCEV expansion sometimes generates redundent expr even if there is an >> available expr which can be reused. The redundent exprs can be a lot >> different from existing exprs so that existing cleanup passes cannot >> remove them. >> >> https://llvm.org/bugs/show_bug.cgi?id=...

> 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: &gt...

...Re: [llvm-dev] ScalarEvolution questions Hi Ashutosh, On Wed, May 9, 2018 at 3:28 AM, Nema, Ashutosh via llvm-dev <llvm-dev at lists.llvm.org> wrote: > I’m new to ScalarEvolution and wanted to explore its capabilities. > > I have following few questions: > > 1) How to compare SCEV expressions. > > I have a situation to compare two SCEV to find the min among them. > > Found an existing function(getMinFromExprs) in LoopAccessAnalysis > which compares two SCEVs. > > getMinFromExprs function finds the diff between two SCEV’s and then > checks for the ne...

> On Aug 23, 2016, at 11:30 PM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote: > > Hi Wei, > > I've not seen GCC's SCEV so I cannot make a comparative comment here > (maybe Chris, Andy or Dan can chime in here), but I personally am in > the "make the cleanup passes smarter" camp. We can also try to make > SCEV expansion smarter -- not by putting more things in SCEVExpander > (it is already com...

My response to this patch is below, but adding a floating-point feature to SCEV should really be hashed out on the llvm-dev list first. I would like to get the attention of floating-point experts on the design review. I’d like to see a small design proposal justifying the feature and defending it’s soundness. My concern is that the approach may not be sound, but providing thi...

Hi Ashutosh, On Wed, May 9, 2018 at 3:28 AM, Nema, Ashutosh via llvm-dev <llvm-dev at lists.llvm.org> wrote: > I’m new to ScalarEvolution and wanted to explore its capabilities. > > I have following few questions: > > 1) How to compare SCEV expressions. > > I have a situation to compare two SCEV to find the min among them. > > Found an existing function(getMinFromExprs) in LoopAccessAnalysis which > compares two SCEVs. > > getMinFromExprs function finds the diff between two SCEV’s and then checks > for the nega...

...r insightful comment. Tons thanks in advance! Shuxin I don't know for sure if I can post the reduced *.ll (2k+ lines) to the list. Let me try my best to describe this problem without *.ll. Let me start from 5k feet high. ================================== The relevant aspect of SCEV regarding to the problem are: a1) SCEV is *NOT* self-contained. At least SCEVUnknown points to an llvm::Instruction. a2) SCEV must be in sync with IR. One way to sync them is to delete invalidate SCEV, and force SE to recompute based on most recent IR. SCEVUnknonw is...

...://llvm.org/bugs/show_bug.cgi?id=27894 And the case with a constant loop count is filed as PR27899: https://llvm.org/bugs/show_bug.cgi?id=27899 On Thu, Jun 2, 2016 at 7:48 AM, Demikhovsky, Elena via llvm-dev < llvm-dev at lists.llvm.org> wrote: > I implemented IV simplification with FP SCEV and uploaded a new patch. The > loop bellow is converted to “start+const*N”. > > (You can see the diff between patches to see what was added). > > > > - * Elena* > > > > *From:* atrick at apple.com [mailto:atrick at apple.com] > *Sent:* Monday, May 30, 2...