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

[Min-Yih Hsu via llvm-dev]

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


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/fd11dc06/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ptr_test.c
Type: application/octet-stream
Size: 225 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/fd11dc06/attachment.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/fd11dc06/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ptr_test.O1.ll
Type: application/octet-stream
Size: 3311 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/fd11dc06/attachment-0001.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/fd11dc06/attachment-0002.html>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: core_dump_msg.txt
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/fd11dc06/attachment.txt>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/fd11dc06/attachment-0003.html>