This is an archive of the discontinued LLVM Phabricator instance.

Make block placement determinisatic
ClosedPublic

Authored by xur on Nov 14 2016, 1:39 PM.

Details

Summary

We fail to produce bit-to-bit matching stage2 and stage3 compiler in PGO bootstrap build. The reason is because LoopBlockSet is of SmallPtrSet type whose iterating order depends on the pointer value.

This patch fixes this issue.

Diff Detail

Event Timeline

xur updated this revision to Diff 77876.Nov 14 2016, 1:39 PM
xur retitled this revision from to Make block placement determinisatic.
xur updated this object.
xur added reviewers: davidxl, chandlerc.
xur added a subscriber: llvm-commits.
davidxl added inline comments.Nov 14 2016, 2:06 PM
lib/CodeGen/MachineBlockPlacement.cpp
1498 ↗(On Diff #77876)

This fix has compile time implication. Two alternatives:

  1. make collectLoopBlockSet to also compute a vector of blocks in fixed order

or

  1. change BlockFilterSet to be a set of integers where the integer is MBB's unique id: getNumber()
mkuper added a subscriber: mkuper.Nov 14 2016, 2:22 PM
mkuper added inline comments.
lib/CodeGen/MachineBlockPlacement.cpp
1498 ↗(On Diff #77876)

Another alternative is to change BlockFilterSet to be a SetVector instead of a SmallPtrSet.
("The drawback of SetVector is that it requires twice as much space as a normal set and has the sum of constant factors from the set-like container and the sequential container that it uses. Use it only if you need to iterate over the elements in a deterministic order")

Or is it also too expensive in this case?

davidxl added inline comments.Nov 14 2016, 2:35 PM
lib/CodeGen/MachineBlockPlacement.cpp
1498 ↗(On Diff #77876)

Dannyb also made the same suggestion. I think SetVector is basically that is needed.

xur updated this revision to Diff 77937.Nov 14 2016, 6:17 PM

Use SmallSetVector as suggested by the reviewers.

davidxl accepted this revision.Nov 15 2016, 4:38 PM
davidxl edited edge metadata.

lgtm

This revision is now accepted and ready to land.Nov 15 2016, 4:38 PM

Note that SetVector::remove is O(n) whereas SmallPtrSet::erase was O(1). I guess it doesn't matter too much, land this now to make codegen deterministic again. If perf issues arise we can come up with a more clever way (e.g. sorting by block number before iterating over the set).

This revision was automatically updated to reflect the committed changes.