Open Radar

 
The attached LLVM IR file (https://www.dropbox.com/s/hdg0hfaxhh1r2x8/beng.ll.zip) hangs when run through the clang optimizer when Dead Store Elimination (-dse) is enabled (which it is at -O1 or higher).

Steps to Reproduce:

0) Compile Clang 3.2 or later from source (debug or release).

1) Confirm issue does not reproduce without -dse:

% ./opt -time-passes ~/Documents/beng.ll      
WARNING: You're attempting to print out a bitcode file.
This is inadvisable as it may cause display problems. If
you REALLY want to taste LLVM bitcode first-hand, you
can force output with the `-f' option.

===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 0.2477 seconds (0.2487 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   0.2471 (100.0%)   0.0005 ( 93.1%)   0.2476 (100.0%)   0.2483 ( 99.8%)  Module Verifier
   0.0000 (  0.0%)   0.0000 (  6.5%)   0.0001 (  0.0%)   0.0004 (  0.2%)  Dominator Tree Construction
   0.0000 (  0.0%)   0.0000 (  0.4%)   0.0000 (  0.0%)   0.0000 (  0.0%)  Preliminary module verification
   0.2472 (100.0%)   0.0005 (100.0%)   0.2477 (100.0%)   0.2487 (100.0%)  Total

===-------------------------------------------------------------------------===
                                LLVM IR Parsing
===-------------------------------------------------------------------------===
  Total Execution Time: 3.1670 seconds (3.2785 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
   3.1130 (100.0%)   0.0540 (100.0%)   3.1670 (100.0%)   3.2785 (100.0%)  Parse IR
   3.1130 (100.0%)   0.0540 (100.0%)   3.1670 (100.0%)   3.2785 (100.0%)  Total

2) Repeat with -dse:

% ./opt -dse -time-passes ~/Documents/beng.ll
WARNING: You're attempting to print out a bitcode file.
This is inadvisable as it may cause display problems. If
you REALLY want to taste LLVM bitcode first-hand, you
can force output with the `-f' option.

(nothing for 60 minutes)

Expected Results:

Optimizer should finish within a few seconds on this input.

Actual Results:

Optimizer hangs (or takes over 60 minutes on my 2.7 GHz Core i7 MacBook Pro).

Regression: Reproduces with Clang 3.2 / Xcode 4.6, Clang 3.3, Xcode 5 DP3, and Clang trunk.