<div dir="ltr">On 21 October 2013 17:29, Arnold Schwaighofer <span dir="ltr"><<a href="mailto:aschwaighofer@apple.com" target="_blank">aschwaighofer@apple.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">I don’t think that recognizing this as a reduction is going to get you far. A reduction is beneficial if the value reduced is only truly needed outside of a loop.<br>
This is not the case here (we are storing/loading from the pointer).<br></blockquote><div><br></div><div>Hi Arnold, Nadav,</div><div><br></div><div>Let me resurrect this discussion a bit.</div><div><br></div><div>There are few things that I need to check while validating a stride access loop:</div>
<div> 1. If there is an induction variable, and it has stride > 1. This is easy, and can be easily extended on isInductionVariable() by adding Step to InductionInfo;</div><div> 2. If the reduction variables' access are sequential and compatible with the stride. This is the core of the change, and will require SCEV computation, as extensively described by Arnold.<br>
</div><div> 3. If the reduction variable has any use outside of the loop. This will need to account for global variables, which is in itself, a use of the computed value.<br></div><div><br></div><div>The problem I'm having, and why I'm resurrecting this thread, is in this simple code:</div>
<div><br></div><div>#define OFFSET 255</div><div>extern char b[OFFSET];</div><div><div>char *fn1 (char a[]) {</div><div> unsigned i;</div><div><br></div><div> for (i=0; i<OFFSET; i += 3) {</div><div> a[i] = OFFSET - b[i] - DELTA;</div>
<div> a[i+1] = OFFSET - b[i+1] - DELTA;</div><div> a[i+2] = OFFSET - b[i+2] - DELTA;</div><div> }</div><div> return &a[0];</div><div>}</div></div><div><br></div><div>This is the most trivial example. The exit count is constant, the operations are the same and compatible with the stride of 3, and the variable "a" is used outside the loop. However, the optimized code that the vectorizer sees is after SCEV has passed through it, leaving the IR very similar to my original example:</div>
<div><br></div><div><div>for.body: ; preds = %entry, %for.body</div><div> %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]</div><div> %arrayidx = getelementptr inbounds [255 x i8]* @b, i64 0, i64 %indvars.iv</div>
<div> %0 = load i8* %arrayidx, align 1</div><div> %1 = xor i8 %0, -1</div><div> %2 = load i8* @DELTA, align 1</div><div> %sub2 = sub i8 %1, %2</div><div><div> %arrayidx5 = getelementptr inbounds i8* %a, i64 %indvars.iv</div>
<div> store i8 %sub2, i8* %arrayidx5, align 1</div></div><div> ...<br></div></div><div> %indvars.iv.next = add nuw nsw i64 %indvars.iv, 3</div><div> %11 = trunc i64 %indvars.iv.next to i32</div><div> %cmp = icmp ult i32 %11, 255</div>
<div> br i1 %cmp, label %for.body, label %for.end</div><div><br></div><div>So, as you can see, my original patch to recognize pointer reductions is still relevant, since I'll need to act on the list of induction and reduction variables to discover if the reduction's stride is compatible with the induction's step. </div>
<div><br></div><div>Also, I'll need that to make sure that the reduction in question has access outside (via global / extern qualifiers), so ignoring load/store instructions that won't have any users, because the variables are not used directly, but through &a[0].</div>
<div><br></div><div>Arnold,</div><div><br></div><div>I agree with you that the analysis should not be done exclusively trying to manipulate the pointer reduction variables (but using SCEV as you describe), but I can't see how I can get past the validation phase if, at least, I don't recognize the GEP PHIs as a reduction variable.</div>
<div><br></div><div>cheers,</div><div>--renato</div></div></div></div>