[LLVMdev] Expressing ambiguous points-to info in AliasAnalysis::alias(...) results?

[Daniel Berlin]

On Sun, Jun 14, 2015 at 9:25 AM, Christian Convey
<christian.convey at gmail.com> wrote:
> Hi all,
>
> I'm playing around with implementing an existing non-LLVM AA algorithm as an
> LLVM AA pass.  I'm looking for suggestions for getting it to fit in
> AliasAnalysis's worldview, so that it might eventually be a candidate for
> inclusion in LLVM.
>
> The algorithm maintains a may-point-to graph.  Unfortunately the algorithm
> doesn't delete an "A-->B" edge when there's a strong update of "A" but the
> value copied into "A" isn't a pointer.  So the interpretation of "A" having
> only one outbound edge (to "B") is a little ambiguous.  It means "'A'
> definitely points to 'B', or 'A' doesn't hold a valid pointer."


Define "valid pointer please"?

>
> This makes it hard for the algorithm to ever return a MustAlias result.  If
> the graph has just two edges, "A-->C" and "B-->C", then the most precise
> answer it could give for "alias(A,B)" would be "MustAlias or NoAlias, I'm
> not sure which".   AFAIK, with the current interface I'd have to return
> "MayAlias" in that case, which is unsatisfying.

So i'm trying to understand what harm would come from returning MustAlias here?
If the value is undef, then we can pick one for which MustAlias is true.
If it's something else, i need to understand how you define "valid pointer".

(I agree there are situations where this would be the wrong answer,
which is why i'm trying to understand what valid pointer means)
>
> One solution would be for me to adapt the algorithm to remove this
> ambiguity.  But if possible I'd like to keep the algorithm as close to the
> published version as possible, so I'd rather find another solution.

Why?
Published versions are often ... wrong, not well engineered, etc :)

>
> Another approach is to add a value to the AliasResult enumeration,
> indicating "MustAlias or NoAlias, I'm not sure which".  But I'm not sure if
> any downstream analyses could make use of a result like that.

Above, you say you want to not return MustAlias.
Here you say it's not clear that any downstream results could make use
of better info.

Before you go and try to figure out what should change, you really
need to actually determine whether the info you have is valuable.

I would do this by finding a pass you think you can improve with your
extra info, and seeing if it improves (add a temporary hack AA
function or something that gives info about this) by giving it must/no
vs may.

If something improves, great, we can figure out whether it's worth the
tradeoffs/etc and help you figure out what to do.
If nothing improves, it may not be worth you spending your time on it.