Eliminate dead branches around typeof comparisons #102248

MichalStrehovsky · 2024-05-15T09:08:41Z

RyuJIT will already do dead branch elimination for typeof(X) == typeof(Y) patterns, but we couldn't do elimination around foo == typeof(X). This fixes that using whole program knowledge - if we never saw a constructed MT for X, the comparison is not going to be true. Because it needs whole program, we still scan this dead branch so in the end this doesn't save much. We can eventually do better.

I'm doing this in SubstitutedILProvider instead of in RyuJIT: this is because we currently only reap a small benefit from this optimization due to it only happening during compilation phase. We need to do this during scanning as well. I think I can extend it to scannig. But the extension will require the optimization to 100% guaranteed happen during codegen. We cannot rely on whether RyuJIT will feel like it. SubstitutedILProvider is our way to ensure the optimization will happen no matter what - the IL from the branch will be gone and RyuJIT can at most remove the comparison (we don't mind much if it's left).

Cc @dotnet/ilc-contrib

RyuJIT will already do dead branch elimination for `typeof(X) == typeof(Y)` patterns, but we couldn't do elimination around `foo == typeof(X)`. This fixes that using whole program knowledge - if we never saw a constructed `MT` for `X`, the comparison is not going to be true. Because it needs whole program, we still scan this dead branch so in the end this doesn't save much. We can eventually do better. I'm doing this in `SubstitutedILProvider` instead of in RyuJIT: this is because we currently only reap a small benefit from this optimization due to it only happening during compilation phase. We need to do this during scanning as well. I think I can extend it to scannig. But the extension will require the optimization to 100% guaranteed happen during codegen. We cannot rely on whether RyuJIT will feel like it. `SubstitutedILProvider` is our way to ensure the optimization will happen no matter what - the IL from the branch will be gone and RyuJIT can at most remove the comparison (we don't mind much if it's left).

dotnet-policy-service · 2024-05-15T09:09:11Z

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

MichalStrehovsky · 2024-05-15T18:08:31Z

/azp run runtime-nativeaot-outerloop

azure-pipelines · 2024-05-15T18:08:41Z

Azure Pipelines successfully started running 1 pipeline(s).

jkotas · 2024-05-15T23:40:37Z

src/coreclr/tools/aot/ILCompiler.Compiler/Compiler/SubstitutedILProvider.cs


+                // We don't actually mind if this is not Object.GetType


If it is an arbitrary call, can it return a type that happens to be equal to the other type?

Or is the idea that this case will fail the CanReferenceConstructedTypeOrCanonicalFormOfType check below? Ie the other argument can be anything. We are just skipping the specific common patterns here to keep things simple.

Yes, we should be okay with any value loaded from a local or parameter. So also any value a method call could return.

We just don't have facilities to accept any value, so only a couple recognized patterns are allowed. Allowing any instance method call is less work than also checking if it's object.GetType.

jkotas · 2024-05-17T05:18:12Z

src/coreclr/tools/aot/ILCompiler.Compiler/Compiler/SubstitutedILProvider.cs

+            if (knownType.IsCanonicalDefinitionType(CanonicalFormKind.Any))
+                return false;
+
+            if (_devirtualizationManager.CanReferenceConstructedTypeOrCanonicalFormOfType(knownType))


Do we need to call convert ConvertToCanonForm before calling CanReferenceConstructedTypeOrCanonicalFormOfType? Or is the type guaranteed to be normalized somehow?

Yes, we should convert to canon. Good catch.

jkotas · 2024-05-17T07:01:17Z

I have run this under debugger on this simple test:

using System;

static class Program
{
    static void Main(string[] args)
    {
        if (typeof(MyType) == args.GetType())
            Console.WriteLine(42);
    }
}

static class MyType
{
}

I would expect the substitution to trigger for it, but it is not happening. It never hits breakpoint at this line https://github.com/dotnet/runtime/pull/102248/files#diff-7c5a8ad684ce4e7f583b3bc392219bb15fc17e8400b172a2ae32d5301b7cdd0bR1027 . Is that expected?

MichalStrehovsky · 2024-05-17T07:06:39Z

It never hits breakpoint at this line https://github.com/dotnet/runtime/pull/102248/files#diff-7c5a8ad684ce4e7f583b3bc392219bb15fc17e8400b172a2ae32d5301b7cdd0bR1027 . Is that expected?

Yes, you need to flip them to the more common pattern.

The problem is in the IL scanner. IL scanner only does the "downgrade result of typeof to necessary MethodTable" for a limited set of IL patterns as well and this one is not it. So we end up with "constructed MethodTable is needed" in the scanning phase, and this can no longer get optimized away.

runtime/src/coreclr/tools/aot/ILCompiler.Compiler/IL/ILImporter.Scanner.cs

