Page MenuHomePhabricator

[ConstantHoisting] Fix non-determinism.

Authored by efriedma on Aug 12 2019, 3:17 PM.

Diff Detail


Event Timeline

efriedma created this revision.Aug 12 2019, 3:17 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 12 2019, 3:17 PM
Herald added a subscriber: mgrang. · View Herald Transcript

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.

efriedma updated this revision to Diff 219018.Sep 5 2019, 6:04 PM

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.

mgrang accepted this revision.Sep 10 2019, 9:56 AM


This revision is now accepted and ready to land.Sep 10 2019, 9:56 AM
This revision was automatically updated to reflect the committed changes.