From 6018104d5e026f0b97b7334614b72cad7353eb1a Mon Sep 17 00:00:00 2001 From: Mikael Holmen Date: Fri, 3 Nov 2017 14:15:08 +0000 Subject: [PATCH] [ADCE] Use MapVector for BlockInfo to make iteration order deterministic 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. Reviewers: kuhar, david2050 Reviewed By: kuhar Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D39593 llvm-svn: 317323 --- llvm/include/llvm/ADT/MapVector.h | 7 +++++++ llvm/lib/Transforms/Scalar/ADCE.cpp | 4 +++- 2 files changed, 10 insertions(+), 1 deletion(-) diff --git a/llvm/include/llvm/ADT/MapVector.h b/llvm/include/llvm/ADT/MapVector.h index 26a555e..3d78f4b 100644 --- a/llvm/include/llvm/ADT/MapVector.h +++ b/llvm/include/llvm/ADT/MapVector.h @@ -56,6 +56,13 @@ public: 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(); } diff --git a/llvm/lib/Transforms/Scalar/ADCE.cpp b/llvm/lib/Transforms/Scalar/ADCE.cpp index f04d0f0..1e683db 100644 --- a/llvm/lib/Transforms/Scalar/ADCE.cpp +++ b/llvm/lib/Transforms/Scalar/ADCE.cpp @@ -18,6 +18,7 @@ #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" @@ -118,7 +119,8 @@ class AggressiveDeadCodeElimination { PostDominatorTree &PDT; /// Mapping of blocks to associated information, an element in BlockInfoVec. - DenseMap BlockInfo; + /// Use MapVector to get deterministic iteration order. + MapVector BlockInfo; bool isLive(BasicBlock *BB) { return BlockInfo[BB].Live; } /// Mapping of instructions to associated information. -- 2.7.4