DSE pass takes very long to optimize llvmAsmParser.cpp

[llvmbot]

Bugzilla Link	930
Resolution	FIXED
Resolved on	Feb 22, 2010 12:53
Version	trunk
OS	MacOS X
Attachments	shark profile
Reporter	LLVM Bugzilla Contributor

Extended Description

I am attaching shark profile.

[asl]

How much is "very long"?

I'm having here:

$ ./opt -time-passes -std-compile-opts llvmAsmParser.bc -disable-output
===-------------------------------------------------------------------------===
... Pass execution timing report ...
===-------------------------------------------------------------------------===
Total Execution Time: 4.9442 seconds (4.9198 wall clock)

---User Time--- --System Time-- --User+System-- ---Wall Time--- ---
Name ---
0.5129 ( 11.7%) 0.0139 ( 2.4%) 0.5269 ( 10.6%) 0.5260 ( 10.6%)
Simplify the CFG
0.4399 ( 10.0%) 0.0109 ( 1.9%) 0.4509 ( 9.1%) 0.4502 ( 9.1%) Scalar
Replacement of Aggregates
0.4269 ( 9.7%) 0.0040 ( 0.7%) 0.4309 ( 8.7%) 0.4323 ( 8.7%) Dead
Store Elimination
0.3229 ( 7.3%) 0.0119 ( 2.1%) 0.3349 ( 6.7%) 0.3269 ( 6.6%)
Promote Memory to Register
0.3069 ( 7.0%) 0.0119 ( 2.1%) 0.3189 ( 6.4%) 0.3217 ( 6.5%)
Combine redundant instructions
0.2859 ( 6.5%) 0.0069 ( 1.2%) 0.2929 ( 5.9%) 0.2753 ( 5.5%)
Function Integration/Inlining
0.2279 ( 5.2%) 0.0070 ( 1.2%) 0.2349 ( 4.7%) 0.2462 ( 5.0%) Break
critical edges in CFG
0.2119 ( 4.8%) 0.0139 ( 2.4%) 0.2259 ( 4.5%) 0.2222 ( 4.5%) Global
Common Subexpression Elimination
0.1739 ( 3.9%) 0.0149 ( 2.6%) 0.1889 ( 3.8%) 0.1882 ( 3.8%) Tail
Duplication
0.1389 ( 3.1%) 0.0129 ( 2.3%) 0.1519 ( 3.0%) 0.1441 ( 2.9%) Break
critical edges in CFG
0.1079 ( 2.4%) 0.0099 ( 1.7%) 0.1179 ( 2.3%) 0.1236 ( 2.5%) Sparse
Conditional Constant Propagation
0.0819 ( 1.8%) 0.0089 ( 1.5%) 0.0909 ( 1.8%) 0.0952 ( 1.9%)
Combine redundant instructions
0.0909 ( 2.0%) 0.0069 ( 1.2%) 0.0979 ( 1.9%) 0.0909 ( 1.8%)
Combine redundant instructions
0.0689 ( 1.5%) 0.0129 ( 2.3%) 0.0819 ( 1.6%) 0.0886 ( 1.8%)
Aggressive Dead Code Elimination
0.0749 ( 1.7%) 0.0079 ( 1.4%) 0.0829 ( 1.6%) 0.0792 ( 1.6%)
Combine redundant instructions
0.0589 ( 1.3%) 0.0109 ( 1.9%) 0.0699 ( 1.4%) 0.0680 ( 1.3%)
Combine redundant instructions
0.0549 ( 1.2%) 0.0079 ( 1.4%) 0.0629 ( 1.2%) 0.0664 ( 1.3%)
Immediate Post-Dominators Construction
0.0609 ( 1.3%) 0.0069 ( 1.2%) 0.0679 ( 1.3%) 0.0663 ( 1.3%)
Combine redundant instructions
0.0559 ( 1.2%) 0.0069 ( 1.2%) 0.0629 ( 1.2%) 0.0624 ( 1.2%)
Simplify the CFG
0.0409 ( 0.9%) 0.0109 ( 1.9%) 0.0519 ( 1.0%) 0.0574 ( 1.1%)
Reassociate expressions

Is it too much for DSE?

[llvmbot]

*** Bug llvm/llvm-bugzilla-archive#1268 has been marked as a duplicate of this bug. ***

[isanbard]

I think this is what he's talking about:

$ opt -time-passes -std-compile-opts llvmAsmParser.bc -disable-output
===-------------------------------------------------------------------------===
... Pass execution timing report ...
===-------------------------------------------------------------------------===
Total Execution Time: 502.2523 seconds (818.1477 wall clock)

