Here's an incomplete (though essentially test-passing) patch that flips more of imp into importlib. It builds on Brett's patch. The gist is that imp.py is a minimal wrapper around importlib, which uses _imp directly.
Ultimately the things implemented in Lib/importlib/_bootstrap.py should be yanked out of Python/import.c (and Python/dynload_*.c). I expect that this will wait for the bootstrap merge (#2377) to land.
Here's a listing of the places where import-ish modules are used in CPython. Once things all the import stuff currently on the table is wrapped up, I'll probably work on switching things over to using importlib directly.
Regarding __all__, I didn't realize that about being a tuple. I'll fix it.
As to the "dm" in the SOABI value, that is definitely something we'll have to factor in. There are actually a few such places in the current patch that rely on problematic data. It's either hidden in C or not available during bootstrapping. That's something we'll have to iron out before the solution for this issue gets committed.
Just because I was thinking about it, I wonder if necessarily all the frozen stuff really needs to stay in import.c. I mean a frozen module is really just an entry in an array of structs that has a name of an char*. I don't see why one couldn't simply have a get_frozen_bytes() method to convert that char* into a bytes object and use that to construct a module in pure Python code.
OK, so I have started to check this stuff in, but I think it's best to do it piecemeal. Going forward I would like to commit in units of functions being replaced, and prioritize stuff that cuts out C code (e.g. the load_*() methods, find_module(), etc.). That way it's clear that progress is being made. Obviously the best way to tell if code is hanging on just because of imp is to comment out the interface code and see what your compiler complains about in terms of dead code (or at least clang is good at this).
It looks like in order to get a clear sign of what it will take to remove various parts of import.c, imp.load_module() needs to go along with imp.load_package() (since they call each other in the C code). You also have to take care of imp.reload(), but I am simplifying the C code greatly and will take care of referencing other code in the module.
I am seeing how this is going to go down. the load_dynamic, load_source, etc. family of functions are simply dispatched to by load_module(). So to keep some semblance of backwards-compatibility, each of those modules need to be implemented and then have load_module() simply dispatch to them based on the "type" of module it is.