[llvm-bugs] [Bug 50584] New: MachineScheduler/PostRAScheduler have quadratic compile time complexity

[via llvm-bugs]

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

            Bug ID: 50584
           Summary: MachineScheduler/PostRAScheduler have quadratic
                    compile time complexity
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Common Code Generator Code
          Assignee: unassignedbugs at nondot.org
          Reporter: lebedev.ri at gmail.com
                CC: llvm-bugs at lists.llvm.org

A continuation of https://bugs.llvm.org/show_bug.cgi?id=50384

Relevant tests:
https://www.dropbox.com/s/3awj7pibbag1du6/test-512.ll?dl=0
https://www.dropbox.com/s/el1f3awkfzxv8qz/test-1024.ll?dl=0

where n is is LoopMicroOpBufferSize in X86ScheduleZnver3.td
(aka the desired unrolled loop size)

$ time ./bin/llc -time-passes -o /dev/null ../test-512.ll
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 11.5713 seconds (11.5714 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  ---
Name ---
   4.7281 ( 41.6%)   0.0011 (  0.6%)   4.7292 ( 40.9%)   4.7294 ( 40.9%)  Post
RA top-down list latency scheduler
   3.1045 ( 27.3%)   0.0000 (  0.0%)   3.1045 ( 26.8%)   3.1046 ( 26.8%) 
Machine Instruction Scheduler
<...>

$ time ./bin/llc -time-passes -o /dev/null ../test-1024.ll 
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 60.8318 seconds (60.8329 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  ---
Name ---
  31.6539 ( 52.3%)   0.0030 (  0.9%)  31.6570 ( 52.0%)  31.6576 ( 52.0%)  Post
RA top-down list latency scheduler
  21.5208 ( 35.6%)   0.0080 (  2.3%)  21.5288 ( 35.4%)  21.5294 ( 35.4%) 
Machine Instruction Scheduler
<...>

So doubling the amount of unrolling (and thus doubling the IR size),
results in 6x increase in compile time, for those parameters.

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