Reproducer: https://gist.github.com/mpickering/2a41aaa61dbf45ca6cb70615dc1d5364 When generating typeable evidence the types we need evidence for all cached in a `TypeMap`, the order terms are retrieved from a type map determines the order the bindings appear in the program. A `TypeMap` is quite diligent to use deterministic maps, apart from in the `TyLitMap`, which uses a `UniqFM` for storing strings, whose ordering depends on the `Unique` of the `FastString`. This can cause non-deterministic .hi and .o files.