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.
Got rid of a few changes that were clearly unnecessary, because we never iterated over the maps in question.
It's possible there are more lightweight solutions in a few of these cases. But anything that affects the order of the modifications performed by ConstantHoisting affects the use lists, at the very least, and the algorithms mostly don't impose any sort of natural ordering.