[LLVMbugs] [Bug 15000] New: Dead Store Elimination takes a very long time (and has no effect)

[bugzilla-daemon at llvm.org]

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

             Bug #: 15000
           Summary: Dead Store Elimination takes a very long time (and has
                    no effect)
           Product: libraries
           Version: 3.2
          Platform: PC
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: caustin at gmail.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified


I suspect the Dead Store Elimination pass has algorithmic deficiencies.  While
investigating why my Emscripten build was so slow, I ran opt with -time-passes
and witnessed:

third-party/mac/clang+llvm-3.1-x86_64-apple-darwin11/bin/opt -time-passes
-std-compile-opts -disable-inlining -std-link-opts -internalize -globaldce
-mergefunc -constmerge -always-inline -o=build/opt.bc build/total.bc
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 53.2006 seconds (53.2081 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  ---
Name ---
  22.9070 ( 43.5%)   0.0270 (  5.5%)  22.9340 ( 43.1%)  22.9402 ( 43.1%)  Dead
Store Elimination
  22.6525 ( 43.0%)   0.0315 (  6.4%)  22.6840 ( 42.6%)  22.6900 ( 42.6%)  Dead
Store Elimination
   0.8339 (  1.6%)   0.0083 (  1.7%)   0.8422 (  1.6%)   0.8417 (  1.6%) 
Global Value Numbering
...

Manually specifying all passes in -std-compile-opts and -std-link-opts but
excluding -dse had literally no effect on the resulting opt.bc file.

Why is dead store elimination so slow?

This occurs in both LLVM 3.1 and LLVM 3.2.

I have attached total.bc so you can reproduce the slowdown with the above
command.

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.