<div dir="ltr">Nice proposal.<div><br></div><div style>A possibly simplified way of doing TBAA is:</div><div style>1) decompose an access into a 3-tuples: <BaseType, AccessType, BitOffset> -- there is no need to remember the full access path.</div>
<div style>2) If the access types are incompatible, return noAlias (scalar TBAA rule)</div><div style>3) if there is no containment relationship between two BaseTypes, return noAlias</div><div style>4) Otherwise, align the the enclosed base type into the enclosing type (for each enclosed instance), and adjust the offset. If there is no overlap, return noAlias, otherwise return mayAlias.</div>
<div style><br></div><div style>For instance, "C::b1.a.y" AND "D::c.b2.a.x</div><div style><br></div><div style>C::b1.a.y --> <C, int, 32> </div><div style>D::c.b2.a.x --> <D, int, 96></div>
<div style><br></div><div style>Base Type C is enclosed in D, so the first access is normalized to <D, int, 32> which does not overlap with <D, int, 96>.</div><div style><br></div><div style>For more complicated cases, such as p->a[i].x.b[j].y, TBAA can choose to normalize the access via projection before creating the tuple --> p->a[0].x.b[0].y. Make sure MustAlias is not wrongly returned for this case.</div>
<div style><br></div><div style>Cheers,</div><div style><br></div><div style>David</div><div style><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Mar 27, 2013 at 1:11 PM, Manman Ren <span dir="ltr"><<a href="mailto:mren@apple.com" target="_blank">mren@apple.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
Hello,<br>
<br>
After discussions with Daniel, Dan and others, here is an updated proposal for struct-access-path aware TBAA.<br>
<br>
Given an example<br>
struct A {<br>
int x;<br>
int y;<br>
};<br>
struct B {<br>
A a;<br>
int z;<br>
};<br>
struct C {<br>
B b1;<br>
B b2;<br>
int *p;<br>
};<br>
struct D {<br>
C c;<br>
};<br>
<br>
The purpose of struct-path-aware TBAA is to say<br>
"C::b1.a" will alias with "B::a.x", "C::b1.a" will alias with "B",<br>
"C::b1.a" does not alias with "D::c.b2.a.x".<br>
"A::x" does not alias with "A::y"<br>
We can potentially disambiguate aggregate accesses and scalar accesses.<br>
<br>
The current scalar TBAA will say<br>
"C::b1.a.x" will alias with "D::c.b2.a.x" since both are accesses to int.<br>
"A::x" will alias with "A::y"<br>
<br>
This proposal is about the format of metadata and how to implement alias queries.<br>
--------- Option A<br>
A> metadata for the type DAG<br>
1> the existing scalar nodes<br>
!0 = metadata !{metadata !"any pointer", metadata !1}<br>
!1 = metadata !{metadata !"omnipotent char", metadata !2}<br>
!2 = metadata !{metadata !"Simple C/C++ TBAA"}<br>
!4 = metadata !{metadata !"int", metadata !1}<br>
2> the struct nodes<br>
A struct node has a unique name plus a list of field types<br>
For example, struct node for "C" should look like<br>
!5 = metadata !{"C", metadata !3, metadata !3, metadata !0}<br>
where !3 is the struct node for "B"<br>
<br>
The type DAG for the example:<br>
int <------------- A <- B <-- C <-- D<br>
int <-------------------- B<br>
any pointer <--------------- C<br>
<br>
B> We call metadata attached to scalar accesses scalar tags and metadata<br>
attached to aggregate accesses aggregate tags.<br>
Each tag can be a sequence of field accesses and nodes in the type DAG.<br>
For example, the tag for "C::b2.a.x" is<br>
!7 := [ "tbaa.path", !C, "C::b2", !B, "B::a", !A, "A::x", !int ] ;C::b2.a.x<br>
where !C, !B, !A are metadata nodes in the type DAG, "C::b2" "B::a" "A::x" are strings.<br>
C> alias(x, y) = alias_rule(x, y) or alias_rule(y, x), where alias_rule(x, y) is<br>
if the first element of 'x' does not enclose the first element of 'y'<br>
return NoAlias<br>
if the last element of 'x' encloses the first element of 'y' via type DAG,<br>
return Alias<br>
Check the first element of 'y', if it is not in 'x', return NoAlias<br>
Repeat until we reach the end of either 'x' or 'y'<br>
Check the next element of 'y' with the next element of 'x'<br>
if not the same, return false.<br>
<br>
-------------- Option B<br>
Option B is to include offset of each field in the type DAG and let tag<br>
be offset based.<br>
A> metadata for the type DAG<br>
1> the existing scalar nodes<br>
2> the struct nodes<br>
A struct node has a unique name plus a list of pairs (offset, field type)<br>
For example, struct node for "C" should look like<br>
!5 = metadata !{"C", 0, metadata !3, 12, metadata !3, 24, metadata !0}<br>
where !3 is the struct node for "B"<br>
The type DAG for the example:<br>
int <- 0 <- A<br>
int <- 4 <- A <- 0 <- B <- 0 <- C <- 0 <- D<br>
int <-------------- 8 <- B <- 12 <- C<br>
any pointer <--------------- 24 <- C<br>
<br>
B> The tag will be (outermost struct type node, offset, size, the last type node)<br>
For example, the tag for C::b2.a.x will be<br>
!7 = [ "tbaa.offset", !C, 12, 4, !int] ;C::b2.a.x<br>
The last field of the tag is to handle alias(D::c, A::x), the tags will be<br>
[!D, 0, 32, !C] and [!A, 0, 4, !int], we only need to check whether !C encloses<br>
!A.<br>
<br>
C> Consider access pair "C::b1.a.x" and "D::c.b2.a.x", the tags are [!C, 0, 4, !int]<br>
and [!D, 12, 4, !int].<br>
To check if they alias, we first check if !D encloses !C. If no, we return<br>
NoAlias. Since !D does enclose !C in our example, we start tracing from !D<br>
and follow the edge with the correct offset by<br>
adjusting the offset to be relative to the next node. We will reach C in the<br>
type DAG, now we have a common type node and can compare the (offset, size)<br>
directly. [!D, 12, 4] will be adjusted to [!C, 12, 4], since it does not<br>
overlap with [!C, 0, 4], we say they do not alias.<br>
<br>
alias_rule(x, y) is<br>
if the outermost type of 'x' does not enclose the outermost type of 'y',<br>
return NoAlias<br>
if the last type of 'x' encloses the outermost type of 'y'<br>
return Alias<br>
Start from the outermost type of 'x'<br>
Repeat until we reach the outermost type of 'y'<br>
follow the edge with the correct offset in the type DAG<br>
adjust the offset to be relative to the next node<br>
Compare the adjusted offset, size pair for 'x' against 'y'<br>
if they overlap, return Alias<br>
Otherwise, return NoAlias<br>
<br>
------------------ Comparison<br>
The complexity of alias queries: similar<br>
The space for metadata: option A should require more space because the tag is a<br>
sequence of nodes and strings.<br>
I will work on Option B.<br>
<br>
------------------ Holes<br>
We use BasicAA to perform sanity check. If BasicAA returns MayAlias, TBAA will<br>
kick off with full speed.<br>
<br>
Watch out for cases where the incoming arguments have different types but they<br>
do alias. Scalar TBAA has the same issue but we don't see bugs coming up. If<br>
we see bugs coming up with struct-path aware TBAA, we can do less aggressive<br>
TBAA or apply similar tricks as GCC.<br>
<br>
Scalar TBAA will say NoAlias for the placement new example under<br>
test/Analysis/TypeBasedAliasAnalysis/placement-tbaa.ll.<br>
If we optimize placement-tbaa.ll with -O1 -gvn, BaiscAA will start saying<br>
MustAlias. This may cause problem.<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote></div><br></div>