Fix endless loop in illink analyzer (#86449)
authorVitek Karas <10670590+vitek-karas@users.noreply.github.com>
Tue, 23 May 2023 07:50:10 +0000 (00:50 -0700)
committerGitHub <noreply@github.com>
Tue, 23 May 2023 07:50:10 +0000 (00:50 -0700)
commit43f55afa6dd5268da00e606ae3c4d2401d850fd8
tree2a018e20717ac25a9a53362e1e75d9f14ca3fb34
parent1e421670a6456d9c5b924b7ffea14cab8559a2e9
Fix endless loop in illink analyzer (#86449)

The root cause is the fact that `ArrayValue` is mutable, so it needs to be `DeepCopy` everywhere. So the first set of fixes is to make sure that even hoisted locals are correctly copied.
The second problem is that we use `HashSet` to store multiple values in `ValueSet`/`MultiValue`. HashSet assumes that items don't change identity (equality group) while they're stored inside. But `ArrayValue` does exactly that. So we can't rely on pure `HashSet` functionality to implement `Equals`.

Changes:
* Make Maybe<T> an IDeepCopyValue and make sure it deep copies its value - because it can store values which require a deep copy
* Make ValueSet<T> an IDeepCopyValue since it can store values which require a deep copy (this causes an effective rename of MultiValue.Clone to MultiValue.DeepCopy - lot of files touched)
* Modify ValueSet<T> to be careful when comparing for equality - we can't rely on immutability of values and since we store them in a hashset, the hashset itself effectively breaks. Maybe we should consider switching to a simple List? But then we want to to unify same values.
* Modify array equality comparison - previously it caused an allocation of a `HashSet` - we compare values quite a bit (in analyzer during multi-pass analysis). Currently we rely on values in arrays to be immutable.

Future looking:
The data flow analysis simply doesn't have a solution for mutable values (mostly mutable refence types, but I think similar set of problems might occur with structs as well). ILLink implements by-ref values, which are probably the closest approximation yet, but the full CFG data flow doesn't support those yet. And ultimately it's probably more complex then just by-ref values.
Proper fix is complex, and requires some design work first.

Note that we will want to backport this to .NET 7 very likely - I haven't looked yet how well it will port.
15 files changed:
src/coreclr/tools/aot/ILCompiler.Compiler/Compiler/Dataflow/ArrayValue.cs
src/coreclr/tools/aot/ILCompiler.Compiler/Compiler/Dataflow/InterproceduralState.cs
src/coreclr/tools/aot/ILCompiler.Compiler/Compiler/Dataflow/TrimAnalysisAssignmentPattern.cs
src/coreclr/tools/aot/ILCompiler.Compiler/Compiler/Dataflow/TrimAnalysisMethodCallPattern.cs
src/tools/illink/src/ILLink.RoslynAnalyzer/DataFlow/InterproceduralState.cs
src/tools/illink/src/ILLink.RoslynAnalyzer/TrimAnalysis/ArrayValue.cs
src/tools/illink/src/ILLink.RoslynAnalyzer/TrimAnalysis/TrimAnalysisAssignmentPattern.cs
src/tools/illink/src/ILLink.RoslynAnalyzer/TrimAnalysis/TrimAnalysisMethodCallPattern.cs
src/tools/illink/src/ILLink.Shared/DataFlow/MaybeLattice.cs
src/tools/illink/src/ILLink.Shared/DataFlow/ValueSet.cs
src/tools/illink/src/linker/Linker.Dataflow/ArrayValue.cs
src/tools/illink/src/linker/Linker.Dataflow/InterproceduralState.cs
src/tools/illink/src/linker/Linker.Dataflow/TrimAnalysisAssignmentPattern.cs
src/tools/illink/src/linker/Linker.Dataflow/TrimAnalysisMethodCallPattern.cs
src/tools/illink/test/Mono.Linker.Tests.Cases/DataFlow/ArrayDataFlow.cs