Hi, I am observing some incorrect behavior in basicaa, wherein two pointers that basicaa should determine to be MustAlias are ending up NoAlias - the other extreme :( I am blaming this on basicaa not handling inttoptr. Here is the relevant IR snippet. -------------------- %sunkaddr36 = ptrtoint %struct.BitParams* %bs to i32 %sunkaddr37 = add i32 %sunkaddr36, 16 %sunkaddr38 = inttoptr i32 %sunkaddr37 to i32* %sunkaddr39 = ptrtoint %struct.BitParams* %bs to i32 %sunkaddr40 = add i32 %sunkaddr39, 16 %sunkaddr41 = inttoptr i32 %sunkaddr40 to i64* --------------------- A query to basicaa: alias(%sunkaddr41, 8, %sunkaddr38, 4) results in a NoAlias return value. The reason is that nothing inside basicaa processes inttoptr; the fall through case of using TBAA (int and long long in this case) is executed and NoAlias is returned as the pointer types are different. I have two questions. 1) Is it safe for basicaa to reason about inttoptr in a manner similar to aliasGEP (using decomposeGEPExpression to symbolically evaluate the pointer). 2) If the answer to the above is no, then shouldn't basicaa treat the above conservatively before it looks at TBAA ? Thanks, Pranav Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
On Thu, Nov 8, 2012 at 6:53 PM, Pranav Bhandarkar <pranavb at codeaurora.org> wrote:> Hi, > > I am observing some incorrect behavior in basicaa, wherein two pointers that > basicaa should determine to be MustAlias are ending up NoAlias - the other > extreme :( > I am blaming this on basicaa not handling inttoptr. Here is the relevant IR > snippet. > -------------------- > %sunkaddr36 = ptrtoint %struct.BitParams* %bs to i32 > %sunkaddr37 = add i32 %sunkaddr36, 16 > %sunkaddr38 = inttoptr i32 %sunkaddr37 to i32* > > > > %sunkaddr39 = ptrtoint %struct.BitParams* %bs to i32 > %sunkaddr40 = add i32 %sunkaddr39, 16 > %sunkaddr41 = inttoptr i32 %sunkaddr40 to i64* > --------------------- > > A query to basicaa: alias(%sunkaddr41, 8, %sunkaddr38, 4) results in a > NoAlias return value. > The reason is that nothing inside basicaa processes inttoptr; the fall > through case of using TBAA (int and long long in this case) is executed and > NoAlias is returned as the pointer types are different. > > I have two questions. > 1) Is it safe for basicaa to reason about inttoptr in a manner similar to > aliasGEP (using decomposeGEPExpression to symbolically evaluate the > pointer).If we can prove the difference between two pointer values is a compile-time constant (in this case, zero), we can return NoAlias/MustAlias/etc. based purely on that. That said, GEP makes special aliasing guarantees which are impossible to reconstruct from inttoptr. -Eli
BasicAA treats it conservatively if used on its own. It will return
mayalias for the two pointers.
TBAA operates based on the guarantee that pointers to different types
cannot alias (think C's strict aliasing rules).
Therein lies its power but also its danger, that is, nothing prevents the
programmer to write code that violates these rules (That's why we have
-fno-strict-aliasing).
So when basica gives up returning mayalias we query tbaa, which will return
- based on strict aliasing rules of our language - noalias.
opt -basicaa -print-alias-sets basicaa.ll -S -o -
Alias Set Tracker: 1 alias sets for 2 pointer values.
AliasSet[0x109808c90, 2] may alias, Mod Pointers: (i64* %sunkaddr4,
18446744073709551615), (i32* %sunkaddr2, 18446744073709551615)
opt -basicaa -tbaa -print-alias-sets basicaa.ll -S -o -
Alias Set Tracker: 2 alias sets for 2 pointer values.
AliasSet[0x112d07cf0, 1] must alias, Mod Pointers: (i64*
%sunkaddr4, 18446744073709551615)
AliasSet[0x112d07d40, 1] must alias, Mod Pointers: (i32*
%sunkaddr2, 18446744073709551615)
define void @basicaatest(%str* %a) {
%sunkaddr1 = ptrtoint %str* %a to i32
%sunkadd = add i32 %sunkaddr1, 4
%sunkaddr2 = inttoptr i32 %sunkadd to i32*
%sunkaddr3 = ptrtoint %str* %a to i32
%sunkadd2 = add i32 %sunkaddr1, 4
%sunkaddr4 = inttoptr i32 %sunkadd2 to i64*
store i64 1, i64* %sunkaddr4, !tbaa !0
store i32 2, i32* %sunkaddr2, !tbaa !2
ret void
}
!0 = metadata !{metadata !"int64", metadata !1}
!1 = metadata !{}
!2 = metadata !{metadata !"int32", metadata !1}
On Thursday, November 8, 2012, Pranav Bhandarkar wrote:>
> 2) If the answer to the above is no, then shouldn't basicaa treat the
above
> conservatively before it looks at TBAA ?
>
>
> Thanks,
> Pranav
>
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted
> by The Linux Foundation
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20121109/218f359b/attachment.html>
On Thu, Nov 8, 2012 at 6:53 PM, Pranav Bhandarkar <pranavb at codeaurora.org>wrote:> Hi, > > I am observing some incorrect behavior in basicaa, wherein two pointers > that > basicaa should determine to be MustAlias are ending up NoAlias - the other > extreme :( > I am blaming this on basicaa not handling inttoptr. Here is the relevant > IR > snippet. > -------------------- > %sunkaddr36 = ptrtoint %struct.BitParams* %bs to i32 > %sunkaddr37 = add i32 %sunkaddr36, 16 > %sunkaddr38 = inttoptr i32 %sunkaddr37 to i32* > > > > %sunkaddr39 = ptrtoint %struct.BitParams* %bs to i32 > %sunkaddr40 = add i32 %sunkaddr39, 16 > %sunkaddr41 = inttoptr i32 %sunkaddr40 to i64* > --------------------- > > A query to basicaa: alias(%sunkaddr41, 8, %sunkaddr38, 4) results in a > NoAlias return value. > The reason is that nothing inside basicaa processes inttoptr; the fall > through case of using TBAA (int and long long in this case) is executed and > NoAlias is returned as the pointer types are different. >>From the perspective of the compiler, this code is making an outrageousdemand of the compiler. It's doing type punning with the pun obscured by casting of pointers to integers. That's considered extreme.> I have two questions. > 1) Is it safe for basicaa to reason about inttoptr in a manner similar to > aliasGEP (using decomposeGEPExpression to symbolically evaluate the > pointer). >GEP's restrictions make it easier to analyze.> 2) If the answer to the above is no, then shouldn't basicaa treat the above > conservatively before it looks at TBAA ? >There's no absolute answer to this question. C-style TBAA is a gray area by its nature. On one hand, it might make sense to have BasicAA use PartialAlias here (and relax its definition). That would be a way to say "I don't know" while still preventing the query from being passed to TBAA. On the other hand, is this code really worth worrying about, or is the right answer to just compile it with -fno-strict-aliasing? If the code is punning with integer-casted pointers, what other things might it be doing that might cause trouble? On the third hand, if you are concerned about getting good optimization, it may be worthwhile to look into rewriting the code to avoid inttoptr and ptrtoint, since these may be suppressing other optimizations besides. Dan -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121109/3899dbba/attachment.html>