search for: backedgetakencount

...drec'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 *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); 04722       if (BackedgeTakenCount == getCouldNotCompute()) return AddRec; 04723 04724       // Then, evaluate the AddRec. 04725       return AddRec->evaluateAtIteration(BackedgeTakenCount, *this); 04726     } The guard checks that !AddRec->getL...

...y 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 *BackedgeTakenCount = > getBackedgeTakenCount(AddRec->getLoop()); > 04722       if (BackedgeTakenCount == getCouldNotCompute()) return AddRec; > 04723 > 04724       // Then, evaluate the AddRec. > 04725       return AddRec->evaluateAtIteration(BackedgeTakenCount, *this); > 04726     } > >...

...at philipreames.com> 2019-08-01 03:16:08 Committer: Philip Reames <listmail at philipreames.com> 2019-08-01 03:16:08 Fix a release-only build warning triggered by rL367485 llvm-svn: 367499 [..] +#ifndef NDEBUG + // Used below for a consistency check only const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); +#endif ----- It seems that the 'SE->getBackedgeTakenCount(L)' call has sideeffects.. Is that to be expected ? Is the correct solution then to always keep the call ? Thanks, Jeroen Dobbelaere

Mmm, sorry, the patch I posted crashes if ExitBr is null (which it may be ...) , this one should be ok (and passess all the ScalarEvolution tests in LLVM): diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index daf7742..b10fab2 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -4293,9 +4293,15 @@

Your patch should include a testcase, see test/Analysis/ScalarEvolution for examples. "BranchInst* " should be "BranchInst *". You should have spaces after the // in your comments. One of the comment lines isn't indented properly. Nick On 8 February 2012 12:05, Marcello Maggioni <hayarms at gmail.com> wrote: > Attached > > 2012/2/8 Marcello Maggioni

...tional branch, so simplifycfg folds the almost empty latch block into its predecessor which is the loop header. This results in an additional backedge in the CFG, so when LoopRotate pass is called it canonicalizes the loop into a nested loop. However, now the loop trip count is unpredictable as the BackedgeTakenCount for the outer loop is not loop invariant. As a result the loop cannot be unrolled. Is this the intended canonicalization for this loop or is the loopsimplify canonicalizing incorrectly? Should simplifycfg skip folding the latch block into the loop header if this results in additional backedges and...

Hello, I'm finding problems with BackEdgeTaken count calculation in even simple fortran loops with gfortran-4.6 + DragonEgg 3.0. Even for simple double loops like this one: program test2 integer i,j,k dimension k(100,100) do j=1,100 do i=1,100 k(i,j) = i enddo enddo write(*,*) k(1,30) end make the ScalarEvolution

On 8 February 2012 15:50, Marcello Maggioni <hayarms at gmail.com> wrote: > Well, it wasn't intended as a "real" patch to be included , but more > as a "proof of concept" for a solution. Do you think it is a valid > solution and I'm correct in my assumption? If so then I'll clean up > the patch and attach a testcase for inclusion. > I'm

This is instead a very simple (handmade) test case that triggers the problem (attached) Also a more conforming patch has been attached 2012/2/9 Marcello Maggioni <hayarms at gmail.com>: > This is the .ll for that graph (attached). I think I understand what > you are saying. > This particular testcase returns CNC not because the exit block > doesn't have a unique predecessor,

FInally I had the time to complete everything up. Now I included the test case in the patch and the testcase runs with the LLVM tests system. 2012/2/9 Marcello Maggioni <hayarms at gmail.com>: > This is instead a very simple (handmade) test case that triggers the > problem (attached) > Also a more conforming patch has been attached > > 2012/2/9 Marcello Maggioni <hayarms

Attached 2012/2/8 Marcello Maggioni <hayarms at gmail.com>: > Mmm, sorry, the patch I posted crashes if ExitBr is null (which it may > be ...) , this one should be ok (and passess all the ScalarEvolution > tests in LLVM): > > diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp > index daf7742..b10fab2 100644 > ---

...rands 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 AddRec; return AddRec; } thanks very much. -- best regards ether

Well, it wasn't intended as a "real" patch to be included , but more as a "proof of concept" for a solution. Do you think it is a valid solution and I'm correct in my assumption? If so then I'll clean up the patch and attach a testcase for inclusion. Thanks! Marcello 2012/2/9 Nick Lewycky <nlewycky at google.com>: > Your patch should include a testcase,

This is the .ll for that graph (attached). I think I understand what you are saying. This particular testcase returns CNC not because the exit block doesn't have a unique predecessor, but because the unique predecessor (the inner loop block) has a successor that is inside the loop (in this case itself, because it's the inner loop block). That doesn't change, anyway, the assuption that

...fycfg folds the almost empty latch block into its > *successor* which is the loop header. This results in an additional > backedge in the CFG, so when LoopRotate pass is called it > canonicalizes the loop into a nested loop. However, now the loop trip > count is unpredictable as the BackedgeTakenCount for the outer loop is > not loop invariant. As a result the loop cannot be unrolled. Is this > the intended canonicalization for this loop or is the loopsimplify > canonicalizing incorrectly? Should simplifycfg skip folding the latch > block into the loop header if this results in a...

...e and fix which just doesn't seem worth it. Based on my limited familiarity with ScalarEvolution code I would like to propose a solution that may work- Have two levels of caching for data structures for which infinite recursion is possible (like Value -> SCEV, Value->Predicate, Loop->BackedgeTakenCount etc). The first level of caching is the 'PendingCache' and the second one is the 'FinalCache'. PendingCache is similar to PendingLoopPredicates. It is used to break infinite recursion. In addition we keep a Boolean class member 'PessimisticMode' (common to all caches). T...

...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 AddRec; > > return AddRec; > } That looks reasonable to me. Do you have a testcase which exhibits this? Dan

...st doesn't seem worth it. > > Based on my limited familiarity with ScalarEvolution code I would like to propose a solution that may work- > > Have two levels of caching for data structures for which infinite recursion is possible (like Value -> SCEV, Value->Predicate, Loop->BackedgeTakenCount etc). I'm a bit apprehensive of adding more caching to solve problems created by caching; but if there is no way out of adding another cache, how about adding a cache that maps SCEV expressions to their simplified versions? Then we could do something like: getZeroExtendExpr(S) { if (Al...

Hi, +CC Max, Serguei This looks like a textbook case of why caching is hard. We first call getZeroExtendExpr on %dec, and this call does end up returning an add rec. However, in the process of simplifying the zext, it also calls into isLoopBackedgeGuardedByCond which in turn calls getZeroExtendExpr(%dec) again. However, this second (recursive) time, we don't simplify the zext and cache a

Hi Sanjoy, SCEV is behaving inconsistently when forming SCEV for this zext instruction in the attached test case- %conv5 = zext i32 %dec to i64 If we request a SCEV for the instruction, it returns- (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