[LLVMdev] tbaa metadata representation

[Daniel Berlin]

On Wed, Mar 6, 2013 at 12:31 PM, Tran Ma <tranma at cse.unsw.edu.au> wrote:
> 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.

Well, as you said, if the docs say they always check both directions,
the directioness is unnecessary.
Acyclicness could be guaranteed if necessary, and makes things easier
(otherwise doing walks is hard).



>
>> 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?)

You would normally start a discussion (which Dan i think already did
somewhere), provide motivating examples, and a patch to do it, and
send it to the mailing list.

Note that your idea of undirected graphs and adding transitive edges
would require transitive closure of the graph, which is N^3 initially.
Since metadata can be added at runtime, you would have to redo this
transitive closure on updates to metadata.
In the presence of no-cycles, this is at least N^2 per update. ( there
are significantly more complex data structures that reduce the time,
but ...).


>
> Thanks heaps,
> --
> Tran (orodru.in)