<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jan 16, 2015 at 1:52 PM, Chandler Carruth <span dir="ltr"><<a href="mailto:chandlerc@google.com" target="_blank">chandlerc@google.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>(sorry for the wide distribution, but this impacts Clang users quite a bit)</div><div><br></div>It's come up a few times in reviews of CFL-AA (a new alias analysis for LLVM), so I wanted to write down what I think the current state actually is for AA pass ordering, why, and how it should look eventually. I may have some bugs here, so please correct me if I miss anything. And I'd love thoughts about the end state.<div><br></div><div>Today, we have a strange ordering which is primarily motivated by trying to support both TBAA and union-based local type punning:</div><div><br></div><div>1) Run BasicAA. If it hits NoAlias, MustAlias, or PartialAlias, done. If it hits MayAlias, delegate to #2.</div><div>2) See if there is scoped no-alias metadata that can produce NoAlias and return that if so. If not, delegate to #3.</div><div>3) See if there is TBAA metadata that can produce NoAlias and return that if so. If not, delegate to #4.</div><div>4) If using CFL-AA, ask it and use its answer as the final answer.</div><div><br></div><div>The primary reason for running BasicAA first is so that it can return MustAlias for local type puns, bypassing the more strict behavior of TBAA. Having TBAA not fire on local type puns was a critical need for the Darwin platform and maybe for others as well. However, this implementation strategy is problematic for a host of reasons:</div><div><br></div><div>a) There are other users of LLVM that might want strict TBAA, and they can't get that today.</div></div></blockquote><div><br></div><div><br></div><div>Because the user want to ignore the aliases (real) or they just want diagnostics?</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>b) BasicAA can hit partial-alias in cases that aren't even type puns and which either TBAA or some other more-powerful AA like CFL-AA would return no-alias. In these cases, we produce a too-conservative answer.</div></div></blockquote><div><br></div><div>Are there bugs tracking them?</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>c) I'm worried that BasicAA does caching that isn't valid for all possible AA implementations.</div><div><br></div><div>I think we should change these things in the following way to get to a more principled place.</div><div><br></div><div>First, we should make the order something a bit more obvious which has to do with which AA passes have the most information:</div><div><br></div><div>1) Run the scoped no-alias AA and return any final answers it produces.</div><div>2) Run TBAA and return any final answers it produces.</div><div>3) Run CFL-AA (if enabled, or any other advanced AA implementations we want) and return any final answers it produces (IE, anything more precise than 'may-alias').</div><div>4) Run BasicAA and use its answer.</div></div></blockquote><div><br></div><div>It might be useful to collect some compile time data. The alias query cost also depends on the type of memory references used the program. Simple base+offset alias check is cheap. If the program has lots of accesses with known base objects, basicaa might be the only thing needed -- pushing it to the end of the pipeline may hurt compile time.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>I then think we should teach TBAA to have an explicit flag which causes it, when discovering a 'no-alias' result, to query BasicAA for a contradiction of must-alias or partial-alias, and to ignore the no-alias in that case. That should more precisely model the desired behavior of TBAA-except-for-local-type-puns.</div></div></blockquote><div><br></div><div><br></div><div>This is a good idea. In general, the aliaser can have two chains of alias infos. One chain consists of analysis based alias results while the other chain is assertion/language rule based. </div><div><br></div><div>Definitive results from one AA can skip the rest of the AAs in the same chain, but may need to go through the other chain if the option is on -- i.e. must alias from basicAA will go through TBAA for checking, or NoAlias from TBAA will go through BasicAA .. The compiler decides who wins in case of contradiction and emits warnings appropriately.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>Finally, I think we should teach Clang to have two flags: "-fstrict-aliasing" and '-fstrict-local-type-pun-aliasing'. By default, strict-aliasing can imply strict-local-type-pun-aliasing. Darwin and any other platforms that want the current aliasing behavior can make the use of strict-aliasing by default *not* imply strict-local-type-pun-aliasing. This would still make it available behind a flag, and let other platforms line up the defaults in other ways that make sense to them.</div><div><br></div></div></blockquote><div><br></div><div>this makes sense to me.</div><div><br></div><div>David</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div></div><div>Thoughts?</div><span class=""><font color="#888888"><div>-Chandler</div></font></span></div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br></div></div>