[LLVMbugs] [Bug 18580] New: Performance regression in the LiveIntervals analysis pass

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=18580

            Bug ID: 18580
           Summary: Performance regression in the LiveIntervals analysis
                    pass
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Register Allocator
          Assignee: unassignedbugs at nondot.org
          Reporter: vaidas.gasiunas at sap.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Created attachment 11919
  --> http://llvm.org/bugs/attachment.cgi?id=11919&action=edit
Perl script to generate C program reproducing the regression

Hi,

We are using LLVM as a backend for jitting code generated from a
domain-specific language, and after porting from llvm 3.1 to llvm 3.3 detected
a significant compile-time regression for some of our test examples. For
example, in one test the jit time increased from 200s to 1500s. 

We reproduced a similar regression with an example compiled by clang. I
attached a perl script that generates C programs to reproduce the performance
regression. For example, we profiled compilation of a C program created by: 

createC.pl example.cpp 5000

Profile results with llvm 3.4:
------------------------------
llvm::FPPassManager::runOnFunction  9.120s
  llvm::LiveIntervals::runOnMachineFunction 4.508s
    llvm::LiveIntervals::computeLiveInRegUnits  4.454s
      llvm::LiveIntervals::computeRegUnitRange  4.452s
        llvm::LiveRangeCalc::extendToUses   2.356s
        llvm::LiveRangeCalc::createDeadDefs 2.096s
      llvm::LiveRange::createDeadDef    0.002s
    llvm::LiveIntervals::computeVirtRegs    0.046s
    llvm::LiveIntervals::computeRegMasks    0.008s
  llvm::SelectionDAGISel::runOnMachineFunction  2.024s
  (anonymous namespace)::MachineBlockPlacement::runOnMachineFunction    0.722s
  llvm::LiveVariables::runOnMachineFunction 0.186s
  llvm::X86AsmPrinter::runOnMachineFunction 0.178s
  llvm::MachineDominatorTree::runOnMachineFunction  0.160s
  (anonymous namespace)::MachineCSE::PerformCSE 0.138s
  (anonymous namespace)::MachineScheduler::runOnMachineFunction 0.132s
  llvm::DominatorTree::runOnFunction    0.090s
 (anonymous namespace)::StackColoring::runOnMachineFunction 0.084s
 (anonymous namespace)::RAGreedy::runOnMachineFunction  0.082s

Profile results with llvm 3.1:
------------------------------
llvm::FPPassManager::runOnFunction  4.408s
  llvm::SelectionDAGISel::runOnMachineFunction  2.204s
  (anonymous namespace)::MachineBlockPlacement::runOnMachineFunction    0.716s
  llvm::LiveVariables::runOnMachineFunction 0.182s
  llvm::X86AsmPrinter::runOnMachineFunction 0.138s
  (anonymous namespace)::RAGreedy::runOnMachineFunction 0.126s
  (anonymous namespace)::MachineCSE::runOnMachineFunction   0.120s
  (anonymous namespace)::RegisterCoalescer::runOnMachineFunction    0.096s
  llvm::LiveIntervals::runOnMachineFunction 0.088s

It can be seen that all the performance regression comes from the method
llvm::LiveIntervals::computeRegUnitRange.

Our investigation had shown that the slow performance is caused by inefficient
insertions into the live ranges array. Due to insertions in the middle of the
array the code has quadratic complexity with respect to the size of the array,
which tends to be pretty big in these examples. In our own test case it has
about 500000 elements. 

We have tried to change the implementation of computeRegUnitRange so that it
uses a set structure instead of array, and in this way managed to reduce the
execution time of the computeRegUnitRange down to a negligible number of about
1s, but the change is now more like workaround so that it is not in a shape to
be contributed. 

Regards,
Vaidas

-- 
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/20140122/88d5799d/attachment.html>