Daniel Berlin dberlin at dberlin.org
Thu Mar 7 08:42:19 PST 2013

```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.

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

```