
<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Hi,<div class=""><br class=""></div><div class="">Recently I got a crash when I tried to analysis a program with ScalarEvolution AliasAnalysis(SCEV-AA for short). It turns out to be a (possibly) incorrect assertion inside the CompareSCEVComplexity routine. </div><div class="">The simplest solution would be just remove that assertion but I also found that the surrounding logics on calculating SCEV cost seems to be incorrect either. Thus I want to discuss with you folks about the best way to solve this.</div><div class="">Here are the details:</div><div class=""><br class=""></div><div class=""><b class="">Setup</b></div><div class="">Off-the-tip llvm-project, including clang and libcxx, built in full Debug build</div><div class=""><br class=""></div><div class=""><b class="">Input Program</b></div><div class="">Both the original C file and IR file are enclosed in the attachment. The IR generation command is `clang -O1 -emit-llvm -S ptr_test.c -o ptr_test.O1.ll`</div><div class=""><br class=""></div><div class=""><b class="">Crashed Command</b></div><div class="">`opt -S -disable-output -basicaa -scev-aa -aa-eval -print-no-aliases ptr_test.O1.ll`</div><div class="">The core dump message is also in the attachments.</div><div class=""><br class=""></div><div class=""><b class="">Investigations</b></div><div class="">1. SCEV-AA try to ‘minus' the SCEV expressions of the given two pointers(lib/Analysis/ScalarEvolutionAliasAnalysis.cpp:64)</div><div class="">2. ScalarEvolution::getMinusSCEV will boil down into ScalarEvolution::getAddExpr. On line 2383 of lib/Analysis/ScalarEvolution.cpp, GroupByComplexity is invoked.</div><div class="">3. CompareSCEVComplexity is eventually called to give a partial order between two SCEV expression.</div><div class="">4. If there are two SCEVAddExpr that are located in different loops which don’t have any hierarchical relation, just like pointers in line 6 and line 10 in the input program(i.e. ptr_test.c), it will violate the assertion in line 705 in lib/Analysis/ScalarEvolution.cpp. </div><div class=""><br class=""></div><div class="">The point is that the assertion in line 705 doesn’t make sense in most of the cases: I don’t think there is any limitation imposed on arbitrary SCEV expressions to make the enclosing SCEVAddRec to be in the same loop(Or should we?).</div><div class="">As I mentioned earlier, the simplest solution is to remove this assertion, but still, the very assumption is still encoded in the surrounding code.</div><div class="">So I want to hear from you folks <b class="">whether we should calculate the complexity of SCEVAddRec located in different loops</b>. If yes, what’s the best way? For the latter question, currently I have an idea in my mind to compare their loop trip counts before doing the following lexicographic comparison. </div><div class=""><br class=""></div><div class="">Thank you,</div><div class=""><br class=""></div><div class="">B.R.</div><div class="">- Min</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""></div></body></html>