[ADCE] Use MapVector for BlockInfo to make iteration order deterministic

[uabelho]

Summary

Also added a reserve() method to MapVector since we want to use that from
ADCE.

DenseMap does not provide deterministic iteration order so with that
we will handle the members of BlockInfo in random order, eventually
leading to random order of the blocks in the predecessor lists.

Without this change, I get the same predecessor order in about 90% of the
time when I compile a certain reproducer and in 10% I get a different one.

No idea how to make a proper test case for this.

[uabelho]

I don't know who should review this. Added David, who seems to have introduced the BlockInfo map,
and Jakub who has done non-NFC changes to ADCE fairly recently.

[uabelho]

foo.ll4 KBDownload

I see the random changes in output when I run opt on the attached foo.ll with:

opt -S -Os -o foo.opt.ll foo.ll -bdce -jump-threading -adce

In some cases I get
bb11: ; preds = %bb8, %bb4
and in some cases I get
bb11: ; preds = %bb4, %bb8

[kuhar]

lib/Transforms/Scalar/ADCE.cpp

214

I can see that MapVector doesn't expose .reserve -- what is the reason for that? While I don't claim that it would have any noticeable performance impact here, I'm a bit surprised by that.

[uabelho]

lib/Transforms/Scalar/ADCE.cpp

214

Unfortunately I have no idea. I just noticed there is no such function, and thus removed the call.

I don't really understand the comment preceding the original reserve call though, it says "so we grow the structure to twice that size", but then it only reserves NumBlocks anyway? Not 2*Numblocks?

[kuhar]

lib/Transforms/Scalar/ADCE.cpp

214

I think it was meant to be .reserve(NumBlocks * 2), but it also makes sense to just reduce the number of allocations.

I looked at MapVector and it should very easy to add reserve to it. Then, I think it would make sense to keep it here, and to update the comment or size for whichever makes more sense.

[uabelho]

Added a reserve method to MapVector, and restored the call to BlockInfo.reserve(NumBlocks) in ADCE.

MapVector::reserve() just passes on the call to Vector.reserve()

[uabelho]

lib/Transforms/Scalar/ADCE.cpp

214

Yes, you're right. I created a reserve method now. I left the original reserve code and comment in ADCE
in place since I don't know what makes most sense, and also, fixing the amout we reserve is not the focus of this patch anyway.

[kuhar]

include/llvm/ADT/MapVector.h

62 ↗

(On Diff #121467)

Shouldn't this reserve Map as well?

[uabelho]

include/llvm/ADT/MapVector.h

62 ↗

(On Diff #121467)

Ah, I guess so. Sorry, I'll update. Thanks!

[uabelho]

Pass on MapVector::reserve to Map.reserve() as well as Vector.reserve()

[kuhar]

LGTM

[uabelho]

Thanks a bunch for the comments! I'll push this in a bit.

lib/Transforms/Scalar/ADCE.cpp

 // catch, particularly involving loop computations.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/ADCE.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/BasicBlock.h"
class AggressiveDeadCodeElimination {
   Function &F;
 
   // ADCE does not use DominatorTree per se, but it updates it to preserve the
   // analysis.
   DominatorTree &DT;
   PostDominatorTree &PDT;
 
   /// Mapping of blocks to associated information, an element in BlockInfoVec.
-  DenseMap<BasicBlock *, BlockInfoType> BlockInfo;
+  /// Use MapVector to get deterministic iteration order.
+  MapVector<BasicBlock *, BlockInfoType> BlockInfo;
   bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; }
 
   /// Mapping of instructions to associated information.
   DenseMap<Instruction *, InstInfoType> InstInfo;
   bool isLive(Instruction *I) { return InstInfo[I].Live; }
 
   /// Instructions known to be live where we need to mark
   /// reaching definitions as live.

 }
 
 static bool isUnconditionalBranch(TerminatorInst *Term) {
   auto *BR = dyn_cast<BranchInst>(Term);
   return BR && BR->isUnconditional();
 }
 
 void AggressiveDeadCodeElimination::initialize() {
-  auto NumBlocks = F.size();
-
-  // We will have an entry in the map for each block so we grow the
-  // structure to twice that size to keep the load factor low in the hash table.
-  BlockInfo.reserve(NumBlocks);
   size_t NumInsts = 0;
 
   // Iterate over blocks and initialize BlockInfoVec entries, count
   // instructions to size the InstInfo hash table.
   for (auto &BB : F) {
     NumInsts += BB.size();
     auto &Info = BlockInfo[&BB];
     Info.BB = &BB;
     Info.Terminator = BB.getTerminator();