> The algorithm maintains a may-point-to graph. Unfortunately the
> doesn't delete an "A-->B" edge when there's a strong update of "A" but
> value copied into "A" isn't a pointer. So the interpretation of "A"
> 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"?
Sorry, I can see how my phrasing raised a red flag.
The original version of the algorithm I'm looking at was designed to
analyze C source code, not LLVM IR. I'm in the process of adapting its
dataflow equations for IR.
The algorithm assumes that a correct C program can't just compute pointer
values *ex nihilo*; that they can only by obtained from certain syntactic
structures like variable declarations, or calls to *malloc*, or pointer
literals. The AA algorithm reckons that dereferencing a runtime value
obtained by some other mechanism is so likely to be a bug, that they can
skip worrying about it.
The AA algorithm uses dataflow analysis to monitor the possible propagation
of those values through the program code, and it represents those flows by
updates to the may-point-to graph. If at some code point CP, a
may-point-to graph vertex "B" has no outbound edges, that's equivalent to
saying that the AA has concluded the runtime memory modeled by "B" does not
contain any pointer that a correct program has any business trying to
So to restate my point in the earlier email: if there's a strong-update of
the form "*A = 42;" (in C parlance), it would be nice to have this AA
algorithm remove any may-point-to graph edges originating at "A" at that
point. But, for the sake of efficiency (in the author's judgment), such
assignments are simply ignored by the dataflow equations. And so any
existing may-point-to edges originating at "A" are allowed to remain in
> 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.
Published versions are often ... wrong, not well engineered, etc
I'm not dead-set against modifying it, I'm just biased against doing it
without a good reason. I'm relatively new to implementing AA algorithms,
and the author seems to have put a great deal of thought into this
algorithm. So I'm trying to follow a policy of "If it's not broken, don't
fix it." Also, the more I can remain faithful to the algorithm's original
writeup, the less I'm on the hook to write my own documentation for my
> 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
> 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
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.
Thanks, will do. I appreciate the feedback!