[llvm-bugs] [Bug 41174] New: [DAGCombiner] Large TokenFactors cause large amount of compile-time spent in CombineTo

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=41174

            Bug ID: 41174
           Summary: [DAGCombiner] Large TokenFactors cause large amount of
                    compile-time spent in CombineTo
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Core LLVM classes
          Assignee: unassignedbugs at nondot.org
          Reporter: florian_hahn at apple.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 21637
  --> https://bugs.llvm.org/attachment.cgi?id=21637&action=edit
Script to generate LL files to stress DAGCombiner's CombineTo

For inputs where DAGombiner creates large TokenFactors (e.g. large number of
loads/stores), CombineTo is very expensive. After combining a set of stores, we
have to remove them from the containing TokenFactor and recompute the
FoldingSetID, which requires iterating over all operands. About half of time
time in DAGCombiner is spent in CombineTo.

The attached generate_ll_combineto.py generates a sequence of sequential
stores, which can all be combined and it illustrates the increase in compile
time. Note that the script generates the worst-case scenario.


for i in `seq 5000 5000 40000`; do echo "=== $i === "; python
generate_ll_combineto.py  $i | time bin/llc -O3 -o /dev/null; done    
=== 5000 ===
bin/llc -o /dev/null  0.35s user 0.02s system 94% cpu 0.391 total
=== 10000 ===
bin/llc -o /dev/null  1.74s user 0.03s system 98% cpu 1.798 total
=== 15000 ===
bin/llc -o /dev/null  4.93s user 0.91s system 99% cpu 5.874 total
=== 20000 ===
bin/llc -o /dev/null  8.37s user 1.54s system 99% cpu 9.944 total
=== 25000 ===
bin/llc -o /dev/null  12.57s user 2.46s system 99% cpu 15.064 total
=== 30000 ===
bin/llc -o /dev/null  17.80s user 3.43s system 99% cpu 21.273 total
=== 35000 ===
bin/llc -o /dev/null  23.89s user 4.59s system 99% cpu 28.526 total
=== 40000 ===
bin/llc -o /dev/null  31.71s user 5.61s system 99% cpu 37.368 total

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20190321/11e8b616/attachment.html>