search for: groupbycomplexity

...*** > > ** ** > > It seems that the majority of the time is spent in comparing the > complexity of the expression operands to sort them. > Why not just fix this then? I assume the issue is that they all end up with the same length/complexity, so it both falls into the N^2 loop in GroupByComplexity, and the sort itself takes a long time because it compares operand by operand. This seems easy to fix by having GroupByComplexity calculate a very cheap hash prior to sorting when number of operands is large, and then using that hash before recursively comparing element by element to distinguish t...

Thank you very much for your reply. Do you mean calculate the hash based on element SCEV pointers? But according to the comments before GroupByComplexity(): /// Note that we go take special precautions to ensure that we get deterministic /// results from this routine. In other words, we don't want the results of /// this to depend on where the addresses of various SCEV objects happened to /// land in memory. Xiaoyi From: Daniel Berlin [mailt...

Hi, We have a benchmark where there are 128 MAD computations in a loop. (See the attached IR.) Creating SCEVs for these expressions takes a long time, making the compile time too long. E.g., running opt with the "indvars" pass only takes 45 seconds. It seems that the majority of the time is spent in comparing the complexity of the expression operands to sort them. I realize that the

...r is there any way to further optimize the performance of SCEV building for such cases. > > Thanks in advance for any response. Nice test case. I tried printing the SCEV… oops. I haven’t seen a case this bad, but I know you’re not the first to run into this problem. There are two steps in GroupByComplexity, sorting (std::sort) and grouping (N^2). The sort calls SCEVComplexityCompare::compare() which can make multiple recursive calls for nodes with multiple operands. This looks like it could be a disaster for expressions that are not strictly trees--exponential in the size of the DAG. If you just ha...

...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....

...gt; optimize the performance of SCEV building for such cases. > > Thanks in advance for any response. > > > Nice test case. I tried printing the SCEV… oops. I haven’t seen a case this > bad, but I know you’re not the first to run into this problem. > > There are two steps in GroupByComplexity, sorting (std::sort) and grouping > (N^2). > > The sort calls SCEVComplexityCompare::compare() which can make multiple > recursive calls for nodes with multiple operands. This looks like it could > be a disaster for expressions that are not strictly trees--exponential in > the siz...

I got the following error while compiling llvm and clang under cygwin. /cygdrive/c/Users/brianherman/Desktop/llvm/llvm-3.3.src/Release+Asserts/lib/libLLVMMCJIT.a(SectionMemoryManager.o):SectionMemoryManager.cpp:(.text+0x3b): undefined reference to `__register_frame'

...passes in the legacy pass manager... +3% r247264: Enable GlobalsAA by default. +1% 6. r247674: [GlobalsAA] Disable globals-aa by default. -1% 7. r248638: [SCEV] Reapply 'Teach isLoopBackedgeGuardedByCond to exploit trip counts'. +2% 8. r249802: [SCEV] Call `StrengthenNoWrapFlags` after `GroupByComplexity`; NFCI. +4% 9. r250157: [GlobalsAA] Turn GlobalsAA on again by default. +1% 10. r251049: [SCEV] Mark AddExprs as nsw or nuw if legal. +23% 11. No data 12. r259252: AttributeSetImpl: Summarize existing function attributes in a bitset. -1% r259256: Add LoopSimplifyCFG pass. -2% 13. r262250: Enabl...

...Or is there any way to further optimize the performance of SCEV building for such cases. Thanks in advance for any response. Nice test case. I tried printing the SCEV... oops. I haven't seen a case this bad, but I know you're not the first to run into this problem. There are two steps in GroupByComplexity, sorting (std::sort) and grouping (N^2). The sort calls SCEVComplexityCompare::compare() which can make multiple recursive calls for nodes with multiple operands. This looks like it could be a disaster for expressions that are not strictly trees--exponential in the size of the DAG. If you just ha...

...tions > > 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...

.... +3% >> r247264: Enable GlobalsAA by default. +1% >> 6. r247674: [GlobalsAA] Disable globals-aa by default. -1% >> 7. r248638: [SCEV] Reapply 'Teach isLoopBackedgeGuardedByCond to exploit trip counts'. +2% >> 8. r249802: [SCEV] Call `StrengthenNoWrapFlags` after `GroupByComplexity`; NFCI. +4% >> 9. r250157: [GlobalsAA] Turn GlobalsAA on again by default. +1% >> 10. r251049: [SCEV] Mark AddExprs as nsw or nuw if legal. +23% >> 11. No data >> 12. r259252: AttributeSetImpl: Summarize existing function attributes in a bitset. -1% >> r259256: Add...

...t; r247264: Enable GlobalsAA by default. +1% > > 6. r247674: [GlobalsAA] Disable globals-aa by default. -1% > > 7. r248638: [SCEV] Reapply 'Teach isLoopBackedgeGuardedByCond to exploit > trip counts'. +2% > > 8. r249802: [SCEV] Call `StrengthenNoWrapFlags` after > `GroupByComplexity`; NFCI. +4% > > 9. r250157: [GlobalsAA] Turn GlobalsAA on again by default. +1% > > 10. r251049: [SCEV] Mark AddExprs as nsw or nuw if legal. +23% > > 11. No data > > 12. r259252: AttributeSetImpl: Summarize existing function attributes in > a bitset. -1% > > r25...

Thanks for sharing the known problem. I think to solve the problem properly, we need to fully understand why that assumption about dominance is there and the implications of removing it. It would be good if you could be more specific about your idea of nullptr or SCEV_unknown (eg which function would return those values and when), but returning nullptr from getAddExpr or getSCEVAtScope may be