Have you tried measuring compile-time on some benchmark with this patch. Changing unordered containers to ordered ones can increase compile-time. What if you simply sort the containers before iteration?
The keys are subclasses of llvm::Value, so sorting is hard. There's no obvious comparator to sort global variables. Instructions and basic blocks could be sorted based on DFS numbers, or something like that, but it would be a lot more complicated.
Looking again, a couple of these might not actually need to be ordered; in particular, BBs, and ConstCandMap. I'll spend a bit more time to try and verify that.