search for: addrec

hi all, i have SCEVAddRec {{(32 + @edge.8265),+,32}<Loop0>,+,4}<Loop1> where Loop0 and Loop1 are brothers (loops at the same level of the loopnest), and Loop0 have a computable backedge taken count. when i call getSCEVAtScope({{(32 + @edge.8265),+,32}<Loop0>,+,4}<Loop1> , Loop1), it just give me...

Hi, Is it valid to query ScalarEvolution::getSCEVAtScope with a Value which is an Instruction inside the provided Loop? If so, I believe there is a bug in computeSCEVAtScope. Specifically: 04716     // If the scope is outside the addrec's loop, evaluate it by using the 04717     // loop exit value of the addrec. 04718     if (!AddRec->getLoop()->contains(L)) { 04719       // To evaluate this recurrence, we need to know how many times the AddRec 04720       // loop iterates.  Compute this now. 04721       const SCEV *Back...

...lt;tjablin at gmail.com> wrote: > Hi, > > Is it valid to query ScalarEvolution::getSCEVAtScope with a Value > which is an Instruction inside the provided Loop? If so, I believe > there is a bug in computeSCEVAtScope. Specifically: > > 04716     // If the scope is outside the addrec's loop, evaluate it by using the > 04717     // loop exit value of the addrec. > 04718     if (!AddRec->getLoop()->contains(L)) { > 04719       // To evaluate this recurrence, we need to know how many > times the AddRec > 04720       // loop iterates.  Compute this now. &gt...

..., label %for.body And, when going through the GEP: %0 = shl nsw i64 %indvars.iv, 1 %arrayidx = getelementptr inbounds i32* %b, i64 %0 ScalarEvolution::createNodeForGEP() is losing the SCEV::FlagNSW, and I believe it's because of this piece of code in getMulExpr(): // Build the new addrec. Propagate the NUW and NSW flags if both the // outer mul and the inner addrec are guaranteed to have no overflow. // // No self-wrap cannot be guaranteed after changing the step size, but // will be inferred if either NUW or NSW is true. Flags = AddRec->getNoWrapFl...

...Evolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, > } > > // If we found some loop invariants, fold them into the recurrence. > if (!LIOps.empty()) { > // NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step} > LIOps.push_back(AddRec->getStart()); > > SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(), > AddRec->op_end()); > - AddRecOps[0] = getAddExpr(LIOps); > + AddRecOps[0] = getAddExpr(LIOps, Flags); > > // Build...

...through the GEP: > > %0 = shl nsw i64 %indvars.iv, 1 > %arrayidx = getelementptr inbounds i32* %b, i64 %0 > > ScalarEvolution::createNodeForGEP() is losing the SCEV::FlagNSW, and I believe it's because of this piece of code in getMulExpr(): > > // Build the new addrec. Propagate the NUW and NSW flags if both the > // outer mul and the inner addrec are guaranteed to have no overflow. > // > // No self-wrap cannot be guaranteed after changing the step size, but > // will be inferred if either NUW or NSW is true. > Flags...

​Hi, Would you be able to kindly check and assist with the IndVarSimplify / SCEV problem I got in the latest LLVM, please? Sometimes IndVarSimplify may not eliminate narrow IV's when there actually exists such a possibility. This may affect other LLVM passes and result in inefficient code. The reproducing test 'indvar_test.cpp' is attached. The problem is with the second

...ext i32 {2,+,1}<nw><%for.body> to i64)* > > > from the following C source, > > *void strong3(int *A, int *B, int n) {* > * for (int i = 0; i < n; i++) {* > * A[i + 2] = i;* > * ...* > * }* > *}* > > > Since the No-Wrap flag is set on the addrec, can't I safely rewrite it as > > *{2,+,1}<nw><%for.body>* > > > If I can, why isn't the SCEV package simplifying things for me? > > > The short answer is that SCEV is terrible at preserving NSW flags. I > personally don't believe they belong in SC...

...} return mult; } the inner loop is completed unrolled (by 30) to a long chain of "add" and "mult" instructions, then indvars follows loop-unroll and triggers SCEV creations for this long instruction chain. When it comes to getMulExpr, it tries to fold multiplications of AddRecs of the same induction variable recursively, this could be very slow if the expression tree is deep. Code responsible for this problem starts here (in ScalarEvolution.cpp): // Okay, if there weren't any loop invariants to be folded, check to see if // there are multiple AddRec's wi...

