Hello Eddie,
Thank you for putting what looks to be significant effort into this PR.  It would be great if we can get this fixed.  There is a real issue about breaking 3rd party extensions.  So, we want to proceed with care.

I wonder, if we are going to break extensions already, could we just remove the whole concept of heap allocated types?  If you look through the CPython source code, I think you will find a lot of tricky code that deals with the Py_TPFLAGS_HEAPTYPE case.  If we could remove heap types, we could remove all those cases.  That would give some performance improvement but more importantly would simplify the implementation.

If PyType_FromSpec() is now working correctly, could we just move everything that the currently a heap type to use that?  Obviously we have to give 3rd party extensions a lot of time to get themselves updated.  Maybe give a deprecation warning if Py_TPFLAGS_HEAPTYPE is used.  You could have a configuration option for Python that enables or disables the Py_TPFLAGS_HEAPTYPE support.  Once we think extensions have been given enough time to update themselves, we can remove Py_TPFLAGS_HEAPTYPE.

Some other possible advantages of getting rid of heap types:

- GC objects will always have the GC header allocated (because CPython controls the allocation of the chunk of memory for the type)

- might be possible to eliminate GC headers and use bitmaps.  I have been experimenting with the idea but it seems to require that we don't use heap types.  Initially I was interested in the bitmap idea because of memory savings.  After more tinkering, I think the big win will be in eliminating linked-list traversals.  On modern CPUs, that's slow and iterating over a bitmap should be much faster.

- I suspect heap types are difficult to support for PyPy.  I haven't looked into that but it seems tricky when you have non-refcounting GC

- type_is_gc() is ugly and would go away.  Based on my profiling, PyObject_IS_GC() is pretty expensive.  A lot of types have the tp_is_gc slot set (more than you would expect).

- In the very long term, using PyType_FromSpec() could give us the freedom to change the structure layout of types.  I don't have any specific ideas about that but it seems like a better design.