Fix non-determinism in Reassociate caused by address coincidences
Summary:
Between building the pair map and querying it there are a few places that
erase and create Values. It's rare but the address of these newly created
Values is occasionally the same as a just-erased Value that we already
have in the pair map. These coincidences should be accounted for to avoid
non-determinism.
Thanks to Roman Tereshin for the test case.
Reviewers: rtereshin, bogner
Reviewed By: rtereshin
Subscribers: mgrang, llvm-commits
Tags: #llvm
Differential Revision: https://reviews.llvm.org/D59401
llvm-svn: 356803
diff --git a/llvm/lib/Transforms/Scalar/Reassociate.cpp b/llvm/lib/Transforms/Scalar/Reassociate.cpp
index 6da9571..34066ae 100644
--- a/llvm/lib/Transforms/Scalar/Reassociate.cpp
+++ b/llvm/lib/Transforms/Scalar/Reassociate.cpp
@@ -2217,8 +2217,15 @@
if (std::less<Value *>()(Op1, Op0))
std::swap(Op0, Op1);
auto it = PairMap[Idx].find({Op0, Op1});
- if (it != PairMap[Idx].end())
- Score += it->second;
+ if (it != PairMap[Idx].end()) {
+ // Functions like BreakUpSubtract() can erase the Values we're using
+ // as keys and create new Values after we built the PairMap. There's a
+ // small chance that the new nodes can have the same address as
+ // something already in the table. We shouldn't accumulate the stored
+ // score in that case as it refers to the wrong Value.
+ if (it->second.isValid())
+ Score += it->second.Score;
+ }
unsigned MaxRank = std::max(Ops[i].Rank, Ops[j].Rank);
if (Score > Max || (Score == Max && MaxRank < BestRank)) {
@@ -2287,9 +2294,15 @@
std::swap(Op0, Op1);
if (!Visited.insert({Op0, Op1}).second)
continue;
- auto res = PairMap[BinaryIdx].insert({{Op0, Op1}, 1});
- if (!res.second)
- ++res.first->second;
+ auto res = PairMap[BinaryIdx].insert({{Op0, Op1}, {Op0, Op1, 1}});
+ if (!res.second) {
+ // If either key value has been erased then we've got the same
+ // address by coincidence. That can't happen here because nothing is
+ // erasing values but it can happen by the time we're querying the
+ // map.
+ assert(res.first->second.isValid() && "WeakVH invalidated");
+ ++res.first->second.Score;
+ }
}
}
}