[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 ↗

(On Diff #121463)

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 ↗

(On Diff #121463)

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 ↗

(On Diff #121463)

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 ↗

(On Diff #121463)

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.

llvm/trunk/include/llvm/ADT/MapVector.h

public:
   /// Clear the MapVector and return the underlying vector.
   VectorType takeVector() {
     Map.clear();
     return std::move(Vector);
   }
 
   size_type size() const { return Vector.size(); }
 
+  /// Grow the MapVector so that it can contain at least \p NumEntries items
+  /// before resizing again.
+  void reserve(size_type NumEntries) {
+    Map.reserve(NumEntries);
+    Vector.reserve(NumEntries);
+  }
+
   iterator begin() { return Vector.begin(); }
   const_iterator begin() const { return Vector.begin(); }
   iterator end() { return Vector.end(); }
   const_iterator end() const { return Vector.end(); }
 
   reverse_iterator rbegin() { return Vector.rbegin(); }
   const_reverse_iterator rbegin() const { return Vector.rbegin(); }
   reverse_iterator rend() { return Vector.rend(); }

llvm/trunk/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.