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

[Christian Convey]

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

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.

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.

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.

A third, even uglier solution would be to modify the
AliasAnalysis::alias(...) methods to let the caller indicate whether or not
the supplied Values can be assumed to actually contain pointers.  But this
strikes me as an unreasonable concession to this one AA algorithm's quirks.

Any suggestions for how to proceed?

Thanks, Christian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150614/d02b2822/attachment.html>