Long running decompilation

[rfalke]

Version: 0.7.2.0-f51c658d81
File: https://github.com/rfalke/decompiler-subjects/tree/master/from_holdec/int_math_with_constants/ia32_elf_clang_O0

Normally I give 10min of CPU time with ulimit but reko didn't finish the above subject in this time. When I run it without ulimit it is still running after 160min when I stopped it.

The test case int_math_with_constants has a few long methods with a large single block. Maybe there is a O(n^2) algorithm for n=block size. Or some other problem.

[uxmal]

I have reproduced this issue. This is what the Microsoft profiler says:

Function Name	Total CPU (ms)	Total CPU (%)	Self CPU (ms)	Self CPU (%)	Module
Reko.Gui.Windows.WindowsDecompilerEventListener::Worker_DoWork	90799	93.08%	0	0.00%	Reko.Arch.X86.dll
Reko.Gui.Forms.MainFormInteractor+<>c__DisplayClass80_0::b__0	90481	92.75%	0	0.00%	Reko.Arch.X86.dll
Reko.Gui.Windows.Forms.AnalyzedPageInteractorImpl::PerformWork	87947	90.16%	0	0.00%	Reko.Arch.X86.dll
Reko.DecompilerDriver::AnalyzeDataFlow	87946	90.15%	0	0.00%	Reko.Arch.X86.dll
Reko.Analysis.DataFlowAnalysis::BuildExpressionTrees	83345	85.44%	0	0.00%	Reko.Arch.X86.dll
Reko.Analysis.SsaState::DeleteStatement	74759	76.64%	15	0.02%	Reko.Arch.X86.dll
Reko.Analysis.DeadCode::Eliminate	49703	50.95%	29	0.03%	Reko.Arch.X86.dll
Reko.Analysis.SsaState::RemoveUses	33765	34.61%	8862	9.08%	Reko.Arch.X86.dll
Reko.Analysis.Coalescer::Transform	25953	26.60%	0	0.00%	Reko.Arch.X86.dll
Reko.Analysis.Coalescer::Process	25946	26.60%	9	0.01%	Reko.Arch.X86.dll
Reko.Analysis.Coalescer::TryMoveAssignment	25860	26.51%	2	0.00%	Reko.Arch.X86.dll
Reko.Analysis.Coalescer::CoalesceStatements	25782	26.43%	6	0.01%	Reko.Arch.X86.dll
Reko.Analysis.SsaState::ReplaceDefinitions	20254	20.76%	10186	10.44%	Reko.Arch.X86.dll Reko.Analysis.DataFlowAnalysis::BuildSsaTransform

At first glance it seems Reko.Analysis.SsaState::DeleteStatement and related functions are taking an awful lot of time. I will investigate further to see if these numbers can be improved.

[uxmal]

The DeadCode::Eliminate method has been made much more effective. However, fixing this uncovered another inefficiency. The Reko type inference engine is doing a lot of unnecessary unifications for structures with large numbers of members. The sample binary has indeed a massive number of global variables, which cause an O(n^3) slowdown.

Fixing this will require rethinking how Reko's type inference collects data types. I will leave this tracking issue as I consider how to best do that.

[rfalke]

This is still an issue in version 0.11.4.0-931ca7d.

List of subjects which exceed the time limit:

from_decompile-it.com/lynx/ia32_elf_from_website
from_decompile-it.com/mathomatic/ia32_elf_from_website
from_explorerplusplus.com/version_1.3.4/ia32_pe_from_website
from_explorerplusplus.com/version_1.3.4/x64_pe_from_website
from_holdec/int_math_with_constants/arm64_elf_clang_O0
from_holdec/int_math_with_constants/arm64_elf_clang_O1
from_holdec/int_math_with_constants/arm64_elf_clang_O2
from_holdec/int_math_with_constants/arm64_elf_clang_O3
from_holdec/int_math_with_constants/arm64_elf_clang_Os
from_holdec/int_math_with_constants/arm64_elf_gcc_O0
from_holdec/int_math_with_constants/arm64_elf_gcc_O1
from_holdec/int_math_with_constants/ia32_elf_clang_O0
from_holdec/int_math_with_constants/ia32_elf_clang_O1
from_holdec/int_math_with_constants/ia32_elf_clang_O2
from_holdec/int_math_with_constants/ia32_elf_clang_O3
from_holdec/int_math_with_constants/ia32_elf_clang_Os
from_holdec/int_math_with_constants/ia32_elf_gcc_O0
from_holdec/int_math_with_constants/ia32_elf_gcc_O1
from_holdec/int_math_with_constants/ia32_elf_gcc_O2
from_holdec/int_math_with_constants/ia32_elf_gcc_O3
from_holdec/int_math_with_constants/ia32_elf_gcc_Os
from_holdec/int_math_with_constants/x64_elf_clang_O0
from_holdec/int_math_with_constants/x64_elf_clang_O1
from_holdec/int_math_with_constants/x64_elf_clang_O2
from_holdec/int_math_with_constants/x64_elf_clang_O3
from_holdec/int_math_with_constants/x64_elf_clang_Os
from_holdec/int_math_with_constants/x64_elf_gcc_O0
from_holdec/int_math_with_constants/x64_elf_gcc_O2
from_holdec/int_math_with_constants/x64_elf_gcc_O3
from_holdec/int_math_with_constants/x64_elf_gcc_Os
from_holdec/movfuscator/sin/ia32_elf_movcc
from_pouet.net/with_source_361/ia32_mz
malware_via_email/malware_0107/ia32_pe
malware_via_email/malware_0276/ia32_pe
malware_via_email/malware_0278/ia32_pe
malware_via_email/malware_0450/ia32_pe
malware_via_email/malware_0653/ia32_pe
malware_via_email/malware_0673/ia32_pe
malware_via_email/malware_0713/ia32_pe
malware_via_email/malware_1032/ia32_pe
malware_via_email/malware_1100/ia32_pe
malware_via_email/malware_1116/ia32_pe
malware_via_email/malware_1148/ia32_pe
malware_via_email/malware_1152/ia32_pe
malware_via_email/malware_1306/ia32_pe
malware_via_email/malware_1359/ia32_pe
malware_via_email/malware_1424/ia32_pe
malware_via_email/malware_1453/ia32_pe
malware_via_email/malware_1558/ia32_pe
malware_via_email/malware_1612/ia32_pe
malware_via_email/malware_1627/ia32_pe
malware_via_email/malware_1639/ia32_pe
malware_via_email/malware_1685/ia32_pe
malware_via_email/malware_1694/ia32_pe
malware_via_email/malware_1717/ia32_pe
malware_via_email/malware_1721/ia32_pe
malware_via_email/malware_1736/ia32_pe
malware_via_email/malware_1747/ia32_pe
malware_via_email/malware_1766/ia32_pe
malware_via_email/malware_1808/ia32_pe
malware_via_email/malware_1814/ia32_pe
malware_via_email/malware_1826/ia32_pe
malware_via_email/malware_2125/ia32_pe