search for: addrecexpr

...a pass for loop optimization. I clone and rearrange loops, setting the cloned loop as the original loop’s parent. This can be done multiple times, until there is no more work to do. The trouble is, after the first time I do this, the cloned loop's SCEVs become unknown types when they should be AddRecExpr. If I re-run the whole pass on the IR outputted by the first iteration, it will correctly identify them as AddRecExpr. I've already tried called Scalar Evolution’s *ForgetAllLoops* function, but that doesn't work. I also tried calling the *runOnFunction* from the ScalarEvolution pass, bu...

...> store i64 0, i64* %arrayidx24, align 8 > {{{(5 + ((3 + %n) * %n)),+,(2 * %n * %n)}<%for.cond1.preheader>,+,(4 * %n)}<%for.cond4.preheader>,+,6}<%for.cond7.preheader> This expression is not straight forward because llvm always fold the loop invariant in the AddExpr into the AddRecExpr. If I understand the AddRecExpr correctly, the above SCEV is equivalent to: (5 + ((3 + %n) * %n)) + (2 * %n * %n) * {0,+,1}<%for.cond1.preheader> + (4 * %n) * {0,+,1}<%for.cond4.preheader> + 6 * {0,+,1}<%for.cond7.preheader> In the above example, you can treat {0,+,1}<%for.cond...

