<div dir="ltr">For use-def relationships, yes.<div>In particular, given a MemoryUse, it's defining access will be something that actually may/must aliases it.</div><div><br></div><div>For def-def relationships, no.</div><div>Given a MemoryDef, it's defining access will be the nearest dominating MemoryDef, regardless of whether it aliases it or not.</div><div><div><br></div><div><br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Dec 19, 2017 at 9:25 AM, Siddharth Bhat <span dir="ltr"><<a href="mailto:siddu.druid@gmail.com" target="_blank">siddu.druid@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir="ltr">@daniel: so, memorySSA is as precise as AA allows it to be? </p>
<p dir="ltr">Thanks <br><span class="HOEnZb"><font color="#888888">
Siddharth </font></span></p>
<br><div class="gmail_quote"><div><div class="h5"><div dir="ltr">On Tue 19 Dec, 2017, 21:17 Daniel Berlin via llvm-dev, <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br></div></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="h5"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Dec 19, 2017 at 3:13 AM, Venugopal Raghavan via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hi,</div><div><br></div>I am new to MemorySSA and wanted to understand its capabilities. Hence I wrote the following program (test.c):<div><br></div><div><div>int N;</div><div><br></div><div>void test(int *restrict a, int *restrict b, int *restrict c, int *restrict d, int *restrict e) {</div><div> int i;</div><div> for (i = 0; i < N; i = i + 5) {</div><div> a[i] = b[i] + c[i];</div><div> }</div><div><br></div><div> for (i = 0; i < N - 5; i = i + 5) {</div><div> e[i] = a[i] * d[i];</div><div> }</div><div>}</div></div><div><br></div><div>I compiled this program using the following commands:</div><div><br></div><div>clang -c -o test_clang_out.ll -emit-llvm -O3 test.c<br></div><div>opt -o test_opt_out.ll -O3 -passes='print<memoryssa>' -disable-output test_clang_out.ll > out 2>&1<br></div><div><br></div><div>The relevant parts of the file "out" are shown below:</div><div> .</div><div> .</div><div> .</div><div><br></div><div><div>for.body: ; preds = %<a href="http://for.body.lr.ph" target="_blank">for.body.lr.ph</a>, %for.body</div><div>; 3 = MemoryPhi({<a href="http://for.body.lr.ph" target="_blank">for.body.lr.ph</a>,<wbr>liveOnEntry},{for.body,1})</div><div> %indvars.iv35 = phi i64 [ 0, %<a href="http://for.body.lr.ph" target="_blank">for.body.lr.ph</a> ], [ %indvars.iv.next36, %for.body ]</div><div> %arrayidx = getelementptr inbounds i32, i32* %b, i64 %indvars.iv35</div><div>; MemoryUse(3)</div><div> %2 = load i32, i32* %arrayidx, align 4, !tbaa !2</div><div> %arrayidx2 = getelementptr inbounds i32, i32* %c, i64 %indvars.iv35</div><div>; MemoryUse(3)</div><div> %3 = load i32, i32* %arrayidx2, align 4, !tbaa !2</div><div> %add = add nsw i32 %3, %2</div><div> %arrayidx4 = getelementptr inbounds i32, i32* %a, i64 %indvars.iv35</div><div><b>; 1 = MemoryDef(3)</b></div><div> store i32 %add, i32* %arrayidx4, align 4, !tbaa !2</div><div> %indvars.iv.next36 = add nuw nsw i64 %indvars.iv35, 5</div><div> %cmp = icmp slt i64 %indvars.iv.next36, %1</div><div> br i1 %cmp, label %for.body, label %for.end</div></div><div><br></div><div> for.end: ; preds = %for.body</div><div> %cmp729 = icmp sgt i32 %0, 5</div><div> br i1 %cmp729, label %<a href="http://for.body8.lr.ph" target="_blank">for.body8.lr.ph</a>, label %for.end17</div><div><br></div><div><a href="http://for.body8.lr.ph" target="_blank">for.body8.lr.ph</a>: ; preds = %for.end</div><div> %sub = add nsw i32 %0, -5</div><div> %4 = sext i32 %sub to i64</div><div> br label %for.body8</div><div><br></div><div> for.body8: ; preds = %<a href="http://for.body8.lr.ph" target="_blank">for.body8.lr.ph</a>, %for.body8</div><div><b>; 4 = MemoryPhi({<a href="http://for.body8.lr.ph" target="_blank">for.body8.lr.ph</a>,1},<wbr>{for.body8,2})</b></div><div> %indvars.iv = phi i64 [ 0, %<a href="http://for.body8.lr.ph" target="_blank">for.body8.lr.ph</a> ], [ %indvars.iv.next, %for.body8 ]</div><div> %arrayidx10 = getelementptr inbounds i32, i32* %a, i64 %indvars.iv</div><div><b>; MemoryUse(4)</b></div><div> %5 = load i32, i32* %arrayidx10, align 4, !tbaa !2</div><div> %arrayidx12 = getelementptr inbounds i32, i32* %d, i64 %indvars.iv</div><div>; MemoryUse(4)</div><div> %6 = load i32, i32* %arrayidx12, align 4, !tbaa !2</div><div> %mul = mul nsw i32 %6, %5</div><div> %arrayidx14 = getelementptr inbounds i32, i32* %e, i64 %indvars.iv</div><div><b>; 2 = MemoryDef(4)</b></div><div> store i32 %mul, i32* %arrayidx14, align 4, !tbaa !2</div><div> %indvars.iv.next = add nuw nsw i64 %indvars.iv, 5</div><div> %cmp7 = icmp slt i64 %indvars.iv.next, %4</div><div> br i1 %cmp7, label %for.body8, label %for.end17 </div><div><br></div><div><br></div><div>I have highlighted the interesting lines in bold.</div><div><br></div><div>I was interested in the use of array "a" in the second loop and and wanted to check if memorySSA would show the reaching definitions for these uses to emanate from the definitions in 1 = MemoryDef(3)<b> </b> and, indeed, the MemoryUse(4) corresponding to the use of "a" shows the reaching definition to be from the MemoryPhi node 4, which, in turn has one of its reaching definitions as 1 = MemoryDef(3). But this MemoryPHi node also has another reaching definition which is 2 = MemoryDef(4) which corresponds to the definition of array e in the second loop. </div><div><br></div></div></blockquote></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>Yes, that is correct.</div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div></div><div>This seems to make the MemorySSA form imprecise because it seems to indicate that the use of "a" in the second loop could be having a reaching definition from the definition of "a" in the first loop or the definition of "e" in the second loop (through the MemoryPhi). I would have expected only the first reaching definition to be inferred.</div></div></blockquote><div><br></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>If AA could prove it, MemorySSA would have a MemoryUse(1) instead.</div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><br></div><div>Am I mis-interpreting the information here or mis-understanding the capabilities of MemorySSA? If not, can someone explain why the information is imprecise? Maybe the underlying alias analysis is unable to disambiguate the different arrays? But I would have thought that this would not be a difficult case for alias analysis.</div></div></blockquote><div><br></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>Here, the underlying AA is unable to distinguish, AFAICT, after some transformation.</div><div><br></div><div>clang -c -o test_clang_out.ll -emit-llvm -O3 test.c -S<br></div><div>bin/opt -print-memoryssa -debug test_clang_out.ll<br></div><div><br></div><div>(note lack of other passes):</div><div><div><br></div><div>; <label>:15: ; preds = %15, %8</div><div>; 3 = MemoryPhi({%8,liveOnEntry},{%<wbr>15,1})</div><div> %16 = phi i64 [ 0, %8 ], [ %23, %15 ]</div><div> %17 = getelementptr inbounds i32, i32* %<a href="https://maps.google.com/?q=1,+i64&entry=gmail&source=g">1, i64</a> %16</div><div>; MemoryUse(liveOnEntry)</div><div> %18 = load i32, i32* %17, align 4, !tbaa !2</div><div> %19 = getelementptr inbounds i32, i32* %<a href="https://maps.google.com/?q=2,+i64&entry=gmail&source=g">2, i64</a> %16</div><div>; MemoryUse(liveOnEntry)</div><div> %20 = load i32, i32* %19, align 4, !tbaa !2</div><div> %21 = add nsw i32 %20, %18</div><div> %22 = getelementptr inbounds i32, i32* %0, i64 %16</div><div>; 1 = MemoryDef(3)</div><div> store i32 %21, i32* %22, align 4, !tbaa !2</div><div> %23 = add nuw nsw i64 %16, 5</div><div> %24 = icmp slt i64 %23, %9</div><div> br i1 %24, label %15, label %10</div><div><br></div><div>; <label>:25: ; preds = %25, %12</div><div>; 4 = MemoryPhi({%12,1},{%25,2})</div><div> %26 = phi i64 [ 0, %12 ], [ %33, %25 ]</div><div> %27 = getelementptr inbounds i32, i32* %0, i64 %26</div><div>; MemoryUse(1)</div><div> %28 = load i32, i32* %27, align 4, !tbaa !2</div><div> %29 = getelementptr inbounds i32, i32* %<a href="https://maps.google.com/?q=3,+i64&entry=gmail&source=g">3, i64</a> %26</div><div>; MemoryUse(liveOnEntry)</div><div> %30 = load i32, i32* %29, align 4, !tbaa !2</div><div> %31 = mul nsw i32 %30, %28</div><div> %32 = getelementptr inbounds i32, i32* %<a href="https://maps.google.com/?q=4,+i64&entry=gmail&source=g">4, i64</a> %26</div><div>; 2 = MemoryDef(4)</div><div> store i32 %31, i32* %32, align 4, !tbaa !2</div><div> %33 = add nuw nsw i64 %26, 5</div><div> %34 = icmp slt i64 %33, %14</div><div> br i1 %34, label %25, label %35</div></div><div><br></div><div><br></div><div>Note memoryuse reaching back through memoryphi.</div><div><br></div><div><br></div><div>MemorySSA is deliberately imprecise for def-def relationships, but this is not the cause of your issue. Yours is caused by AA not being able to distinguish anymore.</div><div><br></div><div><br></div></div></div></div></div></div><span class="">
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
</span></blockquote></div><div class="HOEnZb"><div class="h5"><div dir="ltr">-- <br></div><div class="m_449714680173027410gmail_signature" data-smartmail="gmail_signature"><div dir="ltr">Sending this from my phone, please excuse any typos!</div></div>
</div></div></blockquote></div><br></div>