Change Description:

     This is the implementation of generic unification for separate compilation.

     When we do not use global analysis, we may end up with multiple instances of generic types and methods in different modules. This causes problems for access to static fields, type casting and reflection, notably GetMethodInfo on delegates.

     The implementation proposed has two main components:
      - the binder generates "GenericUnificiationDesc" data structures for each generic type and method. It also indirects accesses to generic types and methods through indirection cells. The mechanism is enabled via a new "/separateCompilation" command line switch.
     - the runtime enters the generic types and methods into a big hash table. If it finds a duplicate, it declares the existing entry the "winner" and overwrites the indirection cells of the "loser" with those of the winner.

     Initial measurements on UnitTests are as follows:
      - about 8,000 types and methods are entered into the hash table on startup
      - about 2,000 duplicates are found (most are between UnitTests and UnitTests.McgInterop)
      - the total number of indirection cells is about 23,000
      - the elapsed time to hash the 8000 types and methods is about 3 milliseconds (11 million clock cycles as measured by the rdtsc instruction, see instrumentation in GenericUnification.cpp).

     I also added interning of generic composition structures which seems to roughly halve the space taken by them.

[tfs-changeset: 1625336]

1 files changed, 236 insertions, 0 deletions

diff --git a/src/Native/Runtime/GenericUnification.cpp b/src/Native/Runtime/GenericUnification.cpp
new file mode 100644
index 000000000..f1c1e2211
--- /dev/null
+++ b/src/Native/Runtime/GenericUnification.cpp
@@ -0,0 +1,236 @@
+// Licensed to the .NET Foundation under one or more agreements.
+// The .NET Foundation licenses this file to you under the MIT license.
+// See the LICENSE file in the project root for more information.
+#include "common.h"
+#include "CommonTypes.h"
+#include "CommonMacros.h"
+#include "daccess.h"
+#include "PalRedhawkCommon.h"
+#include "PalRedhawk.h"
+#include "rhassert.h"
+#include "slist.h"
+#include "holder.h"
+#include "Crst.h"
+#include "rhbinder.h"
+#include "RWLock.h"
+#include "RuntimeInstance.h"
+#include "GenericUnification.h"
+#include "EEType.h"
+
+bool GenericUnificationHashtable::GrowTable(UInt32 minSize)
+{
+    // immediately give up for ridiculously large sizes
+    if (minSize >= 1024 * 1024 * 1024 / sizeof(Entry *))
+        return false;
+
+    UInt32 newSize = max(1024, m_tableSize);
+    while (newSize < minSize)
+        newSize *= 2;
+
+    // newSize should be a power of 2 as we always double the size of the table
+    // we rely on this property, otherwise masking off bits to index wouldn't work
+    ASSERT((newSize & (newSize - 1)) == 0);
+
+    Entry ** newTable = new (nothrow) Entry*[newSize];
+    if (newTable == nullptr)
+        return false;
+
+    memset(newTable, 0, sizeof(newTable[0])*newSize);
+    UInt32 newHashMask = newSize - 1;
+
+    for (UInt32 i = 0; i < m_tableSize; i++)
+    {
+        Entry * pNextEntry;
+        for (Entry *pEntry = m_table[i]; pEntry != nullptr; pEntry = pNextEntry)
+        {
+            pNextEntry = pEntry->m_nextInHash;
+
+            GenericUnificationDesc * pDesc = pEntry->m_desc;
+            UInt32 hashCode = pDesc->m_hashCode & newHashMask;
+
+            pEntry->m_nextInHash = newTable[hashCode];
+            newTable[hashCode] = pEntry;
+        }
+    }
+
+    if (m_table != nullptr)
+        delete[] m_table;
+
+    m_table = newTable;
+    m_tableSize = newSize;
+    m_hashMask = newHashMask;
+
+    return true;
+}
+
+
+// this generic type or method is not a duplicate - enter it into the hash table
+bool GenericUnificationHashtable::EnterDesc(GenericUnificationDesc *pDesc, UIntTarget *pIndirCells)
+{
+    if (m_tableSize < m_entryCount)
+    {
+        if (!GrowTable(m_entryCount))
+            return false;
+    }
+
+    m_entryCount++;
+    
+    UInt32 hashCode = pDesc->m_hashCode & m_hashMask;
+
+    Entry *pEntry = new (nothrow) Entry(m_table[hashCode], pDesc, pIndirCells);
+    if (pEntry == nullptr)
+        return false;
+    m_table[hashCode] = pEntry;
+
+    if (pDesc->m_flags & GUF_GC_STATICS)
+    {
+        UInt32 indirCellIndex = pDesc->GetIndirCellIndex(GUF_GC_STATICS);
+        UInt8 *pGcStaticData = (UInt8 *)pIndirCells[indirCellIndex];
+        StaticGcDesc *pGcStaticsDesc = (StaticGcDesc *)pIndirCells[indirCellIndex + 1];
+        if (!GetRuntimeInstance()->AddDynamicGcStatics(pGcStaticData, pGcStaticsDesc))
+            return false;
+    }
+
+    if (pDesc->m_flags & GUF_THREAD_STATICS)
+    {
+        UInt32 indirCellIndex = pDesc->GetIndirCellIndex(GUF_THREAD_STATICS);
+        UInt32 tlsIndex = *(UInt32 *)pIndirCells[indirCellIndex];
+        UInt32 tlsOffset = (UInt32)pIndirCells[indirCellIndex + 1];
+        StaticGcDesc *pGcStaticsDesc = (StaticGcDesc *)pIndirCells[indirCellIndex + 2];
+        if (!GetRuntimeInstance()->AddDynamicThreadStaticGcData(tlsIndex, tlsOffset, pGcStaticsDesc))
+            return false;
+    }
+
+    return true;
+}
+
+
+// we have found a duplicate - copy the indirection cells from the winner over those from the loser
+void GenericUnificationHashtable::CopyIndirCells(Entry *pWinnerEntry, GenericUnificationDesc *pLoserDesc, UIntTarget *pLoserIndirCells)
+{
+    GenericUnificationDesc *pWinnerDesc = pWinnerEntry->m_desc;
+    UIntTarget *pWinnerIndirCells = pWinnerEntry->m_indirCells;
+
+    ASSERT(pWinnerDesc->m_flags == pLoserDesc->m_flags);
+
+    UInt32 winnerIndirCellCount = pWinnerDesc->GetIndirCellCount();
+    UInt32 loserIndirCellCount = pLoserDesc->GetIndirCellCount();
+
+    ASSERT(winnerIndirCellCount == loserIndirCellCount);
+    for (UInt32 i = 0; i < winnerIndirCellCount; i++)
+    {
+        if (i < loserIndirCellCount && pWinnerIndirCells[i] != 0)
+        {
+            pLoserIndirCells[i] = pWinnerIndirCells[i];
+        }
+    }
+}
+
+
+// unify one generic type or method
+bool GenericUnificationHashtable::UnifyDesc(GenericUnificationDesc *pDesc, UIntTarget *pIndirCells)
+{
+    UInt32 hashCode = pDesc->m_hashCode & m_hashMask;
+
+    for (Entry *pEntry = m_table[hashCode]; pEntry != nullptr; pEntry = pEntry->m_nextInHash)
+    {
+        if (pEntry->m_desc->Equals(pDesc))
+        {
+            CopyIndirCells(pEntry, pDesc, pIndirCells);
+
+#if defined(GENERIC_UNIFICATION_STATS)
+            m_duplicateCount++;
+#endif
+
+            return true;
+        }
+    }
+    return EnterDesc(pDesc, pIndirCells);
+}
+
+#if defined(GENERIC_UNIFICATION_STATS)
+#ifdef _X86_
+static UInt64 GetTicks()
+{
+    _asm rdtsc
+}
+#else
+#define GetTicks    PalGetTickCount
+#endif
+#endif
+
+// unify an array of descriptors describing a parallel array of indirection cells
+bool GenericUnificationHashtable::UnifyDescs(GenericUnificationDesc *descs, UInt32 descCount, UIntTarget *pIndirCells, UInt32 indirCellCount)
+{
+    UNREFERENCED_PARAMETER(indirCellCount);
+    ASSERT(descCount < 128 * 1024 * 1024);
+    if (m_tableSize < descCount)
+    {
+        if (!GrowTable(descCount))
+            return false;
+    }
+
+#if defined(GENERIC_UNIFICATION_STATS)
+    m_indirCellCount += indirCellCount;
+    UInt64 startTicks = GetTicks();
+#endif
+
+    UInt32 indirCellIndex = 0;
+    for (UInt32 i = 0; i < descCount; i++)
+    {
+        ASSERT(indirCellIndex <= indirCellCount);
+        ASSERT(descs[i].GetIndirCellCount() <= indirCellCount - indirCellIndex);
+        if (!UnifyDesc(&descs[i], &pIndirCells[indirCellIndex]))
+            return false;
+        indirCellIndex += descs[i].GetIndirCellCount();
+    }
+
+#if defined(GENERIC_UNIFICATION_STATS)
+    UInt64 elapsedTicks = GetTicks() - startTicks;
+    m_elapsedTicks += elapsedTicks;
+#endif
+
+    return true;
+}
+
+
+bool GenericUnificationDesc::Equals(GenericUnificationDesc *that)
+{
+    if (this->m_hashCode != that->m_hashCode)
+        return false;
+
+    if (this->m_openType.GetValue() != that->m_openType.GetValue())
+        return false;
+
+    if (this->GetOrdinal() != that->GetOrdinal())
+        return false;
+
+    return this->m_genericComposition->Equals(that->m_genericComposition);
+}
+
+
+bool GenericComposition::Equals(GenericComposition *that)
+{
+    if (this->m_arity != that->m_arity)
+        return false;
+
+    EETypeRef *thisArgList = this->GetArguments();
+    EETypeRef *thatArgList = that->GetArguments();
+
+    for (unsigned i = 0; i < m_arity; i++)
+    {
+        EEType *thisArg = thisArgList[i].GetValue();
+        EEType *thatArg = thatArgList[i].GetValue();
+
+        if (thisArg == thatArg)
+            continue;
+
+        if (thisArg == CANON_EETYPE || thatArg == CANON_EETYPE)
+            return false;
+
+        if (!thisArg->IsEquivalentTo(thatArg))
+            return false;
+    }
+
+    return true;
+}