...r) * 2 + 1 ) * inner + i%4; c[ ir0 ] = a[ ir0 ] + b[ ir0 ]; c[ ir1 ] = a[ ir1 ] + b[ ir1 ]; } } LV: Found a loop: for.body LV: Found an induction variable. LV: We need to do 0 pointer comparisons. LV: Checking memory dependencies LV: Bad stride - Not an AddRecExpr pointer %arrayidx11 = getelementptr inbounds float* %c, i64 %add2 SCEV: ((4 * %add2)<nsw> + %c)<nsw> LV: Bad stride - Not an AddRecExpr pointer %arrayidx15 = getelementptr inbounds float* %c, i64 %add8 SCEV: ((4 * %add8)<nsw> + %c)<nsw> LV: Src Scev: ((4 * %add2)<ns...

Hello, I'm studying how the SCEV analyzis works and how to use it and I could not create an example where the SCEV analyzis identifies an expression as "SCEVAddRecExpr". Aren't the expressions below the kind of pattern that should be represented as a "AddRecExpr" ? SCEV: (1 + (2 * %3) or SCEV: (%1 + (2 * %3) or SCEV: (%1 + (%2 * %3) In my experiments they are always recognized as just "AddExpr" (not *Rec*). Can someone help me o...

Is there any chance of replacing/extending the GEP instruction? As noted in the GEP FAQ, GEPs don't support variable-length arrays; when the front ends have to support VLAs, they linearize the subscript expressions, throwing away information. The FAQ suggests that folks interested in writing an analysis that understands array indices (I'm thinking of dependence analysis) should be

...= a[ ir0 ] + b[ ir0 ]; > c[ ir1 ] = a[ ir1 ] + b[ ir1 ]; > } > } > > LV: Found a loop: for.body > LV: Found an induction variable. > LV: We need to do 0 pointer comparisons. > LV: Checking memory dependencies > LV: Bad stride - Not an AddRecExpr pointer %arrayidx11 = getelementptr inbounds float* %c, i64 %add2 SCEV: ((4 * %add2)<nsw> + %c)<nsw> > LV: Bad stride - Not an AddRecExpr pointer %arrayidx15 = getelementptr inbounds float* %c, i64 %add8 SCEV: ((4 * %add8)<nsw> + %c)<nsw> > LV: Src Scev: ((4 * %add...

...hrough the public interface, which would pollute all analysis after that point with those unwanted flags. I don't know if any callers actually do this but I could see it being useful for looking at hypothetical cases. To some degree mutation of wrapping flags is part of the design, because SCEVAddRecExprs are explicitly const_casted to add flags in multiple places so that they can be found again later. But that might not be quite so harmful because they at least contain a Loop as a contextual cue that prevents some leaking. So, my real question is does anyone know what the contract with ScalarEvol...

Hi Sebastian, Recently, I found the "Polly - Calculate dependences" pass would lead to significant compile-time overhead when compiling some loop-intensive source code. Tobias told me you found similar problem as follows: http://llvm.org/bugs/show_bug.cgi?id=14240 My evaluation shows that "Polly - Calculate dependences" pass consumes 96.4% of total compile-time overhead

...which would pollute all analysis after that > point with those unwanted flags. I don't know if any callers actually > do this but I could see it being useful for looking at hypothetical > cases. > > To some degree mutation of wrapping flags is part of the design, > because SCEVAddRecExprs are explicitly const_casted to add flags in > multiple places so that they can be found again later. But that might > not be quite so harmful because they at least contain a Loop as a > contextual cue that prevents some leaking. > > So, my real question is does anyone know what the...

...o the way >>SCEVExpr(essions) in LLVM are nested, Polly sees three scop-invariant >>SCEVExpr(essions) which are all translated into independent parameters. >>However, as we can see, the only difference between the three >>parameters is a different constant in the base of the AddRecExpr. If we >>would just introduce p_0 (the parameter where the scev-base is zero) and >>express any use of p_1 as p_0 + 2 and p_2 as p_0 + 4, isl could solve >>this problem very quickly. > > Currently, Polly introduces three parameters because it treats (base, step) as a whole f...

...length = 2. SLP: Vectorizing a list of length = 2. SLP: Vectorizing a list of length = 2. LV: Checking a loop in "_Z3barmmPfS_S_" LV: Found a loop: for.body LV: Found an induction variable. LV: We need to do 0 pointer comparisons. LV: Checking memory dependencies LV: Bad stride - Not an AddRecExpr pointer %arrayidx6 = getelementptr inbounds float* %c, i64 %add2 SCEV: ((4 * %add2)<nsw> + %c)<nsw> LV: Bad stride - Not an AddRecExpr pointer %arrayidx10 = getelementptr inbounds float* %c, i64 %add312 SCEV: ((4 * %add312)<nsw> + %c)<nsw> LV: Src Scev: ((4 * %add2)&lt...

Verifying function running passes ... LV: Checking a loop in "bar" LV: Found a loop: L0 LV: Found an induction variable. LV: We need to do 0 pointer comparisons. LV: Checking memory dependencies LV: Bad stride - Not an AddRecExpr pointer %13 = getelementptr float* %arg2, i32 %1 SCEV: ((4 * (sext i32 {(256 + %arg0),+,1}<nw><%L0> to i64)) + %arg2) LV: Src Scev: {((4 * (sext i32 %arg0 to i64)) + %arg2),+,4}<%L0>Sink Scev: ((4 * (sext i32 {(256 + %arg0),+,1}<nw><%L0> to i64)) + %arg2)(Inducti...

...ne is actually of isl_aff type. Perhaps we could first commit a patch file to handle common cases, then we can considering submitting another patch file to handle general cases. >I think this is the right idea, but probably the wrong place to put it. >I would put this into SCEVValidator::visitAddRecExpr. This function >always adds the AddRecExpr itself as a parameter, whenever it is found >to be parametric. However, what we should do is to create a new ScevExpr >that starts at zero and is otherwise identical. We then add this as a >parameter. When doing this, we now also need to kee...

...SCoP invariant. However, due to the way SCEVExpr(essions) in LLVM are nested, Polly sees three scop-invariant SCEVExpr(essions) which are all translated into independent parameters. However, as we can see, the only difference between the three parameters is a different constant in the base of the AddRecExpr. If we would just introduce p_0 (the parameter where the scev-base is zero) and express any use of p_1 as p_0 + 2 and p_2 as p_0 + 4, isl could solve this problem very quickly. There are other ways to improve performance which include further tuning isl or reducing the precision of the analysis...

...winter at jlab.org> wrote: > Verifying function > running passes ... > LV: Checking a loop in "bar" > LV: Found a loop: L0 > LV: Found an induction variable. > LV: We need to do 0 pointer comparisons. > LV: Checking memory dependencies > LV: Bad stride - Not an AddRecExpr pointer %13 = getelementptr float* %arg2, i32 %1 SCEV: ((4 * (sext i32 {(256 + %arg0),+,1}<nw><%L0> to i64)) + %arg2) > LV: Src Scev: {((4 * (sext i32 %arg0 to i64)) + %arg2),+,4}<%L0>Sink Scev: ((4 * (sext i32 {(256 + %arg0),+,1}<nw><%L0> to i64)) + %arg2)(Induct...

...However, due to the way >SCEVExpr(essions) in LLVM are nested, Polly sees three scop-invariant >SCEVExpr(essions) which are all translated into independent parameters. >However, as we can see, the only difference between the three >parameters is a different constant in the base of the AddRecExpr. If we >would just introduce p_0 (the parameter where the scev-base is zero) and >express any use of p_1 as p_0 + 2 and p_2 as p_0 + 4, isl could solve >this problem very quickly. >There are other ways to improve performance which include further tuning >isl or reducing the preci...

...ranteed 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->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW)); > const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop, Flags); > > // If all of the other operands were loop invariant, we are done. > if (Ops.size() == 1) return NewRec; > > I understand that you can't assume it won't wrap around with the new stride, but I couldn't find anything else later t...

The debug messages are misleading. They should read “trying to vectorize a list of …”; The problem is that the SCEV analysis is unable to detect that C[ir0] and C[ir1] are consecutive. Is this loop from an important benchmark ? Thanks, Nadav On Oct 30, 2013, at 11:13 AM, Frank Winter <fwinter at jlab.org> wrote: > The SLP vectorizer apparently did something in the prologue of the

For void test0(unsigned short a, unsigned short * in, unsigned short * out) { for (unsigned short w = 1; w < a - 1; w++) //this will never overflow out[w] = in[w+7] * 2; } I think it will be sufficient to add a couple of new cases to ScalarEvolution::HowManyLessThans -- zext(A) ult zext(B) == A ult B sext(A) slt sext(B) == A slt B Currently it bails out if it sees a non-add

...n opportunities (http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-April/084765.html), but maybe different enough to require a new thread. I'm seeing some missed vectorization opportunities in the loop vectorizer because SCEV is not able to fold sext/zext expressions into recurrence expressions (AddRecExpr). This can manifest in multiple ways: - We cannot get the back-edges taken count since SCEV because we may have something like (sext (1,+1)) which we can't evaluate as it can overflow - We cannot get SCEV AddRec expressions for pointers which need runtime checks, and the...