---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
414.4836 ( 83.8%) 6.0081 ( 73.9%) 420.4918 ( 83.7%) 684.2935 ( 83.6%) Dead Store Elimination
8.2178 ( 1.6%) 0.1788 ( 2.2%) 8.3966 ( 1.6%) 14.8037 ( 1.8%) Global Common Subexpression
Elimination
5.8533 ( 1.1%) 0.1453 ( 1.7%) 5.9987 ( 1.1%) 10.6824 ( 1.3%) Combine redundant instructions
5.3960 ( 1.0%) 0.1629 ( 2.0%) 5.5590 ( 1.1%) 9.3899 ( 1.1%) Function Integration/Inlining
3.9742 ( 0.8%) 0.1145 ( 1.4%) 4.0887 ( 0.8%) 8.4153 ( 1.0%) Combine redundant instructions
4.0108 ( 0.8%) 0.1040 ( 1.2%) 4.1149 ( 0.8%) 7.6828 ( 0.9%) Combine redundant instructions
4.0955 ( 0.8%) 0.1067 ( 1.3%) 4.2022 ( 0.8%) 7.5477 ( 0.9%) Combine redundant instructions
3.2156 ( 0.6%) 0.0903 ( 1.1%) 3.3059 ( 0.6%) 6.0778 ( 0.7%) Combine redundant instructions
3.3262 ( 0.6%) 0.0916 ( 1.1%) 3.4178 ( 0.6%) 5.9827 ( 0.7%) Combine redundant instructions
3.7390 ( 0.7%) 0.0597 ( 0.7%) 3.7987 ( 0.7%) 5.5606 ( 0.6%) Loop Invariant Code Motion
4.8300 ( 0.9%) 0.0445 ( 0.5%) 4.8746 ( 0.9%) 5.3244 ( 0.6%) Merge Duplicate Global Constants
4.3730 ( 0.8%) 0.0285 ( 0.3%) 4.4015 ( 0.8%) 4.8293 ( 0.5%) Find Used Types
2.6880 ( 0.5%) 0.0694 ( 0.8%) 2.7574 ( 0.5%) 3.8414 ( 0.4%) Aggressive Dead Code Elimination
2.3697 ( 0.4%) 0.0368 ( 0.4%) 2.4065 ( 0.4%) 3.5789 ( 0.4%) Dead Global Elimination
1.7468 ( 0.3%) 0.0472 ( 0.5%) 1.7940 ( 0.3%) 3.1933 ( 0.3%) Sparse Conditional Constant
Propagation
1.1393 ( 0.2%) 0.0397 ( 0.4%) 1.1790 ( 0.2%) 2.2009 ( 0.2%) Scalar Replacement of Aggregates
1.0988 ( 0.2%) 0.0380 ( 0.4%) 1.1369 ( 0.2%) 1.9483 ( 0.2%) Reassociate expressions
0.7372 ( 0.1%) 0.0210 ( 0.2%) 0.7582 ( 0.1%) 1.6723 ( 0.2%) Break critical edges in CFG
1.1044 ( 0.2%) 0.0363 ( 0.4%) 1.1408 ( 0.2%) 1.6372 ( 0.2%) Promote Memory to Register
0.7857 ( 0.1%) 0.0231 ( 0.2%) 0.8089 ( 0.1%) 1.4402 ( 0.1%) Simplify the CFG
1.0646 ( 0.2%) 0.0213 ( 0.2%) 1.0860 ( 0.2%) 1.4326 ( 0.1%) Post-Dominator Tree Construction
0.7470 ( 0.1%) 0.0236 ( 0.2%) 0.7707 ( 0.1%) 1.3696 ( 0.1%) Canonicalize natural loops
0.9332 ( 0.1%) 0.0207 ( 0.2%) 0.9539 ( 0.1%) 1.2939 ( 0.1%) Post-ET-Forest Construction
0.7074 ( 0.1%) 0.0199 ( 0.2%) 0.7273 ( 0.1%) 1.2682 ( 0.1%) Break critical edges in CFG
0.8237 ( 0.1%) 0.0265 ( 0.3%) 0.8502 ( 0.1%) 1.1953 ( 0.1%) Module Verifier
0.7230 ( 0.1%) 0.0252 ( 0.3%) 0.7483 ( 0.1%) 1.1831 ( 0.1%) Simplify the CFG
0.5918 ( 0.1%) 0.0185 ( 0.2%) 0.6104 ( 0.1%) 1.1339 ( 0.1%) Simplify the CFG
0.9218 ( 0.1%) 0.0112 ( 0.1%) 0.9331 ( 0.1%) 1.0209 ( 0.1%) Module Verifier
0.5937 ( 0.1%) 0.0194 ( 0.2%) 0.6131 ( 0.1%) 1.0082 ( 0.1%) Simplify the CFG
0.4494 ( 0.0%) 0.0165 ( 0.2%) 0.4659 ( 0.0%) 0.8686 ( 0.1%) Dominator Tree Construction
0.4341 ( 0.0%) 0.0164 ( 0.2%) 0.4505 ( 0.0%) 0.8435 ( 0.1%) Loop-Closed SSA Form Pass
0.5352 ( 0.1%) 0.0241 ( 0.2%) 0.5593 ( 0.1%) 0.8244 ( 0.1%) Remove unused exception
handling info

Gah!!

[asl]

*** Bug llvm/llvm-bugzilla-archive#1423 has been marked as a duplicate of this bug. ***

[llvmbot]

*** Bug llvm/llvm-bugzilla-archive#1498 has been marked as a duplicate of this bug. ***

[llvmbot]

FastDSE pretty much takes care of all the speed complaints against DSE.