[llvm-bugs] [Bug 25843] New: OptimizeLEAPass is too slow

[via llvm-bugs]

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

            Bug ID: 25843
           Summary: OptimizeLEAPass is too slow
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: ASSIGNED
          Severity: normal
          Priority: P
         Component: Backend: X86
          Assignee: a.bataev at hotmail.com
          Reporter: vonosmas at gmail.com
                CC: llvm-bugs at lists.llvm.org, nadav256 at gmail.com,
                    qcolombet at apple.com
    Classification: Unclassified

OptimizeLEAPass added in r254712 and triggered by -Os on X86 platforms is
unacceptably slow. Its algorithm complexity is at least
O(MBB * ACCESS * LEA)
where MBB is the number of machine basic blocks in a function,
ACCESS is the number of load/stores in a basic block,
LEA is the number of lea instructions in a basic block.

The last two numbers can easily grow to thousands in real-life code (especially
in auto-generated functions), exploding the compile time.

Please investigate optimization improvements, or add a bound to avoid
triggering this pass. To reproduce:

$ cat a.py
import sys

def foo(n):
  print '#include <unordered_map>'
  print 'std::unordered_map<int, int> m;'
  print 'void foo() {'
  for i in range(n):
    print '  m[%d] = %d;' % (i, i + 100);
  print '}'

if __name__ == '__main__':
  foo(int(sys.argv[1]))

$ python a.py 200 > a.cc ; time ./bin/clang++ -std=c++11 -c a.cc -o a.o -Os

real    0m0.892s
user    0m0.852s
sys    0m0.040s
$ python a.py 400 > a.cc ; time ./bin/clang++ -std=c++11 -c a.cc -o a.o -Os

real    0m3.438s
user    0m3.412s
sys    0m0.030s
$ python a.py 800 > a.cc ; time ./bin/clang++ -std=c++11 -c a.cc -o a.o -Os

real    0m23.815s
user    0m23.709s
sys    0m0.116s

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