[RewriteStatepointsForGC] Workaround a lack of determinism in visit order

The visit order being used in the base pointer inference algorithm is currently non-deterministic.  When working on http://reviews.llvm.org/D12583, I discovered that we were relying on a peephole optimization to get deterministic ordering in one of the test cases.

This change is intented to let me test and land http://reviews.llvm.org/D12583.  The current code will not be long lived.  I'm starting to investigate a rewrite of the algorithm which will combine the post-process step into the initial algorithm and make the visit order determistic.  Before doing that, I wanted to make sure the existing code was complete and the test were stable.  Hopefully, patches should be up for review for the new algorithm this week or early next.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@246801 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp b/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
index 4153e64e2014c45c4e39427f8d271eace5066eca..d9dd80249de7b1b9784b99c844ff14d58581406b 100644 (file)
--- a/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
+++ b/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp
@@ -1026,14 +1026,19 @@ static Value *findBasePointer(Value *I, DefiningValueMapTy &cache) {
   DenseMap<Value *, Value *> ReverseMap;
   SmallPtrSet<Instruction *, 16> NewInsts;
   SmallSetVector<AssertingVH<Instruction>, 16> Worklist;
   DenseMap<Value *, Value *> ReverseMap;
   SmallPtrSet<Instruction *, 16> NewInsts;
   SmallSetVector<AssertingVH<Instruction>, 16> Worklist;

-  for (auto Item : states) {
-    Value *V = Item.first;
-    Value *Base = Item.second.getBase();
+  // Note: We need to visit the states in a deterministic order.  We uses the
+  // Keys we sorted above for this purpose.  Note that we are papering over a
+  // bigger problem with the algorithm above - it's visit order is not
+  // deterministic.  A larger change is needed to fix this.
+  for (auto Key : Keys) {
+    Value *V = Key;
+    auto State = states[Key];
+    Value *Base = State.getBase();

     assert(V && Base);
     assert(!isKnownBaseResult(V) && "why did it get added?");
     assert(isKnownBaseResult(Base) &&
            "must be something we 'know' is a base pointer");
     assert(V && Base);
     assert(!isKnownBaseResult(V) && "why did it get added?");
     assert(isKnownBaseResult(Base) &&
            "must be something we 'know' is a base pointer");

-    if (!Item.second.isConflict())
+    if (!State.isConflict())

       continue;
 
     ReverseMap[Base] = V;
       continue;
 
     ReverseMap[Base] = V;