search for: getzeroextendexpr

...t SCEV, when trying to perform strength reduction, doesn’t use > the ability to prove an induction variable does not signed/unsigned wrap due > to infinite loops. > > Is there an easy way to use the isAddRecNeverPoison function when > determining if strength reduction is possible? In getZeroExtendExpr. > > Is there a reason why this doesn’t happen? I guess your point is that in int foo(int a) { int sum = 0; for (short i = 0; i < a; i++) { sum++; } return sum; } either the loop is finite (and i <= SHORT_MAX) or the program has UB (since sum overflows), so we can assume...

...xt 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()- // Cache knowledge of AR NW, which is propagated to this // AddRec. Negative step causes unsigned wrap, but it // still can't self-wrap. const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW); // Return the expres...

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

...ching; 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: I may be wrong but I think caching is not an issue in itself, but caching in the presence of self-recursion is. >> getZeroExtendExpr(S) { >> if (AlreadyPresent = UniqueSCEVs.find(kZeroExtend, S) { >> if (Simplified = SimplifiedSCEVs.find(AlreadyPresent)) { >> return Simplified; >> } >> return AlreadyPresent; >> } >> ... >> // We discovered zext(s)...

...intel.com>; Maxim Kazantsev <max.kazantsev at azul.com>; Serguei Katkov <serguei.katkov at azul.com> Cc: llvm-dev at lists.llvm.org Subject: Re: [SCEV] Inconsistent SCEV formation for zext 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 pessimistic...

...s 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: > > I may be wrong but I think caching is not an issue in itself, but caching in the presence of self-recursion is. > > >>> getZeroExtendExpr(S) { >>> if (AlreadyPresent = UniqueSCEVs.find(kZeroExtend, S) { >>> if (Simplified = SimplifiedSCEVs.find(AlreadyPresent)) { >>> return Simplified; >>> } >>> return AlreadyPresent; >>> } > >>> ... >...

...cate, 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 (AlreadyPresent = UniqueSCEVs.find(kZeroExtend, S) { if (Simplified = SimplifiedSCEVs.find(AlreadyPresent)) { return Simplified; } return AlreadyPresent; } ... // We discovered zext(s) can be simplified to t UniqueSCEVs.insert({kZeroExtend, S},...

...ching; 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: I may be wrong but I think caching is not an issue in itself, but caching in the presence of self-recursion is. >> getZeroExtendExpr(S) { >> if (AlreadyPresent = UniqueSCEVs.find(kZeroExtend, S) { >> if (Simplified = SimplifiedSCEVs.find(AlreadyPresent)) { >> return Simplified; >> } >> return AlreadyPresent; >> } >> ... >> // We discovered zext(s)...

...s 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: > > I may be wrong but I think caching is not an issue in itself, but caching in the presence of self-recursion is. > > >>> getZeroExtendExpr(S) { >>> if (AlreadyPresent = UniqueSCEVs.find(kZeroExtend, S) { >>> if (Simplified = SimplifiedSCEVs.find(AlreadyPresent)) { >>> return Simplified; >>> } >>> return AlreadyPresent; >>> } > >>> ... >...

...ng another cache, how about adding a cache that maps SCEV expressions to their simplified versions? Then we could do something like: >> >> I may be wrong but I think caching is not an issue in itself, but caching in the presence of self-recursion is. >> >> >>>> getZeroExtendExpr(S) { >>>> if (AlreadyPresent = UniqueSCEVs.find(kZeroExtend, S) { >>>> if (Simplified = SimplifiedSCEVs.find(AlreadyPresent)) { >>>> return Simplified; >>>> } >>>> return AlreadyPresent; >>>> } >&...

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

...cateExpr((3 + (zext i8 {-3,+,3}<%for.body> to i32)), i8) 05: calls getTruncateExpr(3) 06: returns 3 07: calls getTruncateExpt((zext i8 {-3,+,3}<%for.body> to i32)) 08: returns {-3,+,3}<%for.body> 09: returns {0,+,3}<%for.body> 10: calls getZeroExtendExpr({0,+,3}<%for.body>, i32); 11: returns (zext i8 {0,+,3}<%for.body> to i32) 12: returns (zext i8 {0,+,3}<%for.body> to i32) This expression is (I believe) correct for %conv2. The intent of the patch is to construct the correct (evaluatable) expression for %result.03 being...

Dan, Thanks for the response ... On 12/17/2012 1:53 PM, Dan Gohman wrote: > On Mon, Dec 10, 2012 at 2:13 PM, Matthew Curtis <mcurtis at codeaurora.org> wrote: >> Hello all, >> >> I wanted to get some feedback on this patch for ScalarEvolution. >> >> It addresses a performance problem I am seeing for simple benchmark. >> >> Starting with this C

...e(); + assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) && + (Ty->isIntegerTy() || Ty->isPointerTy()) && + "Cannot truncate and zero extend with non-integer arguments!"); + const SCEV *trunc = getTruncateExpr(V, Ty); + const SCEV *zext = getZeroExtendExpr(trunc, V->getType()); + return zext; +} + /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the /// input value to the specified type. If the type must be extended, it is zero /// extended. @@ -3029,13 +3040,22 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHIN...