Make block placement determinisatic

[xur]

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.

[davidxl]

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

2. change BlockFilterSet to be a set of integers where the integer is MBB's unique id: getNumber()

[mkuper]

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]

lib/CodeGen/MachineBlockPlacement.cpp

1498 ↗

(On Diff #77876)

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

[xur]

Use SmallSetVector as suggested by the reviewers.

[davidxl]

lgtm

[bkramer]

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).

llvm/trunk/lib/CodeGen/MachineBlockPlacement.cpp

#endif // NDEBUG
   /// and then once for the function as a whole.
   unsigned UnscheduledPredecessors;
 };
 }
 
 namespace {
 class MachineBlockPlacement : public MachineFunctionPass {
   /// \brief A typedef for a block filter set.
-  typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet;
+  typedef SmallSetVector<MachineBasicBlock *, 16> BlockFilterSet;
 
   /// \brief work lists of blocks that are ready to be laid out
   SmallVector<MachineBasicBlock *, 16> BlockWorkList;
   SmallVector<MachineBasicBlock *, 16> EHPadWorkList;
 
   /// \brief Machine Function
   MachineFunction *F;
 
DEBUG({
     if (LoopChain.UnscheduledPredecessors) {
       BadLoop = true;
       dbgs() << "Loop chain contains a block without its preds placed!\n"
              << "  Loop header:  " << getBlockName(*L.block_begin()) << "\n"
              << "  Chain header: " << getBlockName(*LoopChain.begin()) << "\n";
     }
     for (MachineBasicBlock *ChainBB : LoopChain) {
       dbgs() << "          ... " << getBlockName(ChainBB) << "\n";
-      if (!LoopBlockSet.erase(ChainBB)) {
+      if (!LoopBlockSet.remove(ChainBB)) {
         // We don't mark the loop as bad here because there are real situations
         // where this can occur. For example, with an unanalyzable fallthrough
         // from a loop block to a non-loop block or vice versa.
         dbgs() << "Loop chain contains a block not contained by the loop!\n"
                << "  Loop header:  " << getBlockName(*L.block_begin()) << "\n"
                << "  Chain header: " << getBlockName(*LoopChain.begin()) << "\n"
                << "  Bad block:    " << getBlockName(ChainBB) << "\n";
       }
auto RemovalCallback =
           RemoveList.erase(
               remove_if(RemoveList,
                         [RemBB](MachineBasicBlock *BB) {return BB == RemBB;}),
               RemoveList.end());
         }
 
         // Handle the filter set
         if (BlockFilter) {
-          BlockFilter->erase(RemBB);
+          BlockFilter->remove(RemBB);
         }
 
         // Remove the block from loop info.
         MLI->removeBlock(RemBB);
         if (RemBB == PreferredLoopExit)
           PreferredLoopExit = nullptr;
 
         DEBUG(dbgs() << "TailDuplicator deleted block: "