<div style="line-height:1.7;color:#000000;font-size:14px;font-family:arial"><div style="line-height:1.7;color:#000000;font-size:14px;font-family:arial">Hi Tobias and Sven,<div><br></div><div>Thanks for your discussion and suggestion. </div><div><span style="font-size: 14px; line-height: 1.7;"><br></span></div><div><div>@Sven: ISL actually allows users to <span style="white-space: pre-wrap; font-size: 14px; line-height: 1.7;">have different identifiers with the same name. The problem that we have discussed is caused by incorrect usage of isl_space in Polly, so please do not worry about ISL library. You can skip the following information related to Polly implementation.</span></div><div><span style="white-space: pre-wrap; font-size: 14px; line-height: 1.7;"><br></span></div><div><span style="white-space: pre-wrap;">@Tobias and Polly developers:</span></div><div><span style="white-space: pre-wrap;">I have attached a patch file to fix this!
problem. The key idea is to keep ISL library always seeing the same single parameter for those memory accesses that use the same index variables even though they have different constant base values.</span></div><div><span style="white-space: pre-wrap;"><br></span></div><div><span style="white-space: pre-wrap;">For the example we have seen before:</span></div><div><span style="white-space: pre-wrap;"> for(i = 0; i < 8; i++) {
for (ctr = 0; ctr < 8; ctr++) {
x1 = input[i*64 + ctr*8 + 1] ;
x0 = input[i*64 + ctr*8 + 0] ;
input[i*64 + ctr*8 + 0] = x0 - x1;
input[i*64 + ctr*8 + 1] = x0 + x1;
input[i*64 + ctr*8 + 2] = x0 * x1;
}</span></div><div><span style="white-space: pre-wrap;"><br></span></div><div><span style="white-space: pre-wrap;">Without this patch file, Polly would produce the Context as follows:</span></div><div><br></div><div> Context:</div><div><span style="white-space: pre-wrap;"> [p_0, p_1, p_2] -> { : p_0 >= -9223372036854775808 and p_0 <= 9223372036854775807 and p_1 >= -9223372036854775808 and p_1 <= 9223372036854775807 and p_2 >= -9223372036854775808 and p_2 <= 9223372036854775807 }
p0: {0,+,128}<%for.cond2.preheader>
p1: {2,+,128}<%for.cond2.preheader>
p2: {4,+,128}<%for.cond2.preheader>
Statements {
Stmt_for_body6
Domain :=
[p_0, p_1, p_2] -> { Stmt_for_body6[i0] : i0 >= 0 and i0 <= 7 };
Scattering :=
[p_0, p_1, p_2] -> { Stmt_for_body6[i0] -> scattering[0, i0, 0] };
ReadAccess :=
[p_0, p_1, p_2] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = p_0 + 16i0 };
ReadAccess :=
[p_0, p_1, p_2] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = p_1 + 16i0 };
MustWriteAccess :=
[p_0, p_1, p_2] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = p_0 + 16i0 };
MustWriteAccess :=
[p_0, p_1, p_2] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = p_1 + 16i0 };
MustWriteAccess :=
[p_0, p_1, p_2] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = p_2 + 16i0 };
}</span></div><div><span style="white-space: pre-wrap;"><br></span></div><div><span style="white-space: pre-wrap;">Furthermore, it will produce very complex RAW, WAW and WAR dependence as follows:</span></div><div><span style="white-space: pre-wrap;"><br></span></div><div><span style="white-space: pre-wrap;"> RAW dependences:
[p_0, p_1, p_2] -> { Stmt_for_body6[i0] -> Stmt_for_body6[o0] : (exists (e0 = [(p_1)/2], e1 = [(7p_1 + p_2 + 112i0)/16]: 16o0 = -p_0 + p_1 + 16i0 and 2e0 = p_1 and 16i0 >= -p_1 + p_2 and 16i0 <= 112 + p_0 - p_1 and p_1 >= 16 + p_0 and i0 >= 0 and 16e1 >= -15 + 7p_1 + p_2 + 112i0 and 16e1 <= -1 + 7p_1 + p_2 + 112i0 and p_2 >= 16 + p_0)) or ... or (exists (e0 = [(p_1)/2], e1 = [(-p_1 + p_2)/16]: 16o0 = p_0 - p_1 + 16i0 and 2e0 = p_1 and 16e1 = -p_1 + p_2 and 16i0 >= -p_0 + p_2 and 16i0 <= 112 - p_0 + p_1 and p_1 <= -16 + p_0 and p_2 >= 16 + p_0)) }</span></div><div><br></div><div>It not only leads to significant compile-time overhead, but also produces incorrect dependence results. As we can see from the source code, there should be no RAW, WAW and WAR across loop iterations at all. </div><div><br></div><div>With this patch file, Polly would produce the following Context and RAW, WAW, WAR dependence:</div><div><br></div><div>!
<div>Context:</div><div> [p_0] -> { : p_0 >= -9223372036854775808 and p_0 <= 9223372036854775807 }</div><div> p0: {0,+,128}<%for.cond2.preheader></div><div> Statements {</div><div> <span class="Apple-tab-span" style="white-space:pre"> </span>Stmt_for_body6</div><div> Domain :=</div><div> [p_0] -> { Stmt_for_body6[i0] : i0 >= 0 and i0 <= 7 };</div><div> Scattering :=</div><div> [p_0] -> { Stmt_for_body6[i0] -> scattering[0, i0, 0] };</div><div> ReadAccess := </div><div> [p_0] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = p_0 + 16i0 };</div><div> Rea!
dAccess := </div><div> &
nbsp; [p_0] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = 2 + p_0 + 16i0 };</div><div> MustWriteAccess := </div><div> [p_0] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = p_0 + 16i0 };</div><div> MustWriteAccess := </div><div> [p_0] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = 2 + p_0 + 16i0 };</div><div> MustWriteAccess := </div><div> [p_0] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = 4 + p_0 + 16i0 };</div><div> }</div><div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>RAW dependences:</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>[p_0] -> { }<!
/div><div><span class="Apple-tab-span" style="white-space:pre"> </span>WAR dependences:</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>[p_0] -> { }</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>WAW dependences:</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>[p_0] -> { }</div><div><br></div><div>We can see it only creates a single parameter and it can catch the exact RAR, WAW and WAW dependence.</div><div><br></div>To see whether our patch file could catch normal data dependence, I have constructed another example as follows:</div><div><br></div><div><div> for(i = 0; i < 8; i++) {</div><div> for (ctr = 0; ctr < 8; ctr++) {</div><div><span style="font-size: 14px; line-height: 1.7;"> x0 = input[i*64 + ctr + 0] ;</span> </div><div> x1 = input[i*64 + ctr + 1] ;</div><div> input[i*64 + ctr + 0] = x0 !
- x1;</div><div> input[i*64 + ctr + 1] = x0 + x1;<
/div><div> input[i*64 + ctr + 2] = x0 * x1;</div><div> }</div><div><br></div><div>The original Polly would produce similar complex results. However, with the attached patch file, Polly would <span style="font-size: 14px; line-height: 1.7;">produce the following Context and RAW, WAW, WAR dependence:</span></div><div><div>Context:</div><div> [p_0] -> { : p_0 >= -2147483648 and p_0 <= 2147483647 }</div><div> p0: {0,+,128}<%for.cond2.preheader></div><div> Statements {</div><div> <span class="Apple-tab-span" style="white-space:pre"> </span>Stmt_for_body6</div><div> Domain :=</div><div> [p_0] -> { Stmt_for_body6[i0] : i0 >= 0 and i0 <= 7 };</div><div> Scattering :=</div><div>  !
; [p_0] -> { Stmt_for_body6[i0] -> scattering[0, i0, 0] };</div><div> ReadAccess := </div><div> [p_0] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = p_0 + 2i0 };</div><div> ReadAccess := </div><div> [p_0] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = 2 + p_0 + 2i0 };</div><div> MustWriteAccess := </div><div> [p_0] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = p_0 + 2i0 };</div><div> MustWriteAccess := </div><div> [p_0] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = 2 + p_0 + 2i0 };</div><div> !
MustWriteAccess := </div><div>
[p_0] -> { Stmt_for_body6[i0] -> MemRef_input[o0] : 2o0 = 4 + p_0 + 2i0 };</div><div> }</div><div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>RAW dependences:</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>[p_0] -> { Stmt_for_body6[i0] -> Stmt_for_body6[1 + i0] : exists (e0 = [(p_0)/2]: 2e0 = p_0 and i0 >= 0 and i0 <= 6) }</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>WAR dependences:</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>[p_0] -> { }</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>WAW dependences:</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>[p_0] -> { Stmt_for_body6[i0] -> Stmt_for_body6[1 + i0] : exists (e0 = [(p_0)/2]: 2e0 = p_0 and i0 >= 0 and i0 <= 6) </div></div><div><br></div>Results show that it still creates a single p!
arameter and catches <span style="font-size: 14px; line-height: 1.7;">the exact RAR, WAW and WAW dependence.</span><span style="font-size: 14px; line-height: 1.7;"> Of course, this patch file makes the compiling very faster, i.e., compile-time is reduced from several minutes to less then 1 second.</span></div><div><span style="font-size: 14px; line-height: 1.7;"><br></span></div><div><span style="font-size: 14px; line-height: 1.7;">@Tobias:</span></div><div><pre>>This is obviously a hack. The base is not always a constant.
>You can probably just call use something like,
>isl_pw_aff *BaseValue = visit(AR->getOperand(0))
>Affine = isl_pw_aff_sum(Affine, BaseValue);</pre></div><div><div></div><div id="divNeteaseMailCard"></div>Currently, I only handle constant base values because I have not found a good way to handle general base values. <span style="white-space: pre-wrap; line-height: 1.7;">isl_pw_aff_add requires two isl_pw_aff parameters, but Affine 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.</span></div><div><pre>>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 keep all the parameters
>that have been found previously in the base expression.</pre><pre>A lot of Polly functions access ParameterIds and Parameters using existing ScevExpr. If we create new ScevExpr and put them into Parameters and ParameterIds, it may require some extra tricks to handle the mapping from existing ScevExpr to newly created ScevExpr. I think we can consider fixing it later.</pre><pre>Cheers,</pre><pre>Star Tan</pre></div><div><pre><br>At 2013-07-30 00:27:27,"Tobias Grosser" <<a href="mailto:tobias@grosser.es">tobias@grosser.es</a>> wrote:
>On 07/29/2013 09:15 AM, Sven Verdoolaege wrote:
>> On Mon, Jul 29, 2013 at 07:37:14AM -0700, Tobias Grosser wrote:
>>> On 07/29/2013 03:18 AM, Sven Verdoolaege wrote:
>>>> On Sun, Jul 28, 2013 at 04:42:25PM -0700, Tobias Grosser wrote:
>>>>> Sven: In terms of making the behaviour of isl easier to understand,
>>>>> it may make sense to fail/assert in case operands have parameters that
>>>>> are named identical, but that refer to different pointer values.
>>>>
>>>> No, you are allowed to have different identifiers with the same name.
>>>> I could optionally print the pointer values, but then I'd have
>>>> to think about what to do with them when reading a textual
>>>> representation of a set with such pointer values in them.
>>>
>>> Yes, this is how it is today.
>>
>> No, the pointer values are currently not printed.
>
>I was referring to the first sentence. I do not think printing pointer
>values is what we want. It would make the output unpredictable not only
>when address space randomisation is involved.
>
>>> I wondered if there is actually a need to
>>> allow the use of different identifiers with the same name (except all being
>>> unnamed?). I personally do not see such a need and would prefer isl to
>>> assert/fail in case someone tries to do so. This may avoid confusions as
>>> happened here. Do you see a reason why isl should allow this?
>>
>> Removing this feature would break existing users.
>
>Even if it would, the benefits for future users may outweigh this.
>Also, are you aware of a user that actually breaks?
>
>Anyway, on the Polly side we know the behaviour and can handle it. So
>this is nothing I am very strong about. I just mentioned it as it seemed
>to be a good idea.
>
>Cheers,
>Tobias
>
</pre></div></div></div></div>