<div dir="ltr">Hi,<div><br></div><div>Thanks for the input. In my ptr_test.O1.ll, the two loops should fall into the last case due to loop rotations. And I think we should handle that case.</div><div>I propose to check the dominance relation between loop predecessor blocks of the two loops if there is no dominance relation between their loop headers just like case three. The only thing I'm not pretty sure is that is there guarantee to exist dominance relation on their loop predecessor blocks. That is, either LPred dominates RPred or RPred dominate LPred? </div><div><br></div><div>B.R.</div><div>- Min</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jun 11, 2019 at 8:41 PM Michael Kruse <<a href="mailto:llvmdev@meinersbur.de">llvmdev@meinersbur.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
if I understand CompareSCEVComplexity  correctly, we just need some<br>
deterministic order, not that important which one. We have three<br>
cases:<br>
<br>
1. LHead dominates RHead<br>
2. RHead dominates LHead<br>
3. There is no dominance relationship between the loops<br>
<br>
LHead dominating RHead can either mean that R is nested inside L, or<br>
the entire loop of L dominated R. From ptr_test.c that latter seems<br>
the case, but LoopRotation might change this relation.<br>
<br>
For the third case, we might just find another tie breaker rule, such<br>
as a NumOps comparison afterwards or the order in which LoopInfo finds<br>
them (this might be indeterministic). However, it might also be ok to<br>
just return 0, meaning both are equally complex.<br>
<br>
Michael<br>
<br>
<br>
Am Di., 11. Juni 2019 um 14:21 Uhr schrieb Min-Yih Hsu via llvm-dev<br>
<<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>:<br>
><br>
> Hi,<br>
><br>
> 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.<br>
> 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.<br>
> Here are the details:<br>
><br>
> Setup<br>
> Off-the-tip llvm-project, including clang and libcxx, built in full Debug build<br>
><br>
> Input Program<br>
> 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`<br>
><br>
> Crashed Command<br>
> `opt -S -disable-output -basicaa -scev-aa -aa-eval -print-no-aliases ptr_test.O1.ll`<br>
> The core dump message is also in the attachments.<br>
><br>
> Investigations<br>
> 1. SCEV-AA try to ‘minus' the SCEV expressions of the given two pointers(lib/Analysis/ScalarEvolutionAliasAnalysis.cpp:64)<br>
> 2. ScalarEvolution::getMinusSCEV will boil down into ScalarEvolution::getAddExpr. On line 2383 of lib/Analysis/ScalarEvolution.cpp, GroupByComplexity is invoked.<br>
> 3. CompareSCEVComplexity is eventually called to give a partial order between two SCEV expression.<br>
> 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.<br>
><br>
> 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?).<br>
> As I mentioned earlier, the simplest solution is to remove this assertion, but still, the very assumption is still encoded in the surrounding code.<br>
> 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.<br>
><br>
> Thank you,<br>
><br>
> B.R.<br>
> - Min<br>
><br>
><br>
> _______________________________________________<br>
> LLVM Developers mailing list<br>
> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
> <a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div>Min-Yih Hsu</div><div>Ph.D Student in ICS Department, University of California, Irvine (UCI).<br></div></div></div>