[LLVMdev] tbaa metadata representation

[Tran Ma]

On 07/03/2013, at 1:45 AM, Daniel Berlin <dberlin at dberlin.org> wrote:

> On Wed, Mar 6, 2013 at 4:23 AM, Tran Ma <tranma at cse.unsw.edu.au> wrote:
>> It was derived from what I read in Dan Gohman's slides about one of the
>> possible forms a type DAG could take. Your forest is what we should get in
>> the current tree representation (I believe), so when we have a load/store
>> involving x, we can only annotate the instruction with the x node from the
>> tree rooted at a or c. If we choose the tree at a, we'd lose the information
>> that x does not alias z, and if we choose c, we won't know that x does not
>> alias y. However if we use a graph, such as this:
>> 
>>   a     b
>>  / \   / \
>> v   v v   v
>> x     y     z
>> ^         ^
>>  \__ c __/
>> 
>> Then there wouldn't be a problem. This kind of graph was also described in
>> the slides as one of the possible representations, I don't know what was
>> eventually decided upon.
> 
> The tree is what is currently used, but i'm also not sure the graph
> from his slides will really work.
> We'll see.

The second approach (titled "a more precise type DAG") looks promising, I am convinced that a graph is what we need (the other suggestion was to make it possible to attach a list of metadata nodes to instructions, which was deemed too cumbersome), I'm trying to convince myself about the A and D part.

> You can't actually form cyclic graphs if you follow the typing rules,
> because mutually recursive types are impossible.
> However, It's entirely possible that Dan has described a
> representation/implementation that causes cycles :)

I believe you are right. I'm not saying cycles are bad, for my use case I don't actually care whether the representation is acyclic or not, it's just to make sure we don't make the graph more restrictive than it has to be.

>> The reason why I assumed direction wasn't needed is because I thought the
>> relation `alias` was symmetric: if x aliases y then y alias x in all cases.
>> Is this the case for tbaa?
> 
> It should not be, but LLVM may have done this :)
> See the difference in GCC's alias.c between alias_sets_conflict_p and
> alias_set_subset_of_p.
> 
> You can see where the subset (one-way checking) is used in tree-ssa-alias.c
> 
> If LLVM does always use this rule, and plans on keeping it that way,
> you are correct that there is no point in having a directed graph at
> all, since you aren't using the direction.

That's quite strange. I'm not too familiar with the implementation, but it sounds like keeping the direction is easier than dropping it (despite what the docs say and the symmetry of `alias`), so a change to using DAGs is probably most likely to be accepted. (How do I go about doing this by the way? Do it and send someone a patch?)

Thanks heaps,
--
Tran (orodru.in)