[llvm-bugs] [Bug 41263] New: [CompileTime] [DAGCombiner] Large amount of compile-time spent in getStoreMergeCandidates for inputs with lots of stores

[via llvm-bugs]

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

            Bug ID: 41263
           Summary: [CompileTime] [DAGCombiner] Large amount of
                    compile-time spent in getStoreMergeCandidates for
                    inputs with lots of stores
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Common Code Generator Code
          Assignee: unassignedbugs at nondot.org
          Reporter: florian_hahn at apple.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 21687
  --> https://bugs.llvm.org/attachment.cgi?id=21687&action=edit
Script to trigger worst case in DAGCombiner and Pre-RA-scheduler

Currently DAGCombiner spends a huge amount of time in getStoreMergeCandidates
for inputs with lots of stores, because it iterates over all stores in the same
token factor for each store it visits.

The attached script generates ll files with N stores in a single BB, that
cannot be merged. 

For 10000 stores, bin/llc -o /dev/null -stop-before=machine-scheduler
-time-passes reports

===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 19.3153 seconds (24.4060 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  ---
Name ---
  18.4783 ( 99.5%)   0.7263 ( 97.3%)  19.2046 ( 99.4%)  24.2557 ( 99.4%)  X86
DAG->DAG Instruction Selection
   0.0299 (  0.2%)   0.0093 (  1.2%)   0.0392 (  0.2%)   0.0545 (  0.2%)  MIR
Printing Pass

===-------------------------------------------------------------------------===
                      Instruction Selection and Scheduling
===-------------------------------------------------------------------------===
  Total Execution Time: 19.1471 seconds (24.1911 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  ---
Name ---
   9.1751 ( 49.8%)   0.3746 ( 52.2%)   9.5496 ( 49.9%)  12.7750 ( 52.8%)  DAG
Combining 2
   7.4307 ( 40.3%)   0.1554 ( 21.6%)   7.5861 ( 39.6%)   8.5715 ( 35.4%)  DAG
Combining 1
   1.7270 (  9.4%)   0.1716 ( 23.9%)   1.8986 (  9.9%)   2.6702 ( 11.0%) 
Instruction Scheduling

-- 
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/20190327/cbf243bb/attachment.html>