On Jun 29, 2010, at 7:08 AM, ether zhhb wrote: > > why computeSCEVAtScope not try to get the operands in the current > scope like the function do with SCEVCommutativeExpr, like: > > if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) { > if (!L || !AddRec->getLoop()->contains(L)) { > ... > // Then, evaluate the AddRec. > AddRec = AddRec->evaluateAtIteration(BackedgeTakenCount, *this); > } > > try to evalue every operand of Ad...

...y subtracting one step from >> the recurrence, performing the Truncate and ZeroExtend, and then >> adding the step to the result. In other words: >> >> %add[n] = Add( >> ZeroExtend( >> Truncate( >> Minus(AddRec(Start=0,Step=3)[n], 3), >> i8), >> i32), >> 3) >> >> It's a little more complicated when the Step is another recurrence, >> but essentially the same. > Something is wrong here. On the first iteration, the...

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

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

...;<%for.body> to i64) >> >> from the following C source, >> >> void strong3(int *A, int *B, int n) { >> for (int i = 0; i < n; i++) { >> A[i + 2] = i; >> ... >> } >> } >> >> Since the No-Wrap flag is set on the addrec, can't I safely rewrite it as >> >> {2,+,1}<nw><%for.body> >> >> If I can, why isn't the SCEV package simplifying things for me? > > The short answer is that SCEV is terrible at preserving NSW flags. I personally don't believe they belong in...

On Tue, Dec 18, 2012 at 9:56 AM, Matthew Curtis <mcurtis at codeaurora.org> wrote: > > Here's how I'm evaluating the expression (in my head): > > 00: Add(ZeroExtend(Truncate(Minus(AddRec(Start=0,Step=3)[n],3), i8), i32),3) > | > 01: Add(ZeroExtend(Truncate(Minus(AddRec(Start=0,Step=3)[0],3), i8), i32),3) > | > 02: Add(ZeroExtend(Truncate(Minus(3,3), i8), i32),3) This step is wron...

Yes, I can get "SCEVAddRecExpr" from operands of "(sext i32 {2,+,2}<%for.body4> to i64)". So whenever SCEV cast to "SCEVAddRecExpr" fails, we have drill down for such patterns ? Is that the right way ? Regards, Ashutosh -----Original Message----- From: Nick Lewycky [mailto:nicholas at mxc....

On 16 November 2013 06:56, Andrew Trick <atrick at apple.com> wrote: > - getMulExpr constructs a new AddRec with NSW: > > Flags = AddRec->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW)); > const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop, Flags); > Hi Andrew, Thanks for looking at this. Clearing the flags here makes sense, but it's being too conservative. I'm th...

...turns- (zext i32 {{-1,+,1}<nw><%for.body>,+,-1}<nw><%for.body7> to i64) This can be seen by invoking- $ opt -analyze -scalar-evolution inconsistent-scev-zext.ll But when computing the backedge taken count of the containing loop for.body7, it is able to push zext inside the AddRec and forms the following for the same instruction- {(zext i32 {-1,+,1}<%for.body> to i64),+,-1}<nw><%for.body7> This allows ScalarEvolution to compute a valid backedge taken count for the loop. The 'simplification' is done by this piece of code inside getZeroExtendExpr()-...

Given the following SCEV, *(sext i32 {2,+,1}<nw><%for.body> to i64)* from the following C source, *void strong3(int *A, int *B, int n) {* * for (int i = 0; i < n; i++) {* * A[i + 2] = i;* * ...* * }* *}* Since the No-Wrap flag is set on the addrec, can't I safely rewrite it as *{2,+,1}<nw><%for.body>* If I can, why isn't the SCEV package simplifying things for me? Thanks, Preston -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/201...

Hi, I have a SCEV like this: {16,+,8}. Say that this came from a loop like: int64_t *p; for (int64_t i = 0; i < ...; ++i) p[i+2]... And assuming that I'm on a 64-bit machine. What I would like to do is normalize it like that, basically this: {2,+,1} i.e. map it to the index. Now, I tried to get the underlying element size of the pointer, then getUDivExpr(OriginalSCEV, ElementSize); But