Lines 872 to 897 in 4246ba1

    
           // We expect pattern: 
        
           // 
        
           // ldtoken Foo 
        
           // call GetTypeFromHandle 
        
           // ldtoken Bar 
        
           // call GetTypeFromHandle 
        
           // call Equals 
        
           // 
        
           // We check for both ldtoken cases 
        
           if ((ILOpcode)_ilBytes[_currentOffset + 5] == ILOpcode.call) 
        
           { 
        
               methodToken = ReadILTokenAt(_currentOffset + 6); 
        
               method = (MethodDesc)_methodIL.GetObject(methodToken); 
        
               isTypeEquals = IsTypeEquals(method); 
        
           } 
        
           else if ((ILOpcode)_ilBytes[_currentOffset + 5] == ILOpcode.ldtoken 
        
               && _basicBlocks[_currentOffset + 10] == null 
        
               && (ILOpcode)_ilBytes[_currentOffset + 10] == ILOpcode.call 
        
               && methodToken == ReadILTokenAt(_currentOffset + 11) 
        
               && _basicBlocks[_currentOffset + 15] == null 
        
               && (ILOpcode)_ilBytes[_currentOffset + 15] == ILOpcode.call) 
        
           { 
        
               methodToken = ReadILTokenAt(_currentOffset + 16); 
        
               method = (MethodDesc)_methodIL.GetObject(methodToken); 
        
               isTypeEquals = IsTypeEquals(method); 
        
           }

We really need some better facilities to analyze IL in C#, but also I don't know if I want us to build a "proper" IL importer in C#.

MichalStrehovsky · 2024-05-17T07:07:26Z

(I plan to look into at least sharing this code between scanner and substitutions in some way.)

jkotas · 2024-05-17T08:00:07Z

Could you please share a program that hits this line https://github.com/dotnet/runtime/pull/102248/files#diff-7c5a8ad684ce4e7f583b3bc392219bb15fc17e8400b172a2ae32d5301b7cdd0bR1027 in the compiler? Or is this WIP and this path is not reachable yet?

MichalStrehovsky · 2024-05-17T08:05:53Z

Could you please share a program that hits this line https://github.com/dotnet/runtime/pull/102248/files#diff-7c5a8ad684ce4e7f583b3bc392219bb15fc17e8400b172a2ae32d5301b7cdd0bR1027 in the compiler? Or is this WIP and this path is not reachable yet?

It's the tests that are part of this PR. We also have hits in corelib, for example:

runtime/src/coreclr/nativeaot/System.Private.CoreLib/src/System/Reflection/Runtime/General/Helpers.cs

Lines 177 to 188 in 4246ba1

    
           if (attributeType == typeof(DecimalConstantAttribute)) 
        
           { 
        
               return GetRawDecimalConstant(attributeData); 
        
           } 
        
           else if (attributeType.IsSubclassOf(typeof(CustomConstantAttribute))) 
        
           { 
        
               if (attributeType == typeof(DateTimeConstantAttribute)) 
        
               { 
        
                   return GetRawDateTimeConstant(attributeData); 
        
               } 
        
               return GetRawConstant(attributeData); 
        
           }

(The above will also be a real saving once we can do this optimization in the scanner - this is the only places that boxes DateTime and Decimal and that's a 100 kB saving on an app that uses reflection. It doesn't kick in right now, because the scanner will see we box DateTime/decimal and that destroys our opportunity to get rid of it because DateTime/decimal is referenced in typeof comparisons in other spots.)

jkotas · 2024-05-17T08:30:38Z

It's the tests that are part of this PR.

I have extracted the test into a small program:

using System;
using System.Runtime.CompilerServices;

