<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; color: rgb(0, 0, 0); font-size: 14px; font-family: Calibri, sans-serif;">
<div>Thanks for comments. Here's the bug report: <a href="https://llvm.org/bugs/show_bug.cgi?id=27478">https://llvm.org/bugs/show_bug.cgi?id=27478</a></div>
<div><br>
</div>
<span id="OLK_SRC_BODY_SECTION">
<div style="font-family:Calibri; font-size:11pt; text-align:left; color:black; BORDER-BOTTOM: medium none; BORDER-LEFT: medium none; PADDING-BOTTOM: 0in; PADDING-LEFT: 0in; PADDING-RIGHT: 0in; BORDER-TOP: #b5c4df 1pt solid; BORDER-RIGHT: medium none; PADDING-TOP: 3pt">
<span style="font-weight:bold">From: </span>Hal Finkel <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>><br>
<span style="font-weight:bold">Date: </span>Wednesday, April 20, 2016 at 9:20 PM<br>
<span style="font-weight:bold">To: </span>Taewook Oh <<a href="mailto:twoh@fb.com">twoh@fb.com</a>><br>
<span style="font-weight:bold">Cc: </span>via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<span style="font-weight:bold">Subject: </span>Re: [llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?<br>
</div>
<div><br>
</div>
<div><style type="text/css">p { margin: 0; }</style>
<div>
<div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000">
<br>
<hr id="zwchr">
<blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;">
<b>From: </b>"Taewook Oh via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>To: </b>"via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>Sent: </b>Friday, April 15, 2016 3:22:27 PM<br>
<b>Subject: </b>[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?<br>
<br>
<div>Hello all, </div>
<div><br>
</div>
<div>I observed that BasicAA alias query returns PartialAlias between different fields of a structure. Following is the test program and -print–all-alias-modref-info output:</div>
<div><br>
</div>
<div>---</div>
<div><br>
</div>
<div>; test.ll</div>
<div>
<div>target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"</div>
<div>target triple = "x86_64-unknown-linux-gnu"</div>
<div><br>
</div>
<div>%"type" = type { [10 x i32], i64 }</div>
<div><br>
</div>
<div>define void @test(%"type"* %base) {</div>
<div>entry:</div>
<div> %int = getelementptr inbounds %"type", %"type"* %base, i64 0, i32 1</div>
<div> %arr_first = getelementptr inbounds %"type", %"type"* %base, i64 0, i32 0, i64 0</div>
<div> %arr_last = getelementptr inbounds %"type", %"type"* %base, i64 0, i32 0, i64 9</div>
<div id="DWT19680"> %arr_oob = getelementptr inbounds %"type", %"type"* %base, i64 0, i32 0, i64 10 ; out-of-bound access</div>
</div>
</blockquote>
This is okay. Even for an inbounds GEP, addressing one-past-the-end of the array is allowed.<br>
<br>
<blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;">
<div>
<div></div>
<div> br label %loop</div>
<div><br>
</div>
<div>loop:</div>
<div> %index = phi i64 [ 0, %entry ], [ %inc, %loop ]</div>
<div><br>
</div>
<div> %arr_index = getelementptr inbounds %"type", %"type"* %base, i64 0, i32 0, i64 %index</div>
<div><br>
</div>
<div> %inc = add i64 %index, 1</div>
<div> %cmp = icmp ult i64 %inc, 10</div>
<div> br i1 %cmp, label %loop, label %exit</div>
<div><br>
</div>
<div>exit:</div>
<div> ret void</div>
<div>}</div>
</div>
<div><br>
</div>
<div>; opt < test.ll –basicaa -aa–eval -print-all-alias-modref-info -disable-output</div>
<div><br>
</div>
<div>
<div> PartialAlias: %type* %base, i64* %int</div>
<div> MustAlias: %type* %base, i32* %arr_first</div>
<div> NoAlias: i32* %arr_first, i64* %int</div>
<div> PartialAlias: %type* %base, i32* %arr_last</div>
<div> NoAlias: i32* %arr_last, i64* %int</div>
<div> NoAlias: i32* %arr_first, i32* %arr_last</div>
<div> PartialAlias: %type* %base, i32* %arr_oob</div>
<div> MustAlias: i32* %arr_oob, i64* %int</div>
<div> NoAlias: i32* %arr_first, i32* %arr_oob</div>
<div> NoAlias: i32* %arr_last, i32* %arr_oob</div>
<div> PartialAlias: %type* %base, i32* %arr_index</div>
<div> PartialAlias: i32* %arr_index, i64* %int</div>
<div> PartialAlias: i32* %arr_first, i32* %arr_index</div>
<div> PartialAlias: i32* %arr_index, i32* %arr_last</div>
<div> PartialAlias: i32* %arr_index, i32* %arr_oob</div>
<div>===== Alias Analysis Evaluator Report =====</div>
<div> 15 Total Alias Queries Performed</div>
<div> 5 no alias responses (33.3%)</div>
<div> 0 may alias responses (0.0%)</div>
<div> 8 partial alias responses (53.3%)</div>
<div> 2 must alias responses (13.3%)</div>
<div> Alias Analysis Evaluator Pointer Alias Summary: 33%/0%/53%/13%</div>
<div> Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!</div>
</div>
<div><br>
</div>
<div>---</div>
<div><br>
</div>
<div id="DWT19697">As you can see, BasicAA query returns PartialAlias for %arr_index and %int. Does anyone know if it is by design to be conservative in case of undefined behavior (such as out-of-bound array access)? It seems that gcc-4.9 alias analysis tells
that there is no alias between %arr_index and %int. </div>
</blockquote>
Please file a bug report:<br>
<br>
1. This is a correctness bug because the result should not be PartialAlias, but MayAlias. PartialAlias should be returned only in cases where we can prove there is a partial overlap. In this case, we can't.<br>
<br>
2. We're also missing an analysis opportunity here. We should be able to prove that %index is never greater than 9, which should be enough to provide a NoAlias result.<br>
<br>
As a test, you might try running with -scev-aa and see if that gets this case.<br>
<br>
-Hal<br>
<blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;">
<div></div>
<div><br>
</div>
<div>Thanks,</div>
<div>Taewook</div>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote>
<br>
<br>
<br>
-- <br>
<div><span name="x"></span>Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<span name="x"></span><br>
</div>
</div>
</div>
</div>
</span>
</body>
</html>