Dataflow analysis taking forever

[MichalStrehovsky]

Reported on Discord.

dotnet publish -p:PublishTrimmed the following code and notice we're stuck forever in the C# compilation phase:

typeof(object).GetMethod("Foo");

object[] data = new object[20];
if (true) data[0] = new object();
if (true) data[1] = new object();
if (true) data[2] = new object();
if (true) data[3] = new object();
if (true) data[4] = new object();
if (true) data[5] = new object();
if (true) data[6] = new object();
if (true) data[7] = new object();
if (true) data[8] = new object();
if (true) data[9] = new object();
if (true) data[10] = new object();
if (true) data[11] = new object();
if (true) data[12] = new object();
if (true) data[13] = new object();
if (true) data[14] = new object();
if (true) data[15] = new object();
if (true) data[16] = new object();
if (true) data[17] = new object();
if (true) data[18] = new object();
if (true) data[19] = new object();

Tagging subscribers to this area: @agocke, @sbomer, @vitek-karas
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Reported on Discord.

dotnet publish -p:PublishTrimmed the following code and notice we're stuck forever in the C# compilation phase:

typeof(object).GetMethod("Foo");

object[] data = new object[20];
if (true) data[0] = new object();
if (true) data[1] = new object();
if (true) data[2] = new object();
if (true) data[3] = new object();
if (true) data[4] = new object();
if (true) data[5] = new object();
if (true) data[6] = new object();
if (true) data[7] = new object();
if (true) data[8] = new object();
if (true) data[9] = new object();
if (true) data[10] = new object();
if (true) data[11] = new object();
if (true) data[12] = new object();
if (true) data[13] = new object();
if (true) data[14] = new object();
if (true) data[15] = new object();
if (true) data[16] = new object();
if (true) data[17] = new object();
if (true) data[18] = new object();
if (true) data[19] = new object();

Author:	MichalStrehovsky
Assignees:	-
Labels:	area-Tools-ILLink
Milestone:	-

[ZacharyPatten]

At first glance this ticket seems related to #86379 which already has a fix

[vitek-karas]

I thought so as well - but the code pattern doesn't match the root cause of that issue - at least I think it doesn't.
I'll have to debug into it.

[vitek-karas]

This is definitely a new problem. I don't think it hangs, it just takes really long time.
After about 30 seconds I can see a MultiValue which has 16834 distinct array values in it - doing anything with this is going to take a while, and given the number it looks like with each operation this doubles in size - so it's only going to get worse.

Obvesrvations:

• We don't even complete one full iteration of the CFG data flow algorithm - so it's not about iterating over and over the same code with mutating state (so this completely rules out PublishTrimmed causing dotnet publish to hang #86379)
• The code will create a branch of the state (a copy) for each branch in the analyzed method. Each such branch will modify values of all already stored states. After the branch we merge with the "else" which does nothing and so we double the size of the state. And so on...

I don't think there's anything wrong with the algorithm - the above code does have effectively 2^20 number of states if one assumes that the conditions are unpredictable (the analyzer doesn't handle constant conditions, so the fact that it has true doesn't make a difference).

I think the fix for this should be just introducing a cap on the number of states we're OK to track. I would probably just modify MultiValue to allow something like 100 different states (or similar order of magnitute number). Once it goes over such value, it would instead change to Unknown value - which means it effectively disables analysis with that value.

Ideally I'd like @sbomer to take another look at this to confirm the theory and the possible fix.

[sbomer]

The theory is right, and limiting the number of states seems like an ok fix for now. But in my mind, the root cause for this (and related issues we've been hitting) is that we never developed a model for the analysis of reference types. Ideally I'd expect this particular example to model the value as a single array, where each element is a ValueSet of two possible values by the end. It shouldn't have to track an exponential number of states.

[vitek-karas]

But in my mind, the root cause for this (and related issues we've been hitting) is that we never developed a model for the analysis of reference types.

You're right. That said having a limit is still a good thing in my mind - even if we fix reference values in the future.
Reference values are... I gave it some thought and it would require us to change lot of things. While I agree that the recent problems with arrays are annoying, I currently don't see much value in trying to model true reference values. We only make use of this for arrays and the arrays themselves are really only used in limited scenarios (MakeGeneric* is basically the only meaningful use case).

[agocke]

So, another way to think about this: the current analysis is beyond what C# or .NET normally allows in the type system. If we think about DAM as constraints, C# requires a uniform type for arrays, meaning you wouldn't be allowed to have different constraints for different array elements. If we determined a single type for arrays it would be closer to how .NET works. That said, it is less flexible. The general question is: does anyone strongly depend on the existing functionality?

[vitek-karas]

We want to be able to handle cases like:

typeof(Dictionaty<,>).MakeGenericType(new Type[] { typeof(Key), typeof(Value) });

And in that case we want to be able to statically know that we're creating Dictionary<Ket,Value>, or dynamically what annotations the various type parameters have.

This is basically the entire reason why we track arrays (there some other more esoteric cases, but we could probably live without those). Combine that with the CFG and you get where we're today :-)