static class Program
{
    static void Main(string[] args)
    {
        Type someType = GetTheType();
        if (someType == typeof(Never3))
        {
            Console.WriteLine(42);
        }
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    static Type GetTheType() => null;
}

class Never3
{
}

I have compiled the test in release mode (the test is under #if !DEBUG). Roslyn optimized out the someType local variable and the IL looks like this:

    IL_0000:  call       class [System.Runtime]System.Type Program::GetTheType()
    IL_0005:  ldtoken    MyType
    IL_000a:  call       class [System.Runtime]System.Type [System.Runtime]System.Type::GetTypeFromHandle(valuetype [System.Runtime]System.RuntimeTypeHandle)
    IL_000f:  call       bool [System.Runtime]System.Type::op_Equality(class [System.Runtime]System.Type,
                                                                       class [System.Runtime]System.Type)

It fails the pattern match in TryExpandTypeEquality_TokenOther very early since the ldloc that the pattern match is looking for is gone. What am I missing?

MichalStrehovsky · 2024-05-17T10:17:05Z

Weird, I don't know how the test would pass without it. I've submitted #102374 with just the test because I don't want to switch branches locally right now.

MichalStrehovsky · 2024-05-17T11:30:36Z

Weird, I don't know how the test would pass without it. I've submitted #102374 with just the test because I don't want to switch branches locally right now.

The tests are all failing in #102374 so the optimization here works. I agree that for the local case this is pretty fragile. This is another case where the expectation is that this will mostly come from a parameter in real world code. Loading it from a local was just equally cheap in the pattern match so I just allowed it. But parameter is the main use case.

jkotas · 2024-05-17T21:35:36Z

I have figured out one of the mysteries:

The dotnet/runtime build sets DebugSymbols property to true globally. DebugSymbols does not actually do what its name suggests. The (portable) symbols are generated regardless of whether this property is true or false. What this property actually does is that it disables C# peephole IL optimizations. The C# peephole IL optimizations break the IL patterns used by the tests added in this PR. Setting the DebugSymbols to false makes the tests fail as demonstrated by #102391 . It would be nice to fix the pattern match and/or the test to work with DebugSymbols set to false.

The ordinary user projects out there do not set DebugSymbols property. I have done my quick ad-hoc test using an ordinary project and it is why it did not work for me. I will look into deleting the DebugSymbols setting so that we build and test our bits using the same settings as our users.

jkotas · 2024-05-18T02:25:51Z

Yes, you need to flip them to the more common pattern.

Ok, this was the other part of the mystery. if (t == typeof(Never)) works as expected, if (typeof(Never) == t) does not work as expected. The code added in this PR handles it, but the pre-existing ldtoken handling in the scanner does not as you have pointed out.

jkotas · 2024-05-23T03:54:28Z

src/coreclr/tools/aot/ILCompiler.Compiler/Compiler/ILScanner.cs

+            {
+                Debug.Assert(type.NormalizeInstantiation() == type);
+                Debug.Assert(ConstructedEETypeNode.CreationAllowed(type));
+                return _constructedMethodTables.Contains(type);


Should we also assert that we are only adding normalizations into _constructedMethodTables when it is populated?

jkotas

Thanks

MichalStrehovsky added the area-NativeAOT-coreclr label May 15, 2024

dotnet-policy-service bot assigned MichalStrehovsky May 15, 2024

github-actions bot mentioned this pull request May 15, 2024

102248 MichalStrehovsky/rt-sz#21

Closed

Update TrimmingDriver.cs

6beca33

build-analysis bot mentioned this pull request May 15, 2024

NativeAOT legs timing out in CI #102239

Open

jkotas reviewed May 15, 2024

View reviewed changes

jkotas reviewed May 17, 2024

View reviewed changes

Fixes

31c52b0

jkotas closed this May 21, 2024

jkotas reopened this May 21, 2024

This was referenced May 21, 2024

Abort on mono in SwiftErrorHandling #102478

Closed

SupportedLinuxPlatforms_IsSupportedIsTrue failed in CI #102479

Closed

jkotas reviewed May 23, 2024

View reviewed changes

jkotas approved these changes May 23, 2024

View reviewed changes

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Eliminate dead branches around typeof comparisons #102248

Eliminate dead branches around typeof comparisons #102248

MichalStrehovsky commented May 15, 2024

dotnet-policy-service bot commented May 15, 2024

MichalStrehovsky commented May 15, 2024

azure-pipelines bot commented May 15, 2024

jkotas May 15, 2024

MichalStrehovsky May 16, 2024

jkotas May 17, 2024

MichalStrehovsky May 17, 2024

jkotas commented May 17, 2024

MichalStrehovsky commented May 17, 2024

MichalStrehovsky commented May 17, 2024

jkotas commented May 17, 2024

MichalStrehovsky commented May 17, 2024

jkotas commented May 17, 2024

MichalStrehovsky commented May 17, 2024

MichalStrehovsky commented May 17, 2024

jkotas commented May 17, 2024 •

edited

jkotas commented May 18, 2024 •

edited

jkotas May 23, 2024

jkotas left a comment

Eliminate dead branches around typeof comparisons #102248

Are you sure you want to change the base?

Eliminate dead branches around typeof comparisons #102248

Conversation

MichalStrehovsky commented May 15, 2024

dotnet-policy-service bot commented May 15, 2024

MichalStrehovsky commented May 15, 2024

azure-pipelines bot commented May 15, 2024

jkotas May 15, 2024

Choose a reason for hiding this comment

MichalStrehovsky May 16, 2024

Choose a reason for hiding this comment

jkotas May 17, 2024

Choose a reason for hiding this comment

MichalStrehovsky May 17, 2024

Choose a reason for hiding this comment

jkotas commented May 17, 2024

MichalStrehovsky commented May 17, 2024

MichalStrehovsky commented May 17, 2024

jkotas commented May 17, 2024

MichalStrehovsky commented May 17, 2024

jkotas commented May 17, 2024

MichalStrehovsky commented May 17, 2024

MichalStrehovsky commented May 17, 2024

jkotas commented May 17, 2024 • edited

jkotas commented May 18, 2024 • edited

jkotas May 23, 2024

Choose a reason for hiding this comment

jkotas left a comment

Choose a reason for hiding this comment

jkotas commented May 17, 2024 •

edited

jkotas commented May 18, 2024 •

edited