Cache the results of CanCompareValueTypeBits (#5468)

This is a recursive algorithm and there's a pathological test in the CoreCLR test assets that has been timing out ever since the code was introduced.

Made the cache a bit more general purpose, since I'm expecting this to be reused for more things later.

1 files changed, 94 insertions, 40 deletions

diff --git a/src/Common/src/TypeSystem/IL/TypeSystemContext.ValueTypeMethods.cs b/src/Common/src/TypeSystem/IL/TypeSystemContext.ValueTypeMethods.cs
index 7106b1980..a1487a5ac 100644
--- a/src/Common/src/TypeSystem/IL/TypeSystemContext.ValueTypeMethods.cs
+++ b/src/Common/src/TypeSystem/IL/TypeSystemContext.ValueTypeMethods.cs
@@ -71,71 +71,125 @@ namespace Internal.TypeSystem
             if (valueType.IsEnum)
                 return false;
 
-            return !CanCompareValueTypeBits(valueType);
+            return !_typeStateHashtable.GetOrCreateValue(valueType).CanCompareValueTypeBits;
         }
 
-        private bool CanCompareValueTypeBits(MetadataType type)
+        private class TypeState
         {
-            Debug.Assert(type.IsValueType);
-
-            if (type.ContainsGCPointers)
-                return false;
+            private enum Flags
+            {
+                CanCompareValueTypeBits         = 0x0000_0001,
+                CanCompareValueTypeBitsComputed = 0x0000_0002,
+            }
 
-            if (type.IsGenericDefinition)
-                return false;
+            private volatile Flags _flags;
+            private readonly TypeStateHashtable _hashtable;
 
-            OverlappingFieldTracker overlappingFieldTracker = new OverlappingFieldTracker(type);
+            public TypeDesc Type { get; }
 
-            bool result = true;
-            foreach (var field in type.GetFields())
+            public bool CanCompareValueTypeBits
             {
-                if (field.IsStatic)
-                    continue;
-
-                if (!overlappingFieldTracker.TrackField(field))
-                {
-                    // This field overlaps with another field - can't compare memory
-                    result = false;
-                    break;
-                }
-
-                TypeDesc fieldType = field.FieldType;
-                if (fieldType.IsPrimitive || fieldType.IsEnum || fieldType.IsPointer || fieldType.IsFunctionPointer)
+                get
                 {
-                    TypeFlags category = fieldType.UnderlyingType.Category;
-                    if (category == TypeFlags.Single || category == TypeFlags.Double)
+                    Flags flags = _flags;
+                    if ((flags & Flags.CanCompareValueTypeBitsComputed) == 0)
                     {
-                        // Double/Single have weird behaviors around negative/positive zero
-                        result = false;
-                        break;
+                        Debug.Assert(Type.IsValueType);
+                        if (ComputeCanCompareValueTypeBits((MetadataType)Type))
+                            flags |= Flags.CanCompareValueTypeBits;
+                        flags |= Flags.CanCompareValueTypeBitsComputed;
+
+                        _flags = flags;
                     }
+                    return (flags & Flags.CanCompareValueTypeBits) != 0;
                 }
-                else
+            }
+
+            public TypeState(TypeDesc type, TypeStateHashtable hashtable)
+            {
+                Type = type;
+                _hashtable = hashtable;
+            }
+
+            private bool ComputeCanCompareValueTypeBits(MetadataType type)
+            {
+                Debug.Assert(type.IsValueType);
+
+                if (type.ContainsGCPointers)
+                    return false;
+
+                if (type.IsGenericDefinition)
+                    return false;
+
+                OverlappingFieldTracker overlappingFieldTracker = new OverlappingFieldTracker(type);
+
+                bool result = true;
+                foreach (var field in type.GetFields())
                 {
-                    // Would be a suprise if this wasn't a valuetype. We checked ContainsGCPointers above.
-                    Debug.Assert(fieldType.IsValueType);
+                    if (field.IsStatic)
+                        continue;
 
-                    // If the field overrides Equals, we can't use the fast helper because we need to call the method.
-                    if (fieldType.FindVirtualFunctionTargetMethodOnObjectType(_objectEqualsMethod).OwningType == type)
+                    if (!overlappingFieldTracker.TrackField(field))
                     {
+                        // This field overlaps with another field - can't compare memory
                         result = false;
                         break;
                     }
 
-                    if (!CanCompareValueTypeBits((MetadataType)fieldType))
+                    TypeDesc fieldType = field.FieldType;
+                    if (fieldType.IsPrimitive || fieldType.IsEnum || fieldType.IsPointer || fieldType.IsFunctionPointer)
                     {
-                        result = false;
-                        break;
+                        TypeFlags category = fieldType.UnderlyingType.Category;
+                        if (category == TypeFlags.Single || category == TypeFlags.Double)
+                        {
+                            // Double/Single have weird behaviors around negative/positive zero
+                            result = false;
+                            break;
+                        }
+                    }
+                    else
+                    {
+                        // Would be a suprise if this wasn't a valuetype. We checked ContainsGCPointers above.
+                        Debug.Assert(fieldType.IsValueType);
+
+                        MethodDesc objectEqualsMethod = fieldType.Context._objectEqualsMethod;
+
+                        // If the field overrides Equals, we can't use the fast helper because we need to call the method.
+                        if (fieldType.FindVirtualFunctionTargetMethodOnObjectType(objectEqualsMethod).OwningType == fieldType)
+                        {
+                            result = false;
+                            break;
+                        }
+
+                        if (!_hashtable.GetOrCreateValue((MetadataType)fieldType).CanCompareValueTypeBits)
+                        {
+                            result = false;
+                            break;
+                        }
                     }
                 }
+
+                // If there are gaps, we can't memcompare
+                if (result && overlappingFieldTracker.HasGaps)
+                    result = false;
+
+                return result;
             }
+        }
 
-            // If there are gaps, we can't memcompare
-            if (result && overlappingFieldTracker.HasGaps)
-                result = false;
+        private class TypeStateHashtable : LockFreeReaderHashtable<TypeDesc, TypeState>
+        {
+            protected override int GetKeyHashCode(TypeDesc key) => key.GetHashCode();
+            protected override int GetValueHashCode(TypeState value) => value.Type.GetHashCode();
+            protected override bool CompareKeyToValue(TypeDesc key, TypeState value) => key == value.Type;
+            protected override bool CompareValueToValue(TypeState v1, TypeState v2) => v1.Type == v2.Type;
 
-            return result;
+            protected override TypeState CreateValueFromKey(TypeDesc key)
+            {
+                return new TypeState(key, this);
+            }
         }
+        private TypeStateHashtable _typeStateHashtable = new TypeStateHashtable();
 
         private struct OverlappingFieldTracker
         {