<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">> The algorithm maintains a may-point-to graph.  Unfortunately the algorithm<br>
> doesn't delete an "A-->B" edge when there's a strong update of "A" but the<br>
> value copied into "A" isn't a pointer.  So the interpretation of "A" having<br>
> only one outbound edge (to "B") is a little ambiguous.  It means "'A'<br>
> definitely points to 'B', or 'A' doesn't hold a valid pointer."<br>
<br>
<br>
</span>Define "valid pointer please"?<br></blockquote><div><br></div><div>Sorry, I can see how my phrasing raised a red flag.</div><div><br></div><div>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.</div><div><br></div><div>The algorithm assumes that a correct C program can't just compute pointer values <i>ex nihilo</i>; that they can only by obtained from certain syntactic structures like variable declarations, or calls to <i>malloc</i>, 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.  </div><div><br></div><div>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 dereference.</div><div><br></div><div>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 existence.</div><div> <br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">> One solution would be for me to adapt the algorithm to remove this<br></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
> ambiguity.  But if possible I'd like to keep the algorithm as close to the<br>
> published version as possible, so I'd rather find another solution.<br>
<br>
</span>Why?<br>
Published versions are often ... wrong, not well engineered, etc :)<br></blockquote><div><br></div><div>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 implementation.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
><br>
> Another approach is to add a value to the AliasResult enumeration,<br>
> indicating "MustAlias or NoAlias, I'm not sure which".  But I'm not sure if<br>
> any downstream analyses could make use of a result like that.<br>
<br>
</span>Above, you say you want to not return MustAlias.<br>
Here you say it's not clear that any downstream results could make use<br>
of better info.<br>
<br>
Before you go and try to figure out what should change, you really<br>
need to actually determine whether the info you have is valuable.<br>
<br>
I would do this by finding a pass you think you can improve with your<br>
extra info, and seeing if it improves (add a temporary hack AA<br>
function or something that gives info about this) by giving it must/no<br>
vs may.<br>
<br>
If something improves, great, we can figure out whether it's worth the<br>
tradeoffs/etc and help you figure out what to do.<br>
If nothing improves, it may not be worth you spending your time on it.<br></blockquote><div><br></div><div>Thanks, will do.   I appreciate the feedback!</div><div><br></div><div>- Christian</div><div> </div></div><br></div></div>