<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Aug 21, 2017 at 2:19 PM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</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 bgcolor="#FFFFFF"><div><div class="gmail-h5">
<div class="gmail-m_479059396580791321moz-cite-prefix">On 08/20/2017 08:47 PM, Xinliang David
Li via llvm-dev wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">Hi Ivan, thanks for writing it up. This is a pretty
long thread, and there are many good points brought up in the
heated discussions. Here is my take on many of the points that
have been mentioned:
<div><br>
</div>
<div>1) The type based aliasing IR annotation should be generic
enough to represent aliasing constraints for any frontend
languages; </div>
<div>2) The offset based aliasing rules and type based aliasing
rule have a lot in common. The difference is that the offset
based aliasing rule require that the two accesses to have same
base pointer value, while type based aliasing rules specifies
whether two base pointers can possibly point to the same
underlying object, and if yes, what are the legally allowed
offsets at which the two base pointers can be aligned;</div>
<div>3) Type specific information is usually not interesting to
offset based aliasing rules if offsets can be folded into
constant. It is when there is a variable involved in the
indexing that makes language guaranteed bounds information
also useful.</div>
<div><br>
</div>
<div>Given the above, the type based aliasing annotation can be
represented as list of <base_type, offset> pairs, as
well as the original base pointer type in the source. Each
pair represent a way to access the memory legally allowed by
the language -- this field can be accessed with a base pointer
of type 'base_type' at 'offset'.</div>
<div><br>
</div>
<div>For instance:</div>
<div><br>
</div>
<div>struct A { struct B { struct C {int m, n; } c1; int i, j; }
b1, b2; int k; };</div>
<div>struct A*ap;</div>
<div>struct B *bp;</div>
<div>struct C *cp;</div>
<div>int *ip;</div>
<div><br>
</div>
<div>(1) access ap->b2.c1.n has following annotation:</div>
<div><br>
</div>
<div> {A*, [ <A, 12>, <B, 4>, <C,4>, <int,
0>] }</div>
<div><br>
</div>
<div>What it means </div>
<div> </div>
<div> Access (1) may only be aliased with another access if
that access's base pointer is type A and the offset is 12, or
type B at offset 4, or type C at offset 4, or type int at
offset 0. Also access (1) is originally accessed via path
<A, 12>.</div>
<div><br>
</div>
<div>(2) access ap->k has only</div>
<div> </div>
<div> {A*, [<A, 16>, <int, 0>}</div>
<div><br>
</div>
<div>(3) access bp->c1.n has</div>
<div> </div>
<div> {B*, [<B, 4>, <int, 0>]}</div>
<div><br>
</div>
<div>(4) Access bp->j has</div>
<div><br>
</div>
<div> {B*, [<B, 12>, <int, 0>]}</div>
<div><br>
</div>
<div>(5) access *ip (implicitly) has</div>
<div><br>
</div>
<div> {int *, <int, 0>}</div>
<div><br>
</div>
<div>From the above, we can see (5) is aliased with all the
above, and (3) is also aliased with (1). <br>
</div>
</div>
</blockquote>
<br></div></div>
This sounds reasonable. It is almost exactly an encoding of our
current TBAA scheme where, instead of causing the client to walk up
the tree, we explicitly provide the path up the tree at each access.
It should also handle unions naturally because, regardless of the
"currently live" union member, all potentially-aliasing accesses
will have an entry in their list like <U, offset>.</div></blockquote><div><br></div><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 bgcolor="#FFFFFF"><span class="gmail-"><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div><br>
</div>
<div>With this representation, the type based alias rules
implementation becomes: given two memory accesses, align the
pointer of one access to the other. If it can be done, they
are not aliased. If yes, the use the same
base+offset+access_size aliasing rule to check overlapping.</div>
</div>
</blockquote>
<br></span>
I'm not entirely sure what you mean by aligning pointers (and why
aligning them would mean they couldn't alias). Can you please
explain?</div></blockquote><div><br></div><div>I had a typo there. I meant 'if it can not be done, they are not aliased ...".</div><div><br></div><div>By aligning pointers, I meant align the base pointer of another access with one of the allowed types in the access list.</div><div><br></div><div>Given:</div><div><br></div><div>Access (1) {A*, [ <A, 12>, <B, 4>, <C,4>, <int, 0>] } and access (2) {B*, [<B, 4>, <int, 0>]}, we know that access (2)'s base pointer type is 'B*'. Its base pointer typed then needs to be matched up against the types in Access (1)'s list. In this case, it finds a match, so (2)'s base pointer will be aligned to point to the type B subobject of the access (1). After alignment, we then compare offset and access size to determine overlapping.</div><div><br></div><div>David</div><div><br></div><div><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF"><span class="gmail-"><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div><br>
</div>
<div>For languages that have rules about access bounds of member
arrays, the offset information can be replaced with offset +
range. By default, the range is the size of the array type.</div>
</div>
</blockquote>
<br></span>
Yes, and I'd certainly like to include this information going
forward (along with some flag saying whether it's legal to
over/under index the field).<br>
<br>
Thanks again,<br>
Hal<div><div class="gmail-h5"><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div><br>
</div>
<div>David</div>
<div><br>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Wed, Aug 16, 2017 at 11:59 AM,
Ivan A. Kosarev 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">Hal,
Daniel,<br>
<br>
Thanks for your responses. Here's a quick formal
introduction to the proposed approach follows. I also
attached a couple files to put some visibility on
implementation details. We'd love to hear from you
gentlemen and LLVM community in general on how this fits
what you know about TBAA.<br>
<br>
<br>
Overview<br>
========<br>
<br>
With this writing we propose a new approach to the TBAA
mechanism<br>
designed to overcome current issues such as:<br>
- inability to represent accesses to aggregates, unions,
union<br>
members, bit fields, fields of union and aggregate
types,<br>
including array members and<br>
- lack of a mean to identify user types defined in
different<br>
translation units.<br>
<br>
As of today, we have a local patch that implements this
approach.<br>
This new implementation is known to be at least as
functionally<br>
complete as the current one. Additionally, with this patch
on top<br>
we improved SROA to propagate TBAA information, thus
making sure<br>
the new features work as expected.<br>
<br>
We should be able to upload that patch for review in a few
days.<br>
<br>
<br>
The Approach<br>
============<br>
<br>
With the proposed approach we represent accesses as
sequences<br>
that contain all accessed types and fields in order. For
example<br>
for this access:<br>
<br>
struct T { union U { struct S { int i1, i2; } s1, s2; }
u1, u2; } t;<br>
t.u1.s1.i1<br>
<br>
we generate an access sequence of the form:<br>
<br>
[T, T::u1, U, U::s1, S, S::i1, int]<br>
<br>
An array is allowed to overlap with any object of its
element<br>
type, including other arrays of the same element type, so
an<br>
access to an array element is represented as an access to
an<br>
object of the element type:<br>
<br>
int a[7];<br>
a[5]<br>
<br>
[int]<br>
<br>
In case of a multi-dimensional array this rule applies<br>
recursively:<br>
<br>
int a[7][9];<br>
a[3][5]<br>
<br>
[int]<br>
<br>
For member arrays we specify the member field as usual so
we can<br>
distinct it from other array members:<br>
<br>
struct S { int a[7], b[9]; } s;<br>
s.a[5]<br>
<br>
[S, S::a, int]<br>
<br>
Similarly to the scalar and struct-path approaches, we
consider<br>
every type to be a member of a type group it explicitly
refers<br>
to. Here's how the tree that describes relations between
type<br>
groups would look like for the example above:<br>
<br>
<tbaa_root><br>
|- <may_alias><br>
|- <representation_byte><br>
|-<structure><br>
| |- S<br>
|- int<br>
<br>
The <vtable_pointer> group has a special meaning and
is used to<br>
describe accesses to virtual table pointers. Similarly,
the<br>
<union> type group includes all union types and used
by the TBAA<br>
implementation to distinct union types from other types.
The<br>
<may_alias> group is technically equivalent to<br>
<representation_byte> and supposed to be a group for<br>
may_alias-marked types.<br>
<br>
For two given access sequences we can determine if the
accessed<br>
objects are allowed to overlap by the rules of the input<br>
language. Here's the list of rules complete enough to
support C<br>
and C++. Ellipsis elements denote sequences of zero or
more<br>
elements. For other input languages more rules can be
supported,<br>
if necessary.<br>
<br>
[X...] is allowed to overlap with [S1..., X..., S2...]<br>
and the most generic access sequence is [X...].<br>
<br>
[X1..., X2...] is allowed to overlap with [S1..., X1...]<br>
with the most generic access sequence to be [X1...].<br>
<br>
[X1..., U, U::m1, X2...] is allowed to overlap with<br>
[S1..., X1..., U, U::m2, S2...]<br>
for a union U of an unknown effective type, provided m1
!= m2<br>
and the most generic access sequence is [X1..., U].<br>
<br>
If neither of the given sequences contains the leading
access<br>
type of the other, then they are allowed to overlap if the<br>
leading access type of one sequence is a direct or
indirect field<br>
of the final access type of the other sequence and then
the most<br>
generic access sequence consists of a single element,
which is<br>
that final access type.<br>
<br>
For the purpose of determining whether one type is a
direct or<br>
indirect member of another type unions are considered to
have no<br>
members as accesses to members of unions are only allowed
to<br>
overlap if they have the base union object explicitly
specified.<br>
<br>
Otherwise, given sequences overlap if there is a type
group that<br>
includes both the leading access types and the most
generic<br>
access sequence consists of the smallest common type group
as its<br>
only element.<br>
<br>
See the attached TypeBasedAliasAnalysis.cpp file and
specifically<br>
the MatchAccessSequences() function for how these rules
can be<br>
implemented.<br>
<br>
TBAA information is encoded as metadata nodes, as usual.
Load and<br>
store instructions refer to access sequences:<br>
store %struct.T* %p, %struct.T** %p.addr, align 8, !tbaa
!11<br>
<br>
A type node is either a terminal type node that names a
root type<br>
group:<br>
!0 = !{ !"<tbaa_root>" }<br>
<br>
or a non-terminal type node that names a type and refers
to a<br>
type group it belongs to:<br>
!1 = !{ !0, !"int" }<br>
<br>
Record types also refer to their field descriptors:<br>
!3 = !{ !0, !"S", !9 }<br>
<br>
An access node is either a terminal access node that
refers to<br>
the corresponding access type:<br>
!5 = !{ !1 }<br>
!9 = !{ !3 }<br>
<br>
or a member node that refers to a structure/class or union
field<br>
descriptor and a subsequent access path node:<br>
!7 = !{ !type_group, !field_id, !field_offset,
!field_size }<br>
!11 = !{ !5, !9, !7 }<br>
<br>
For a field node the first element refers to its type. The<br>
purpose of other elements is to make the field node
unique. Their<br>
meaning is unspecified. Currently the other members for C
and C++<br>
are the field name, bit offset and bit size of the member,
but<br>
this may change in future and front ends for other input<br>
languages may act differently, so TBAA implementation in
the<br>
codegen shall not rely on specific shape or meaning of
these<br>
elements.<br>
<br>
For types that are interchangeable for purposes of TBAA it
is<br>
important to encode them identically so that descriptors
of<br>
interchangeable types defined in different modules merge
into<br>
same metadata nodes.<br>
<br>
Structure/class fields are specified in the order of
declaration.<br>
For union fields there is a canonical order that guarantee
that<br>
definitions of the same union type will result in
identical<br>
descriptors regardless of the order of member
declarations.<br>
Currently we sort union fields with key (field_id,
field_offset,<br>
field_size).<br>
<br>
C++ tagged types with no linkage are to be encoded as
"distinct"<br>
nodes to guarantee their uniqueness.<br>
<br>
The support for !tbaa.struct information is to be replaced
with<br>
plain !tbaa tags representing accesses to the
corresponding<br>
record types.<br>
<br>
Another attached file, the tbaa.cpp one, is a test case
that can<br>
give an idea what encoded TBAA metadata may look like.<br>
<br>
<br>
Space and Performance Analysis<br>
==============================<br>
<br>
In terms of metadata size, with the new approach we
generate<br>
about 15% more of metadata nodes. The ratio of the total
number<br>
of TBAA nodes to the amount of code remains very low,
meaning the<br>
size of TBAA metadata is unlikely to be a problem any time
soon.<br>
<br>
From the performance perspective, the proposed approach
differs<br>
from the current one in that:<br>
- it does not traverse through record types if one of the
access<br>
sequences to match contains the leading access type of
the<br>
other and<br>
- it never traverses union types.<br>
<br>
We thus expect that the new approach is at least as
efficient as<br>
the current one. Our experiments do not indicate any
sensible<br>
difference in performance between the implementations.<span class="gmail-m_479059396580791321HOEnZb"><font color="#888888"><br>
<br>
-- <br>
<br>
</font></span><br>
______________________________<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>
<br>
</blockquote>
</div>
<br>
</div>
</div>
<br>
<fieldset class="gmail-m_479059396580791321mimeAttachmentHeader"></fieldset>
<br>
<pre>______________________________<wbr>_________________
LLVM Developers mailing list
<a class="gmail-m_479059396580791321moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a class="gmail-m_479059396580791321moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
</div></div><span class="gmail-"><pre class="gmail-m_479059396580791321moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</span></div>
</blockquote></div><br></div></div>