llvm dev - Oct 2013 - [LLVMdev] dragonegg: switch from old TBAA format to the new struct-path aware TBAA format

Hi Duncan,

I am hoping to remove the support for the old TBAA format soon.
You should be able to switch to the new format by replacing

MDNode *AliasTag = MDHelper.createTBAANode(TreeName, getTBAARoot());

with
MDNode *AliasType = MDHelper.createTBAAScalarTypeNode(TreeName,
getTBAARoot());
MDNode *AliasTag = MDHelper.createTBAAStructTagNode(AliasType, AliasType, 0)

Also replacing
LeafTag->replaceAllUsesWith(getTBAARoot());

with
MDNode *Root = getTBAARoot();
LeafTag->replaceAllUsesWith(MDHelper.createTBAAStructTagNode(Root, Root, 0)

The document is currently at the beginning of TypeBasedAliasAnalysis.cpp. I
am going to update the language ref when struct-path aware TBAA is on by
default.

Let me know if you have any problem with it.

Thanks,
Manman
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131007/05fbe87a/attachment.html>

Hi Manman, thanks for the heads up.  I looked into what it would take to produce
full struct TBAA metadata from the GCC aliasing info (GCC has aliasing info for
struct types, in fact for any type), but it looks kind of tricky.  The problem
is the "offset" field, which doesn't exist in GCC.  In GCC the
aliasing
information forms a DAG, with a node for each type, plus a special root node.
How language types turn into GCC TBAA DAG nodes depends on the language, but
for a simple language like C it is set up like this: scalar types just have an
edge to the root node; struct types have edges to the nodes for the types of
its fields.  This is pretty similar to what you have set up, but there is no
offset, and it is not clear how I can get hold of one in general (I need to
look into this more though).

There are other problems with the offset field too:

(1) many languages have array types.  For these languages it is natural to have
a node for the array type with an edge to the node for the element type.  But
there is no reasonable offset in general: arrays have many elements (all of the
same type) but each at a different offset.  A possibility is to create one node
per element, but since arrays often have thousands of elements this would create
vast amounts of metadata.  There could be an artificial limit: only produce TBAA
info for arrays with less than X elements, but that is a bit nasty.  It would
also mean not producing any TBAA info for array types with variable size that
you can find in some languages.

(2) some languages have struct types with fields at variable offsets (i.e. the
offset is determined by the value of some variable, often the value of another
field in the struct).  As the offset is not a constant, it is not possible to
put it in the metadata.  Not producing TBAA info for these types would be a
pity.

An interesting part of the GCC design is that there is no distinction between
scalar and struct nodes: all nodes are equal.  You can *define* a
"scalar" node
to be one which only has an edge to the root, but they might not correspond to
the scalar types in the original language.  In fact I don't think nodes have
to
have anything to do with a type at all, they seem to be arbitrary cookies.

It's a pity that the LLVM design hardwires in the offset.  It looks like it
has
been designed with only C like languages in mind, which isn't surprising but
is
limiting.  Is the offset field really useful/necessary?

Best wishes, Duncan.

On 08/10/13 02:47, Manman Ren wrote:
> Hi Duncan,
>
> I am hoping to remove the support for the old TBAA format soon.
> You should be able to switch to the new format by replacing
>
> MDNode *AliasTag = MDHelper.createTBAANode(TreeName, getTBAARoot());
>
> with
> MDNode *AliasType = MDHelper.createTBAAScalarTypeNode(TreeName,
getTBAARoot());
> MDNode *AliasTag = MDHelper.createTBAAStructTagNode(AliasType, AliasType,
0)
>
> Also replacing
> LeafTag->replaceAllUsesWith(getTBAARoot());
>
> with
> MDNode *Root = getTBAARoot();
> LeafTag->replaceAllUsesWith(MDHelper.createTBAAStructTagNode(Root, Root,
0)
>
> The document is currently at the beginning of TypeBasedAliasAnalysis.cpp. I
am
> going to update the language ref when struct-path aware TBAA is on by
default.
>
> Let me know if you have any problem with it.
>
> Thanks,
> Manman
>
>
>

On Sat, Oct 12, 2013 at 5:28 AM, Duncan Sands <baldrick at free.fr> wrote:
> Hi Manman, thanks for the heads up.  I looked into what it would take to
> produce
> full struct TBAA metadata from the GCC aliasing info (GCC has aliasing
> info for
> struct types, in fact for any type), but it looks kind of tricky.  The
> problem
> is the "offset" field, which doesn't exist in GCC.  In GCC
the aliasing
> information forms a DAG, with a node for each type, plus a special root
> node.
>
This sound similar to clang's TBAA.

> How language types turn into GCC TBAA DAG nodes depends on the language,
> but
> for a simple language like C it is set up like this: scalar types just
> have an
> edge to the root node; struct types have edges to the nodes for the types
> of
> its fields.

This sounds similar to clang's TBAA as well. Struct types have edges to the
field types, but
we attach an offset for each edge. The TBAA tags also have an access offset
and we can use
the access offset and the DAG to decide the access path for the tag. I
don't know how gcc's
TBAA figures out the access path.

Thanks,
Manman

>  This is pretty similar to what you have set up, but there is no
> offset, and it is not clear how I can get hold of one in general (I need to
> look into this more though).
>
> There are other problems with the offset field too:
>
> (1) many languages have array types.  For these languages it is natural to
> have
> a node for the array type with an edge to the node for the element type.
>  But
> there is no reasonable offset in general: arrays have many elements (all
> of the
> same type) but each at a different offset.  A possibility is to create one
> node
> per element, but since arrays often have thousands of elements this would
> create
> vast amounts of metadata.  There could be an artificial limit: only
> produce TBAA
> info for arrays with less than X elements, but that is a bit nasty.  It
> would
> also mean not producing any TBAA info for array types with variable size
> that
> you can find in some languages.
>
> (2) some languages have struct types with fields at variable offsets (i.e.
> the
> offset is determined by the value of some variable, often the value of
> another
> field in the struct).  As the offset is not a constant, it is not possible
> to
> put it in the metadata.  Not producing TBAA info for these types would be a
> pity.
>
> An interesting part of the GCC design is that there is no distinction
> between
> scalar and struct nodes: all nodes are equal.  You can *define* a
"scalar"
> node
> to be one which only has an edge to the root, but they might not
> correspond to
> the scalar types in the original language.  In fact I don't think nodes
> have to
> have anything to do with a type at all, they seem to be arbitrary cookies.
>
> It's a pity that the LLVM design hardwires in the offset.  It looks
like
> it has
> been designed with only C like languages in mind, which isn't
surprising
> but is
> limiting.  Is the offset field really useful/necessary?
> Best wishes, Duncan.
>
>
> On 08/10/13 02:47, Manman Ren wrote:
>
>> Hi Duncan,
>>
>> I am hoping to remove the support for the old TBAA format soon.
>> You should be able to switch to the new format by replacing
>>
>> MDNode *AliasTag = MDHelper.createTBAANode(**TreeName, getTBAARoot());
>>
>> with
>> MDNode *AliasType = MDHelper.**createTBAAScalarTypeNode(**TreeName,
>> getTBAARoot());
>> MDNode *AliasTag = MDHelper.**createTBAAStructTagNode(**AliasType,
>> AliasType, 0)
>>
>> Also replacing
>> LeafTag->replaceAllUsesWith(**getTBAARoot());
>>
>> with
>> MDNode *Root = getTBAARoot();
>>
LeafTag->replaceAllUsesWith(**MDHelper.**createTBAAStructTagNode(Root,
>> Root, 0)
>>
>> The document is currently at the beginning of
TypeBasedAliasAnalysis.cpp.
>> I am
>> going to update the language ref when struct-path aware TBAA is on by
>> default.
>>
>> Let me know if you have any problem with it.
>>
>> Thanks,
>> Manman
>>
>>
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131014/6161a935/attachment.html>