[llvm-dev] [RFC][SCEV] Behavior of AddRec in CompareSCEVComplexity

[Min-Yih Hsu via llvm-dev]

CC the code owner and the last author touching the affected part.

> On Jun 11, 2019, at 11:26 AM, Min-Yih Hsu via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> Hi,
> 
> 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. 
> 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.
> Here are the details:
> 
> Setup
> Off-the-tip llvm-project, including clang and libcxx, built in full Debug build
> 
> Input Program
> 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`
> 
> Crashed Command
> `opt -S -disable-output -basicaa -scev-aa -aa-eval -print-no-aliases ptr_test.O1.ll`
> The core dump message is also in the attachments.
> 
> Investigations
> 1. SCEV-AA try to ‘minus' the SCEV expressions of the given two pointers(lib/Analysis/ScalarEvolutionAliasAnalysis.cpp:64)
> 2. ScalarEvolution::getMinusSCEV will boil down into ScalarEvolution::getAddExpr. On line 2383 of lib/Analysis/ScalarEvolution.cpp, GroupByComplexity is invoked.
> 3. CompareSCEVComplexity is eventually called to give a partial order between two SCEV expression.
> 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. 
> 
> 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?).
> As I mentioned earlier, the simplest solution is to remove this assertion, but still, the very assumption is still encoded in the surrounding code.
> So I want to hear from you folks whether we should calculate the complexity of SCEVAddRec located in different loops. 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. 
> 
> Thank you,
> 
> B.R.
> - Min
> 
> 
> <ptr_test.c>
> <ptr_test.O1.ll>
> <core_dump_msg.txt>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/c04d7092/attachment.html>