[llvm-bugs] [Bug 41264] New: [CompileTime][ScheduleDAGRRList] Quadratic behavior in popFromQueueImpl

[via llvm-bugs]

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

            Bug ID: 41264
           Summary: [CompileTime][ScheduleDAGRRList] Quadratic behavior in
                    popFromQueueImpl
           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 21688
  --> https://bugs.llvm.org/attachment.cgi?id=21688&action=edit
Script to trigger quadratic behavior in ScheduleDAGRRList

We do a linear scan in popFromQueueImpl. For certain inputs, where we have a
large number of available candidates (e.g. large number of stores for bottom up
scheduling), this can have a large impact on compile time. 

For an input with 10000 stores, we spend 10 seconds ScheduleDAGRRList because
of that. The attached script can be used to generate such inputs. Note that
currently the compile time is dominated by DAGCombiner, which is tracked by
PR41263

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